スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




フィボナッチ数 Fibonacci Number

2008.02.26 16:06  動的計画法

Time-Space complexity など、動的計画法と再帰による手法の違いを表すよい例がイタリアの数学者フィボナッチによって定義されたフィボナッチ数(Fibonacci number)の生成です。n 番目のフィボナッチ数 Fn

Fn = Fn-1 + Fn-2

と定義されます。

これはフィボナッチがウサギの増殖をモデル化するために定義した数です。フィボナッチは、もし1年目に1つがいのウサギがいれば、n年目に生まれるウサギのつがいの数は、その1年前と2年前のウサギのつがいの和に等しいと推量しました。従ってフィボナッチ数列の最初の数項は F0 = 0, F1 = 1 とすれば
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
.
.
となります。この数列は、自然界の現象やアプリケーションにも数多く出現します。

フィボナッチ数列は再帰的な式で定義できるので、それを以下のように簡単な再帰的なプログラムとして記述することができます。



001 int fibonacci( int i ){
002 if ( i == 0 ) return 0;
003 if ( i == 1 ) return 1;
004 return fibonacci(i - 2) + fibonacci(i - 1);
005 }



しかし、単純な再帰によるプログラムの計算量は指数関数時間になってしまいます。例えば、フィボナッチ数列の第5項を再帰で求めると以下のようになります。

再帰によるフィボナッチ数の生成


このように、最終的にはF(n)の結果がF(0)とF(1)の呼び出し回数の和になってしまいます。


以下のように、動的計画法を用いればF(n)をO(n)の多項式時間の計算量で求めることができます。


001 int F[MAX];
002
003 void makeFibonacci(){
004 F[0] = 0;
005 F[1] = 1;
006 for ( int i = 2; i < MAX; i++ ){
007 F[i] = F[i-2] + F[i-1];
008 }
009 }




動的計画法では全ての数列の値をメモリに記憶します。このプログラムはフィボナッチ数を小さい方から生成し記録していくので、F(i)を計算するときにはF(i-1)とF(i-2)がすでに計算されているのでそれを有効利用することができます。このように、小さい問題の解をメモリに記憶することにより、指数関数時間を多項式時間に改善し、計算時間を飛躍的に減少させることができます。
スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。