010: 「フィボナッチの四重奏」のヒント

問題 / 解答

難易度: ☆

ヒント1

再帰式は定義としては自然ですが、そのまま関数呼び出しにすると同じ値を何度も計算します。 T(100) では、その重複が大きくなります。

ヒント2

T(0) から順にリストへ入れていくと、各項を一度だけ計算できます。 T(k) を作るときには、すでに T(k - 1)、T(k - 2)、T(k - 3)、T(k - 4) がリストに入っています。

ヒント3

リスト全体を持たなくても、直前4項だけを変数で持てば計算できます。 最初に 0, 0, 0, 1 を持ち、1項進むたびに古い値を捨てます。

ヒント4

まずはリストを使う実装で正しく動かしてください。 そのあと、発展として直前4項だけを持つ実装に書き換えます。