3

我有一些小软件可以计算每个三角形数的因子数，以查看其中第一个因子的数量超过 X 个（是的，这是一个投影仪问题，数字 12，虽然我没有解决它）...当我试图使 X 一些随机值以查看代码的作用和时间时，我注意到一些奇怪的事情（至少对我来说）：直到 X=47 执行时间以明显正常的方式增加，但是当 X = 48 它比正常增加更多，并且函数调用比速率大得多，如果我这么说它（爆炸）..它为什么这样做？

编码：

def fac(n):
    c=0
    for i in range (1,n+1):
        if n%i==0:
            c=c+1
    return c

n=1

while True:
    summ=0
    for i in range (1,n+1):
        summ=summ+i
    if fac(summ)>X:
        break
    n=n+1

print summ

在分析时：

when X=45 :  314 function calls in 0.027 CPU seconds
when X=46 :  314 function calls in 0.026 CPU seconds
when X=47 :  314 function calls in 0.026 CPU seconds
when X=48 :  674 function calls in 0.233 CPU seconds
when X=49 :  674 function calls in 0.237 CPU seconds

我假设如果我继续我会遇到系统调用增加和时间突然增加的其他点，以前有这样的点，但时间太小所以没那么重要。为什么函数调用突然增加？难道不应该为新值再调用一次函数吗？

PS我使用cProfile作为分析器，X这里的代码只是为了演示，我直接在代码中写了值...提前谢谢...

4

2 回答 2

6

您是否查看过所涉及的实际值？

第一个超过 47 个因子的三角形数是 T(104) = 5460，它有 48 个因子。

但是第一个超过 48 个因子的三角形数是 T(224) = 25200，它有 90 个因子。所以难怪它需要更多的工作。

如果您的代码运行到 T( n )，那么它会调用range2 n次和fac n次，总共 3 n次函数调用。因此，对于 T(104)，它需要 312 个函数调用，而对于 T(224)，它需要 672 个函数调用。据推测，您没有向我们展示的某处有 2 个开销函数调用，这解释了您获得的分析结果。

您当前的策略不会让您找到欧拉计划问题的答案。但我可以给出一些提示。

  • summ=0每次计算三角形数时都必须重新开始吗？
  • 您是否必须遍历直到n的所有数字才能计算出它有多少个除数？有没有更快的方法？（2 16 = 65536 有多少个除数？你必须循环从 1 到 65536 的所有数字吗？）
  • 三角数有多少个除数？（查看一些可以计算答案的小三角数。）你能看到任何可以帮助你计算更大三角数答案的模式吗？
于 2011-08-06T23:44:25.187 回答
3

如果您检查输出，您会看到执行时间出现几个峰值（突然增加）。

原因是所需的循环数不是逐渐增加而是突然增加。n循环后打印出来while True，你会看到它。

注意：欧拉是数学网站，不要写蛮力算法；）

于 2011-08-06T23:43:42.550 回答