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)演算です。したがって、アルゴリズムは指数で2次式になります。

S(k)これを回避するには、最初の偶数フィボナッチ数の合計の閉じた式を見つけ（ヒント： 1つのkフィボナッチ数を含む比較的簡単な式です）、最大のものを見つけて、式と計算するアルゴリズムを使用して合計を計算します。ステップ例：ここ。kF(3*k) <= limitF(n)O(log n)

于 2012-12-18T00:13:42.783 に答える
0

ここでの問題は、計算に線形時間がかかる偶数フィボナッチ数の式を使用しているようです。制限を2倍にすると、計算時間も2倍になります。対数時間しかかからないアルゴリズムがあるはずです（制限を2倍にすると、時間は一定の値で変化します）が、それを見つけるのはあなたの仕事です。ここでオイラーの答えを台無しにしているわけではありません。

于 2012-12-17T23:12:32.370 に答える