「プロジェクトオイラー解説問2」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー解説問2 - (2014/01/07 (火) 03:36:31) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

 ----
 *Problem 2 「偶数のフィボナッチ数」 †
 フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである.
 
 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 数列の項の値が400万以下の, 偶数値の項の総和を求めよ.
 ----
 **解説
 この問題の本当に賢い解法はリンク先をご覧ください。
 http://bach.istc.kobe-u.ac.jp/lect/ProLang/org/euler-002.html
 私の解説よりずっと高度な解説をしています。
 
 
 ***初等的解法
 
 フィナボッチ数列を眺めると
-1   1  2  3  5  8 13 21 34 55 89 144
-奇 奇 偶 奇 奇 偶 奇 奇 偶 奇 奇 偶
+ 1   1  2  3  5  8 13 21 34 55 89 144 
+ 奇 奇 偶 奇 奇 偶 奇 奇 偶 奇 奇 偶
 と奇奇偶とループしていることがわかります。
 
 これはフィナボッチ数列の規則から言って当然のことで。
 Fi+2=Fi+Fi+1
 偶数=奇数+奇数
 奇数=奇数+偶数
 奇数=奇数+奇数
 偶数=偶数+偶数
 です。
 F3=F1+F2
 偶数=奇+奇
 F4=F3+F2
 奇数=偶数+奇数
 F5=F4+F3
 奇数=奇数+偶数
 そして
 F6=F5+F4で
 偶数=奇数+奇数
 と偶数と奇数は3周期でループします。
 
 よってフィナボッチ数列の
 3,6,9,,,3n個めと3の倍数だけ計算していけばいいことがわかります。
 
 まず最初はF3は特別で。
 F3=F1+F2
 
 F6は数列を展開するとフィナボッチ数列の定義より
 F6=F5+F4=(F4+F3)+(F3+F2)=((F3+F2)+F3)+(F3+F2)=3F3+2F2となります。
 
 F6=3*F(6-3)+2*F(6-4)ですね。
 F9=3*F6+2*F5
 F12=3*F9+2*F8
 F15=3*F12+2*F11
 ,,,,
 と単調に続いていきます。
 よって漸化式は
 F(3n+3)=3*F(3n)+2*F(3n-1)となると分かります。
 
 
 計算に必要なF(3n-1)はF5の場合で実験すると
 F5=F4+F3=(F3+F2)+F2=F3+2F2
 
 となります。
 一般の場合は
 F(3n-1)=F(3n-3)+2*F(3n-4)
 F(3n)=3*F(3n-3)+2*F(3n-4)
 
 この漸化式を計算していけばF(3n)を足し合わせていけば答えとなります。