フィボナッチ数列
この演習では、自然界に広く見られるフィボナッチ数列を作成します。数列は「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変数に保存することで、処理を効率化します。
この演習はコースの一部です
Pythonで学ぶデータ構造とアルゴリズム
実践的なインタラクティブ演習
このサンプルコードを完成させて、この演習に挑戦してみましょう。
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))