フィボナッチ数列を求めよう！

みなさん、フィボナッチ数列をご存知だろうか？
こんな数列。

1, 1, 2, 3, 5, 8, 13, 21, 34, ....

第n項の値が、第n-1項と第n-2項の和になっているような数列だ。

この数列を一般形で書くと、

f(n) = f(n-1) + f(n-2) if n => 2,
f(0) = 1,
f(1) = 1.

である。
さて、このフィボナッチ数列の第n項目を出力する関数 long long fibonacci(int n)を作成してみよう。

view plainprint?

1. long long fibonacci(int n) {  
2. if (n == 0 || n == 1)  
3.  return 1LL;  
4. else  
5.  return fibonacci(n - 1) + fibonacci(n - 2);  
6. }  

long long fibonacci(int n) {
if (n == 0 || n == 1)
 return 1LL;
else
 return fibonacci(n - 1) + fibonacci(n - 2);
}

んー、まあ定義に忠実に実装すれば簡単です。

ではここで、以下のコードを実行してみましょう。

view plainprint?

1. #define forf(i, n) for(int i=0; i<(int)(n); i++)  
2.   
3. int main() {  
4.  forf(i, 50)  
5.   cout << i << "," << fibonacci(i) << endl;  
6.  return 0;  
7. }  

#define forf(i, n) for(int i=0; i<(int)(n); i++)

int main() {
 forf(i, 50)
  cout << i << "," << fibonacci(i) << endl;
 return 0;
}

どうです？？

面白い結果がえられると思います。

私のマシンでは上記処理が終了するまで、543秒かかりました。10分くらいかかっちゃうんですね。。
上記のやり方だと、O(2^n)になっちゃってるんですね。。

では、ちょっとやり方を変えてみましょう。

view plainprint?

1. long long fibonacci2(int n) {  
2.  long long ret = 0;  
3.  long long x0 = 1LL;  
4.  long long x1 = 0;  
5.   
6.  forf (i, n) {  
7.   ret = x0 + x1;  
8.   x1 = x0;  
9.   x0 = ret;  
10.  }  
11.  return ret;  
12. }  

long long fibonacci2(int n) {
 long long ret = 0;
 long long x0 = 1LL;
 long long x1 = 0;

 forf (i, n) {
  ret = x0 + x1;
  x1 = x0;
  x0 = ret;
 }
 return ret;
}

どうでしょう？どうやら多項式時間で実行できそうですね。私のマシン上で先ほどと同じことをやると0.001秒で済んじゃいました。。

これが、所謂、動的計画法（Dynamic Programming）、通称DPと言われるものです。
ボトムアップ的に必要な情報を積み上げて行って解を出力しています。一方、再帰を使ったものの場合は、トップダウン的な解法になっています。
しかし、これはまだまだ序の口です。
フィボナッチ数列の場合は、初めから何も考えずにDPで解く人が多いと思いますし、パッと見、多項式時間で解けそうな感じがします。
次回は、普通に解くとO(2^n)である問題に対して、少しトリッキーな方法でDPを適用し多項式時間で解く方法を紹介します。