フィボナッチ数列を計算してみよう C言語

フィボナッチ数列とは直前の2つの数字の和になっている数列のことです。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

数列を見たら分かりますね。C言語でプログラミングしていきましょう。

3通りの方法で書いています。

fibo1, fibo2, fibo3 と進むにつれて処理が早くなっています。

fibo1が最も単純で何度も再起呼び出しをしていて遅い方法です。

fibo2はデータを保存して再起呼び出しの回数を少なくしています。

fibo3が一番シンプルです。for文で回しているだけです。
初めからfibo3で書けよという感じですね。

関数の再起呼び出しは難しい。プログラムを読むだけで頭を使います。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_VAL 47
unsigned long fibo2Arr[MAX_VAL];
unsigned long fibo3Arr[MAX_VAL];

unsigned long fibo1(int n)
{
unsigned long f;
switch (n) {
case 1:
case 2:
f = 1L;
break;
default:
f = fibo1(n - 1) + fibo1(n - 2);
break;
}
return (f);
}

unsigned long fibo2(int n)
{
unsigned long f;
if (fibo2Arr[n]) {
f = fibo2Arr[n];
return (f);
}
switch (n) {
case 1:
case 2:
f = 1L;
break;
default:
f = fibo2(n  - 1) + fibo2(n - 2);
break;
}
fibo2Arr[n] = f;
return (f);
}

unsigned long fibo3(int n)
{
int i;
fibo3Arr[1] = 1;
fibo3Arr[2] = 1;
for (i = 3; i <= n; i++) {
fibo3Arr[i] = fibo3Arr[i - 1] + fibo3Arr[i - 2];
}
return (fibo3Arr[n]);
}

int main(void)
{
int n = MAX_VAL;
clock_t start, end;
unsigned long result1, result2, result3;
start = clock();
result1 = fibo1(n);
end = clock();
printf("fibo1 %lu %f\n", result1, (double)end - start);
start = clock();
result2 = fibo2(n);
end = clock();
printf("fibo2 %lu %f\n", result2, (double)end - start);
start = clock();
result3 = fibo3(n);
end = clock();
printf("fibo3 %lu %f\n", result3, (double)end - start);
return 0;


フィボナッチ数列の47まで計算して、それぞれ掛かった時間を計測しています。

私の環境ではこんな感じ。fibo1だけがやたら遅いです。

fibo1 2971215073 15680165.000000

fibo2 2971215073 2.000000

fibo3 2971215073 1.000000

フィボナッチ数列の47は
2971215073です。

たった47番目で 約30億になりますよ、と。

Wolfram Alphaで検索して合っているか確認してみましょう。

http://www.wolframalpha.com/input/?i=fibonacci+47 

同様に100番目でも検索してみてください。 

http://www.wolframalpha.com/input/?i=fibonacci+100