フィボナッチ数の計算
スポンサーリンク
ここでは「フィボナッチ数を計算」し、フィボナッチ数列を表示するサンプルプログラムを紹介します。
フィボナッチ数
\(n\)番目のフィボナッチ数\(F_n\)は
\[ \begin{aligned} F_0 &= 0\\ F_1 &= 1\\ F_{n+2} &= F_{n} + F_{n+1} (n\geq1) \end{aligned} \]で定義されます。
実際に\(n=0\)から計算してみると \[ \begin{aligned} F_0 &= 0\\ F_1 &= 1\\ F_2 &= 1 = 0 + 1\\ F_3 &= 2 = 1 + 1\\ F_4 &= 3 = 1 + 2\\ F_5 &= 5 = 2 + 3\\ F_6 &= 8 = 3 + 5\\ F_7 &= 13 = 5 + 8\\ \cdots \end{aligned} \]
となり、計算結果を並べた数列
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,...
を「フィボナッチ数列」といいます。
それではプログラムでフィボナッチ数を計算してみましょう。
サンプルプログラム
10000より小さいフィボナッチ数を計算するサンプルプログラムです。
/*
* C言語のサンプルプログラム - Webkaru
* - フィボナッチ数の計算 -
*/
#include <stdio.h>
int main(void)
{
/* 変数の宣言 */
int n;
int f0, f1, f2;
f0 = 0;
f1 = 1;
/* フィボナッチ数(n=0)の出力 */
printf("%d\n", f0);
/* フィボナッチ数の計算 */
while(f1<100000) {
// フィボナッチ数の出力(n>0)
printf("%d\n", f1);
// フィボナッチ数の計算
f2 = f1 + f0;
// 変数の代入
f0 = f1;
f1 = f2;
}
return 0;
}
実行結果です。
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025
このように計算したフィボナッチ数が出力されます。