2

我有一个解决Project Euler Problem 2的 Haskell 解决方案，它适用于 400 万限制以及高达 10^100000 的限制，在我的机器上只需要几秒钟。

但是对于任何更大的值，例如 10^1000000，计算不会及时返回，如果有的话（尝试将其放置几分钟）。这里的限制因素是什么？

evenFibonacciSum :: Integer -> Integer
evenFibonacciSum limit = 
  foldl' (\t (_,b) -> t + b) 0 . takeWhile ((<=limit) . snd) . iterate doIteration $ (1,2) where
    doIteration (a, b) = (twoAB - a, twoAB + b) where
      twoAB = 2*(a + b)
4

2 回答 2

5

问题是您正在对（偶数）斐波那契数进行求和。这意味着您必须全部计算。但

F(n) ≈ φ^n / √5, with  φ = (1 + √5)/2

因此，您添加了很多大尺寸的Θ(n)位数，用于F(n). 对于 的限制10^1000000，您需要大约 800000×2 个大于 的数字相加10^500000。通常，您需要Θ(n)将数字与Θ(n)位相加。

添加d数字[以任何基数]是一项O(d)操作。所以你的算法是指数的二次方。

为避免这种情况，请为S(k)第一个k偶数斐波那契数的总和找到一个封闭公式（提示：这是一个涉及一个斐波那契数的相对简单的公式），找到最大k的F(3*k) <= limit，然后使用公式和算法计算总和以F(n)计算O(log n)步骤例如这里。

于 2012-12-18T00:13:42.783 回答
0

这里的问题似乎是您正在使用一个公式来计算需要线性时间的偶数斐波那契数。I如果你加倍你的限制，你的计算时间也会加倍。应该有一个只需要对数时间的算法（如果你把限制加倍，时间会改变一个常数值），但你的工作就是找出答案。我不会在这里破坏欧拉的答案。

于 2012-12-17T23:12:32.370 回答