問題
フィボナッチ数列において、400万以下の偶数項の総和を求めよ。
とりあえずフィボナッチ数列ぶん回すか!
using System; using System.Diagnostics; namespace Problem2 { class Program { static void Main(string[] args) { Debug.WriteLine(EF1(4000000)); } static int EF1(int max) { int f1, f2; int sum = 0; f1 = 1; f2 = 1; while(true) { int f3 = f1 + f2; if (f3 > max) break; if (f3 % 2 == 0) sum += f3; f1 = f2; f2 = f3; } return sum; } } }
いつも通りフィボナッチ数列の項を1つ1つ判定して足していくプログラムです。
偶数の出かたとか
フィボナッチ数列は
\( 0,1,1,2,3,5,8,13,21,34,\cdots \)
と続きます。
前の2項を足したものが次の項、という形ですね。
漸化式としてはこんなの。
\(a_{n+2} = a_{n+1} + a_{n} \)
数列をよく見ればわかりますが、規則正しい間隔で偶数が出現してます。
最初の0を抜かせば、
\(奇数、奇数、偶数、奇数、奇数、偶数、\cdots \)
という形になっています。
つまり、約2/3が奇数なので全部奇数偶数チェックする必要はないってこと。
じゃぁ偶数項だけ算出できないかなと考えて、偶数項だけ抜き出してみました。
\( 2, 8, 34, 144, 610, 2584, \cdots \)
じっと見てると「なんとなく4倍くらい…?」と感じたので(直感派)いじくると、こんな式になりました。
\( a_{n+2} = 4 \cdot a_{n+1} + a_{n} \)
例えば、偶数第4項の値を求めるには、
\( a_{4} = 4 \cdot a_{3} + a_{2} \)
\( a_{4} = 4 \cdot 34 + 8 \)
\( a_{4} = 136 + 8 = 144 \)
と、こんな感じ。
これを使えばフィボナッチ数列から偶数項だけを取り出せる。
…まぁ、フィボナッチ数列の一般項使えばいいんですけどね。
偶数列でやってみる
using System; using System.Diagnostics; namespace Problem2 { class Program { static void Main(string[] args) { Debug.WriteLine(EF2(4000000)); } static int EF2(int max) { int sum = 0; int f2 = 2; int f1 = 0; sum += f2; while (true) { int fnext = f2 * 4 + f1; if (fnext > max) break; sum += fnext; f1 = f2; f2 = fnext; } return sum; } } }
- 作者: ジョセフダグニーズ,ジョンオブライエン,Joseph D’Agnese,John O’Brien,渋谷弘子
- 出版社/メーカー: さえら書房
- 発売日: 2010/09
- メディア: ハードカバー
- クリック: 37回
- この商品を含むブログ (3件) を見る
- 作者: 近藤滋
- 出版社/メーカー: 学研プラス
- 発売日: 2013/09/13
- メディア: 単行本
- この商品を含むブログ (6件) を見る
- 作者: アルフレッド・S・ポザマンティエ、イングマル・レーマン,松浦俊輔
- 出版社/メーカー: 日経BP社
- 発売日: 2010/08/05
- メディア: 単行本
- 購入: 1人 クリック: 132回
- この商品を含むブログ (9件) を見る