STEP 10.2　フィボナッチ数　(fibonacci number)

<問題> フィボナッチ数は、以下の漸化式で定義される。

 F (0) = 0,  F (1) = 1
 F (N) = F (N -1) +  F (N - 2) (N > 1)

部分解を、配列fib_num[N]に記録することを考えよう。

Nに関するfib_num[N]の値があれば、それを使う。
Nに関するfib_num[N]がないとき(初期値を-1として、計算されていないことをチェックする）は、再帰的な計算を行うことにしよう。

<実行結果 例>　
n :7
fib (7) = 13

n :10
fib (10) = 55

n :45 
fib (45) = 1134903170  (え、っと思うほど速くなる））
解答例
#include <stdio.h>
#define N 100  /* 99まで用意 */

void ini_fiv_num(int n);
int fibonacci (int n);

int fib_num[N];   /* 記録用の配列 */

void ini_fiv_num (int n) {
   int i;
   for (i = 0; i < n ; i++)  /* 記録前は、全て -1に初期化 */
      fib_num[i] = -1;
}


int fibonacci (int n) {
   if (fib_num[n] == -1) { /* 記録がない場合 */
      if (n == 0)
         fib_num[0] = 0;
      else if (n == 1)
         fib_num[1] = 1;
      else /* 計算して、記録する */
         fib_num[n] = fibonacci(n-1) + fibonacci(n-2);
    }

   return fib_num[n]; /* 記録がある状況になっているので、その値を */
}


int main (void) {
   int n;
   ini_fiv_num (N);
   printf ("n :");
   scanf ("%d", &n);

   printf("fibonacci (%d) = %d \n", n, fibonacci(n));

   return 0;
}