フィボナッチ数列
さいきんちかごろ再帰がマイブームなので,フィボナッチ数列を書いてみました.
#include <stdio.h> //--------------------------------------------------------- // フィボナッチ数を求める // 引数 // n: フィボナッチ数の n 番目 // 戻り値 // 成功 -> フィボナッチ数 // 失敗 -> -1 ( n < 0 など) //--------------------------------------------------------- int fibonacciNumber(int n) { int r = 0; // 戻り値 if(n == 0) // 0 番目は 0 { r = 0; } else if(n == 1) // 1 番目は 1 { r = 1; } else if(n >= 2) // 一つ前と,二つ前のフィボナッチ数を足す { r = fibonacciNumber(n-1) + fibonacciNumber(n-2); } else // エラー { r = -1; } return r; } int main(int argc, char **argv) { int f; // フィボナッチ数 int l; // フィボナッチ数列の長さ int i; // ループ処理 while(1) { printf("フィボナッチ数列の長さを整数で入力( 0 で終了) -> "); scanf("%d", &l); if(l == 0) // 終了 { break; } for(i = 0; i < l; i++) { if((f = fibonacciNumber(i)) != -1) { printf("%d ", f); } } printf("\b\n"); } return 0; }
やっぱり動的計画法のほうが楽だね.
#include <stdio.h> //--------------------------------------------------------- // フィボナッチ数列を表示する // 引数 // l: フィボナッチ数の長さ //--------------------------------------------------------- void fibonacciNumber(int l) { int prepreF, preF, crrF; // 前の前のフィボナッチ数,前のフィボナッチ数,今のフィボナッチ数 int i; // ループ処理 // 0 番目と 1 番目 for(i = 0; i < l && i < 2; i++) { printf("%d ", i); } // 2 番目以降 prepreF = 0; preF = 1; for(i = 2; i < l; i++) { crrF = preF + prepreF; // F(n-1) + F(n-2) printf("%d ", crrF); preF = crrF; // F(n-1) の更新 prepreF = preF; // F(n-2) の更新 } printf("\n"); } int main(int argc, char **argv) { int l; // フィボナッチ数列の長さ while(1) { printf("フィボナッチ数列の長さを整数で入力( 0 以下で終了) -> "); scanf("%d", &l); if(l <= 0) // 終了 { break; } fibonacciNumber(l); } return 0; }
[追記: 0802]
knct-csさんからコメントをいただいたので,直してみました.
ついでに,引数は 2 以上であることが多いと期待して条件式の順番を入れ替えてみました.
感想,すずめの涙ですね(・・;
//--------------------------------------------------------- // フィボナッチ数を求める // 引数 // n: フィボナッチ数の n 番目 // 戻り値 // 成功 -> フィボナッチ数 // 失敗 -> -1 ( n < 0 など) //--------------------------------------------------------- int fibonacciNumber(int n) { int r = -1; // 戻り値 if(n >= 2) // 一つ前と,二つ前のフィボナッチ数を足す { r = fibonacciNumber(n-1) + fibonacciNumber(n-2); } else if(n >= 0) // ゼロ番目と一番目は n と同じ値(0, 1) { r = n; } else // エラー { r = -1; } return r; }