埋めたセル
足し算の回数
表なしの呼び出し回数

  • 記入中
  • 参照元
  • 答え

動的計画法によるフィボナッチ数の計算をもっと詳しく

動的計画法でフィボナッチ数

フィボナッチ数は、動的計画法の最初の例として定番です。単純な再帰は同じ項を何度も求めますが、各項を覚えておく表があれば、手間は n に比例して増えるだけです。項を選び、ボトムアップかトップダウンを選んで1ステップずつ進めると、どのセルも1回だけ埋まる様子がわかります。 「再生」で表が埋まっていく様子を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。求める項 n と方法を選びます。ボトムアップは表を左から埋めていきます。トップダウンは再帰をそのまま使いますが、まず表を確認します。このとき表の下の列は、まだ終わっていない呼び出しのスタックです。「新しい例」で別の n を選びます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. 「第 n 項」に求める項 n を入力し、ボトムアップかトップダウンを選びます。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。
  3. 各セルが直前の2つのセルを読む様子を見てください。トップダウンでは、表の下の列がまだ終わっていない呼び出しのスタックです。

ボトムアップとトップダウン

ボトムアップ(表を使う方法、tabulation)は、F(0) = 0 と F(1) = 1 から始めて、表を左から右へ埋めます。新しいセルはそれぞれ、直前の2つのセルの和です。トップダウン(メモ化)は、再帰による定義をそのまま使います。F(n) を求めるには、F(n − 1) と F(n − 2) を求めます。単純な再帰との違いは、どの呼び出しもまず表を確認し、セルがまだ空のときだけ項を計算することです。どちらの方法も各セルを1回ずつ埋め、足し算は n − 1 回です。

単純な再帰はなぜこんなに遅いのか

表がないと、F(n) は F(n − 1) と F(n − 2) を呼び出し、その両方が F(n − 3) を呼び出し、という具合に続きます。呼び出しは木の形になり、同じ項が何度も現れます。呼び出し回数は 2·F(n + 1) − 1 で、フィボナッチ数そのものと同じ速さで増えます。F(10) で 177 回、F(20) で 21,891 回、F(40) では3億3100万回を超えます。このように部分問題が重なり合う場面こそ、動的計画法の出番です。

よくある質問

動的計画法とは何ですか?

問題を互いに重なり合う小さな問題に分け、小さな問題をそれぞれ1回だけ解いて、その答えを表に保存しておく解き方です。フィボナッチ数はいちばん簡単な例で、どの項も直前の2つの項から作られます。

メモ化と表を使う方法(tabulation)の違いは?

メモ化は再帰のコードをそのまま使い、答えを初めて計算したときに保存しておくので、あとの呼び出しはそれを読むだけです。表を使う方法は、各セルに必要な答えが必ずそろっている順番で表を埋めます。どちらも足し算は同じです。表を使う方法はコールスタックを使わずに済み、メモ化は本当に必要なセルだけを計算します。

F(n) には足し算が何回必要ですか?

表を使えば n − 1 回です。F(2) から F(n) までの各項に1回ずつです。読むのは常に最後の2項だけなので、プログラムは表全体の代わりに2つの数だけを持っておくこともできます。

なぜ n = 40 までなのですか?

F(40) = 102,334,155 はまだ画面に楽に収まり、単純な再帰ではこれを求めるのにすでに 331,160,281 回の呼び出しが必要です。これより大きい項は急速に大きくなります。JavaScript の数値で正確に表せる最大の項は F(78) です。

データはどこかに送信されますか?

いいえ。計算はすべてブラウザー内で行われ、最後の設定はこのブラウザーのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ