我正在编写一段代码,用于计算下面函数 g(x)
中相对于自然数的间隙,然后对它们求和。
from math import *
a = set()
n = eval(input("n = "))
def g(x):
return floor(x*log10(x)) # thanks to tzaman
b = 1
while g(b) < n:
a.add(g(b))
b+=1
aprime = set(range(max(a)))
z = max(a)
print(z*(z+1)/2-sum(a)) # thanks to tzaman
input("Done!")
我试图让 n = 10 ** 10
,即 10000000000
,并在合理的时间内(例如 < 10 分钟)执行计算。然而,这段代码的执行时间长得可笑,我想知道:是否有更有效的方法来做到这一点?
I/O 示例
n = 12, output = 15
其他信息
下图比较了x
和g(x)
:
x | 1 2 3 4 5 6 7 8 9 10 11 12
g(x) | 0 0 1 2 3 4 5 7 8 10 11 12
集合x\g(x)
表示x
中而不是g(x)
中的成员,并且对于以下数字12、{0,6,9}
;它们的总和是 15。因此,当 n = 12
时,output = 15
。
最佳答案
您的麻烦可能来自于 sum(aprime-a)
行。这迫使 python 计算两个集合的集合差。考虑到您的集合有多大,这会极大浪费时间。
请注意,当 b
是 a
的子集时,sum(a-b) = sum(a)-sum(b)
(如这是你的情况)。所以我们现在有 sum(aprime)-sum(a)
。
接下来利用 aprime
只是一个算术序列这一事实!你有一个公式来计算这些东西的总和!您可以代替 sum(aprime)
maxVal = max(a)
sumAPrime = ((maxVal +1)*maxVal)/2
所以您现在有了 sumAPrime - sum(a)
作为您的解决方案!
我将假设您需要优化才能适用于任何任意函数 g
,因此您不能对代码中的函数做出假设。
希望这有帮助! :)
关于python - 用函数变换集合的高效算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31973507/