といた こたえを また つかう

同じものを また とく

さいきは 大きな もんだいを
小さな もんだいに わって ときます。
フィボナッチが まさに それです。
fib(5)は fib(4)と fib(3)を、
fib(4)は また fib(3)と fib(2)を よびます。
でも よく 見ると、
fib(2)が この えだ あの えだで
何ども また でてきます。
下の 木で
ノードを 一つ おしてみましょう。

同じ 小さな もんだいが 木の あちこちに また でます。(ノード クリック → 同じ値 ぜんぶ きょうちょう)

見えますね。
同じ fib(2)を
一かいでなく 何かいも ときます。
fib(3)も 同じです。
nが 大きく なると
この じゅうふくは すごく ふえます。
もう といてある こたえを
また ときなおすのは
だれが 見ても もったいないです。

こたえを かいておく

かいけつは いがいと かんたんです。
といた こたえを
メモに かいておくのです。
つぎに 同じものが また 必要なら、
けいさんしなおさず
メモから ただ とりだして つかいます。
はじめてのものだけ けいさんし、
見たことが あるのは とりだせば いいです。
ボタンを おして
よびだしを 一つずつ しょりしましょう。

はじめては けいさんして かき、見たことが あるのは メモから とりだします。(これが メモか)

けいさんは さいしょの 一かいだけです。
あとは ぜんぶ
メモから とりだして つかうので、
同じものを 二ど とく ことが
すっかり なくなります。
こうして といた こたえを
かいておいて また つかうのを
メモか と いいます。
名まえは りっぱでも
なかみは「かいておく」です。

下から 表を うめる

同じ かんがえを
ぎゃくに する ことも できます。
上から わって おりる かわりに、
いちばん下の 小さな 値から
表を うめて 上へ いくのです。
fib(0)と fib(1)は そのまま わかります。
その 二つを たして fib(2)、
fib(1)と fib(2)を たして fib(3)。
下の マスが もう かいてあるので、
上の マスは たすだけで すみます。

0,1から 一マスずつ 上へ うめます。(つぎの マス = すぐ下の 二マスの 合計 · ボトムアップ)

この やり方は メモ さえ
必要 ありません。
表 じたいが メモ だからです。
下から 上へ
順に 一かい とおすだけで、
ときなおしが まったく ありません。
メモか が
「必要な とき かいておく」なら、
これは「さきに ぜんぶ かいておく」です。
どちらも なかみは 同じです。

ぐっと はやく なる

では どれだけ はやく なるのか。
かいておく 一手で
変わるものは とても 大きいです。
じゅんすい さいきは
じゅうふくまで ぜんぶ とくので、
nが 大きく なるほど
しごとが ばくはつ するように ふえます。
メモは かく マスを たった 一かいずつ、
nに ひれいする ぶんだけ ときます。
nを ふやしながら 二つを くらべましょう。

同じ nでの とく 回数。(じゅんすい さいき=しすうで ばくはつ · メモ=nに ひれいする せんけい)

ちがいが 見えますね。
nが すこし 大きく なるだけで
じゅんすい さいきの ぼうは
がめんを つきぬけそうに のびます。
メモの ぼうは
ほとんど そのままです。
同じ こたえを また とかない、
この 一つが
おそいと はやいを わけるのです。

まとめ

どうてき けいかくほうは
むずかしい 名まえですが
なかみは 三あしです。
同じものを また といていると 気づき、
といた こたえを かいておき、
また つかうから ぐっと はやく なる。
下の カードを 一つずつ おして
三あしを まとめましょう。

また とく → かいておく → ぐっと はやく。(ぶんかつ とうちは かさならず メモ ふようだった ことを かいしゅう)

前回の ぶんかつ とうちでは
わった かけらが かさならず
かいておく ものが ありませんでした。
そこが まさに わかれみちです。
かけらが かさなる とき、
つまり 同じ 小さな もんだいが
何ども また でてくる とき、
はじめて かいておく 一手が
すべてを 変えるのです。