定義を直接実装したプログラム
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/02 16:40 UTC 版)
「動的計画法」の記事における「定義を直接実装したプログラム」の解説
定義に基づいてプログラムを作成すると、次のようになる。 int fib(unsigned int n) { switch (n) { case 0: return 0; case 1: return 1; default: return fib(n - 1) + fib(n - 2); }} 例えば、このプログラムを使ってフィボナッチ数列の第5項を求める場合を考えてみる。このプログラムは再帰的に呼び出されるので、その様子を以下に示す。 fib(5) = fib(4) + fib(3) = (fib(3) + fib(2)) + (fib(2) + fib(1)) = ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) = (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1)) このように最終的に fib(0) と fib(1) の呼び出しに収束し、fib(0) と fib(1) の呼び出し回数の和が結果の値となる。この方法を用いたフィボナッチ数列の計算量は O ( 2 n ) {\displaystyle O(2^{n})} の指数関数時間となる。
※この「定義を直接実装したプログラム」の解説は、「動的計画法」の解説の一部です。
「定義を直接実装したプログラム」を含む「動的計画法」の記事については、「動的計画法」の概要を参照ください。
- 定義を直接実装したプログラムのページへのリンク
