サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：再帰＞フィボナッチ数列を表示する関数（動的計画法版）
[フィボナッチ数列（再帰改良版）]←このソース→[ファイル操作の基本]
今回もフィボナッチ数を求める関数を作ります。前回、前々回は再帰的呼び出しを使ってフィボナッチ数を求めました。今回は、違う方法で、しかも、もっと高速に求めます。まず、フィボナッチ数の定義にもう一度戻ります。フィボナッチ数とは、
- i = 1 の時 Fibo(1) = 1
- i = 2 の時 Fibo(2) = 1
- i = 3 の時 Fibo(3) = 2
- i = 4 の時 Fibo(4) = 3
- i = 5 の時 Fibo(5) = 5
- - - - - - -
- i = n の時 Fibo(n) = Fibo(n - 1) + Fibo(n - 2)
- - - - - - -
Fibo(1)とFibo(2)を例外として、任意の項はその前の２つの項の合計になっています。結局下記の数列になります。
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, - - -
再帰的呼び出しでは、フィボナッチ数の大きいものから小さいものを呼び出して求めました。今回は逆に１から順にnまで求める方法を検討します。前回は計算結果を配列に保存し、計算済みのものは再利用しました。計算結果保存用の配列result[ ]は関数の外で宣言しました。従って、result[ ]は静的領域に存在し、コンパイル時に０に初期化されます。また、プログラムの実行中常にメモリに存在し、関数から抜け出してもその値は保持されます。
前回と同様に、配列result[ ]は静的領域に置きます。Fibo(n)の値を計算するにあたって、この配列を使います。
n = 1 の時 Fibo(1) = 1 なので、result[1]には1Lを保存
n = 2 の時 Fibo(2) = 1 なので、result[2]には1Lを保存
n = 3の時 Fibo(3) = Fibo(2) + Fibo(1) ですが、下記のように書き換えることができます。
Fibo(3) = result[2] + result[1];
つまり、Fibo(3)以降はフィボナッチ数を計算する代わりに、 配列の添字の１小さいものと、２小さいものを足せば求められます。この計算を順次行い、nに達したら計算結果をリターンすれば、 Fibo(n)が求められます。
このように、問題を分割し、分割された問題の解を蓄えておき、 部分問題の再計算を避ける方法を動的計画法といいます。 */
#include <stdio.h> #include <stdlib.h> /* exit( )で必要 */ #define MAX_VAL 48 unsigned long result[MAX_VAL]; /* ここに計算結果を保存 */ /* nのフィボナッチ数を返す */ unsigned long Fibo3(int n) { int i; result[1] = 1; /* n が 1 なら result[1] は 1 */ result[2] = 1; /* n が 2 なら result[2] は 1 */ /* nが１か２ならこのループは実行されない */ for (i = 3; i <= n; i++)/* 計算結果を蓄えながら計算を進める */ result[i] = result[i - 1] + result[i - 2]; return (result[n]); } void main(void) { int n; /* nのフィボナッチ数を求める */ printf("１から４７までの整数を入力して下さい\t"); scanf("%d", &n); if(n > MAX_VAL -1) { /* nが４７より大きければ何もしないで終了 */ printf("数字が大き過ぎます\n"); exit(0); } /* フィボナッチ数を表示 */ printf("\nFibonacci 数は %lu\n", Fibo3(n)); } |
[フィボナッチ数列（再帰改良版）]←このソース→[ファイル操作の基本]
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−