1. เรียนรู้
    2. /
  2. Courses
    3. /
  3. Pythonで学ぶデータ構造とアルゴリズム
Connected

Exercises

フィボナッチ数列

この演習では、自然界でも広く見られるフィボナッチ数列を実装します。数列は「0, 1, 1, 2, 3, 5, 8…」のように続きます。数列を生成するアルゴリズムを再帰で実装していきます。

最初の2つの数は 0 と 1 で、その後は直前の2つの数の和になります。

この数列は次のように再帰的に定義できます：$fib(n)=fib(n-1)+fib(n-2)$、ただし $fib(0)=0$、$fib(1)=1$。ここで \(n\) は数列の \(n\) 番目の位置を表します。

最初のステップでは、再帰を使ってフィボナッチを実装します。次のステップでは、動的計画法を用いて改良し、部分問題の解を cache 変数に保存します。

คำแนะนำ 1 / 2

undefined XP
  • 1
    • 基本ケースを定義します。
    • fibonacci() 関数を再帰的に呼び出します。
  • 2
    • cache に値が存在するかを確認します。
    • 後で再計算しないように、結果を cache に保存します。