4

私は Haskell にはかなり慣れていません。問題は、400 万以下のすべての偶数フィボナッチ数の合計を見つけることです。リストが使えません。

私が正しく理解していれば、リストを使用しているため、以下の解決策は間違っています。

my_sum = sum $ filter (odd) $ takeWhile (< 4000000) fibs

ここで、 fibsはすべてのフィボナッチ数のリストです。

どういうわけか、リストの観点から Haskell を考えないのは難しいと思います。この問題の解決策を教えてくれる人はいますか?

よろしく

編集：

誰かが興味を持っているなら、私はこの問題を解決しました。これがコードです（非常に不器用に見えますが、それでも動作します）：

findsum threshold = findsum' 0 1 0 threshold


findsum' n1 n2 accu t 
| n2 > t    = accu
| odd n2    = findsum' n2 n3 accu t 
| otherwise = findsum' n2 n3 accu2 t
where
    n3 = n2 + n1
    accu2 = accu + n2
4

3 に答える 3

5

これを Excel で作成し、そこからコードを理解する方が簡単な場合があります。これをエクセルで行うのはとても簡単です。最初のセルに 1 を入力し、そのすぐ下に 1 を入力します。次に、その下のすべてのセルを作成し、その上の 2 つを追加します。(つまり、セル a3 には =A1+A2 が含まれます)。次の列に偶数値のみを含めるようにします「つまり、if(mod(a3,2)==0,a3,0)」。次に、現在の合計を 3 番目の列に入力します。それに基づいて、再帰的なソリューションを考え出すことができるはずです。

別の方法は、問題から始めることです。アキュムレータを求めて叫ぶ合計だけが必要です。

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold

上記の関数の署名を見ることができます。私は、フィボナッチ数の構築をいつ終了するかを決定するしきい値 (4,000,000) を使用するきれいなフロント エンドを作成しました。次に、これに最初の 2 つのフィボナッチ数とアキュムレータを加えて、再帰を行うワーカー関数「sumFib」に渡します。出来上がり...答え、「4613732」、リストなし....

n1 は n-1 フィボナッチ数、n2 は n-2 フィボナッチ数です。

それが役立つことを願っています。

編集:ここに私の完全な解決策があります:

sumFib :: Integer -> Integer
sumFib threshold = sumFib' 1 1 0 threshold

sumFib' :: Integer -> Integer -> Integer -> Integer -> Integer
sumFib' n1 n2 acc threshold
     | n1 > threshold = acc
     | otherwise = sumFib' (n2+n1) n1 newAcc threshold
            where newAcc = if n1 `mod` 2 == 0
                               then n1 + acc
                               else acc
于 2010-05-05T21:18:38.193 に答える
3

これは、リストなしで、再帰的ソリューションを使用して、継続渡しスタイルを使用して行うことができます。

ところで、すべてのフィボナッチ数を実行し、奇数を除外することは、この問題を解決するための遅い方法です。

于 2010-05-05T20:59:29.303 に答える
3

繰り返しになりますが、コンピューターがいかに有用であるかを示す非例:

パソコンがなくてもできる！

最初の観測: 3 つおきの Fibo 数は偶数で、最初の偶数の Fibo 数は F_3=2 です

確かに：奇数+奇数=偶数; 奇数+偶数=奇数; 偶数+奇数=奇数、すでに円を閉じています

2 番目の観測: F_3 + F_6 + F_9 + ... + F_{3k} = 1/2 (F_{3k+2} - 1)

誘導による: F_3 = 2 = 1/2 (5 - 1) = 1/2 (F_5 - 1)

F_3 + F_6 + ... + F_{3k+3} = 1/2 (F_{3k+2} - 1) + F_{3k+3} = 1/2 (F_{3k+2} + 2F_{3k +3} -1) = 1/2 (F_{3k+4} + F_{3k+3} -1) = 1/2 (F_{3k+5} -1)

3 番目の観察: 合計には 1333333 の加数があり、最後の加数は 3999999 番目の Fibo 数です。

4 番目の観測: F_n = 1/sqrt(5) * (phi^n - (1-phi)^n)

ウィキペディアによる証明

これで、パーツをまとめることができます: F_3 + F_6 + ... + F_3999999 = 1/2 (F_4000001 - 1) = 1/2 1/sqrt(5) (φ^4000001 - (1-φ)^4000001) - 1/2 = int(1/2 1/sqrt(5) φ^4000001)

ここで int は整数部分です。-1 < 1-phi < 0 なので (1-phi)^4000001 はほとんど消えてしまうので、最後のステップは機能します。電卓を使用して数値を取得することができます。

于 2010-05-14T20:24:12.697 に答える