Project Euler 問題2（偶数のフィボナッチ数）を解いてみる

Project Euler で紹介されている問題2を解いてみました。素直にプログラミングした例とフィボナッチ数列の性質を使った例を紹介します。

問題2（偶数のフィボナッチ数）

解答例

素直に実装してみます。C での実装例です。

#include <stdio.h>

int main(void)
{
	int i1, i2, i3, sum;

	i1 = 1;
	i2 = 2;
	sum = 2;

	i3 = i1 + i2;
	while (i3 <= 4000000) {
		if (i3 % 2 == 0) {
			sum += i3;
		}
		i1 = i2;
		i2 = i3;
		i3 = i1 + i2;
	}

	printf("Problem002: %d\n", sum);

	return 0;
}

前の2項を足すことで得られるフィボナッチ数列の項が偶数か調べて、偶数なら解答を表す変数 sum に加えます。繰り返し文の中では、項をずらして、次のフィボナッチ数を求めていきます。

考察

フィボナッチ数列は、前の2項を加えて次の項を求める、という簡単な規則に基づいています。問題では最初の10項を計算していました。もう少し計算してみましょう。

　1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

3項毎に偶数が現れます。これは偶然ではなく、以下のように繰り返されるからです。

• 奇数, 偶数　→　次は奇数（奇数＋偶数）
• 奇数, 偶数, 奇数　→　次は奇数（偶数＋奇数）
• 奇数, 偶数, 奇数, 奇数　→　次は偶数（奇数＋奇数）
• 奇数, 偶数, 奇数, 奇数, 偶数　→　最初の場合に戻る

つまり偶数のフィボナッチ数は、2から3項毎に現れることが分かります。各項をFn（n：自然数）と書くと、以下のようになります。

• F1, F2, F3 = F1 + F2
• F1, F2, F3, F4 = F2 + F3 = F2 +（F1 + F2）= F1 + 2 × F2
• F1, F2, F3, F4, F5 = F3 + F4 =（F1 + F2）+（F1 + 2 × F2）= 2 × F1 + 3 × F2

これを繰り返すと、偶数のフィボナッチ数だけ求めることができます。

解答例（改善版1）

#include <stdio.h>

int main(void)
{
	int i1, i2, i3, sum;

	i1 = 1;
	i2 = 2;
	sum = 2;

	i3 = 2 * i1 + 3 * i2;
	i1 = i1 + 2 * i2;
	i2 = i3;
	while (i3 <= 4000000) {
		sum += i3;
		i3 = 2 * i1 + 3 * i2;
		i1 = i1 + 2 * i2;
		i2 = i3;
	}

	printf("Problem002: %d\n", sum);

	return 0;
}

元の解答例は、while ループで、毎回フィボナッチ数を計算していますが、改善版は、偶数分しか繰り返されないため、ループ回数は、3分の1になっています。また偶数だけ判定するため、条件判断文も無くなりました。一方、ループの繰り返し中に、掛け算が入っています。オーダーレベルの計算量は変わらないですが、多少でも計算は減っているでしょうか。

最後に

フィボナッチ数列は、自然界に現れたり、一般項に黄金比がでてくるなど、いろいろな興味深い性質があることが知られています。「フィボナッチ数列」で検索してください。

解答例に加えて改善版を紹介しました。別の工夫を追加で紹介するため、次回もこの問題について解説します。