フィボナッチ数列
この演習では、自然界でも広く見られるフィボナッチ数列を実装します。数列は「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))