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

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

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

再帰を使わないプログラムを書こう (2から、Nまでどんどん計算していくイメージで)


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

n :10
fib (10) = 55

n :45 
fib (45) = 1134903170  (速い)

(全てのプログラムが出ます)

解答例
#include <stdio.h>

int fib1(int n) {
   int f0, f1, f, i;
   if (n == 0)
      return 0;
   else if (n == 1)
      return 1;
   else { /* i > 1 の場合は、1つ前の値と2つ前の値を更新していくプログラム */
      f0 = 0;
      f1 = 1;
      for (i = 2; i<= n; i++) { /* i=2からはじめて、カウンタをあげていく i=nになったら、答え */
         f = f0+ f1;
         f0 = f1;
         f1 = f ;
      }
      return f;
   }
}

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

   printf("fib (%d) = %d \n", n, fib1(n));

   return 0;
}