「プロジェクトオイラー解説問2」の編集履歴（バックアップ）一覧はこちら
「プロジェクトオイラー解説問2」(2014/01/07 (火) 08:44:25) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*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
奇 奇 偶 奇 奇 偶 奇 奇 偶 奇 奇 偶
と奇奇偶とループしていることがわかります。
これはフィナボッチ数列の規則から言って当然のことで。
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)+F3=2*F3+F2
となります。
一般の場合は
F(3n-1)=2F(3n-3)+F(3n-4)
F(3n)=3*F(3n-3)+2*F(3n-4)
この漸化式を計算してF（３ｎ）を足し合わせていけば答えとなります。
実験してみましょう。
F3=2 F2=1は既知とします.
F6 =3*F3+2*F2 F5 =2*F3+F2
F9 =3*F6+2*F5 F8 =2*F6+F5
F12=3*F9+2*F8 F11=2*F9+F8
,,,
と単調に計算が進みます。
上の行から次の行が決まることが簡単に確認できるでしょう。
----
*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
奇 奇 偶 奇 奇 偶 奇 奇 偶 奇 奇 偶
と奇奇偶とループしていることがわかります。
これはフィナボッチ数列の規則から言って当然のことで。
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となります。
F9=F8+F7=(F7+F6)+(F6+F5)=((F6+F5)+F6)+(F6+F5)=3F6+2F5
これは一般的な規則で
F6=3*F3+2*F2=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)+F3=2*F3+F2
となります。
一般の場合は
F(3n-1)=2F(3n-3)+F(3n-4)
F(3n)=3*F(3n-3)+2*F(3n-4)
この漸化式を計算してF（３ｎ）を足し合わせていけば答えとなります。
実験してみましょう。
F3=2 F2=1は既知とします.
F6 =3*F3+2*F2 F5 =2*F3+F2
F9 =3*F6+2*F5 F8 =2*F6+F5
F12=3*F9+2*F8 F11=2*F9+F8
,,,
と単調に計算が進みます。
上の行から次の行が決まることが簡単に確認できるでしょう。
