Fibonacci Number
フィボナッチ数は F(0) = 0 と F(1) = 1 から始まり、それ以降の各数はその前の2つの数の和です。F(n) = F(n-1) + F(n-2)。数列は 0, 1, 1, 2, 3, 5, 8, 13 で始まります。関数は n を受け取り、F(n) を返します。
関数
- ninteger
- 0から数えたフィボナッチ数列での位置
- 戻り値integer
- フィボナッチ数 F(n)
制約
0 ≤ n ≤ 45- 答えは符号付き32ビット整数に収まります:
F(45) = 1134903170.
例
- 入力
- n = 4
- 出力
- 3
- 説明
- 開始から数え上げます：
F(2) = 1 + 0 = 1、F(3) = 1 + 1 = 2、そしてF(4) = 2 + 1 = 3です。
- 入力
- n = 10
- 出力
- 55
- 説明
- インデックス 0 から始まる数列は、0、1、1、2、3、5、8、13、21、34、55 です。インデックス 10 の数は
34 + 21 = 55です。
提出時に隠しテスト+13件
発展問題
F(n) を O(log n) 時間で計算できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
再帰的定義を使って、手作業で
F(5)を計算しましょう。どの値を複数回計算することになりますか？各フィボナッチ数に必要なのは、その直前の2つの数だけです。小さい順に計算すれば、必要な値は使うときにはすでにわかっています。
0と1から始めます。n-1回繰り返します。手元にある2つの数を足し、その後、古い方を捨てて合計を残します。
解説
定義自体はすでに再帰関数であり、そのまま関数として書けば正しい答えが得られます。落とし穴は実行時間です。2つの再帰呼び出しは互いの計算をやり直すため、呼び出し回数はnに対して指数関数的に増加します。動的計画法では、フィボナッチ数をそれぞれ一度だけ、ボトムアップで計算することでこれを解決します。最後のステップでは、次の数に必要な2つの数だけを保持します。
定義からそのまま再帰へ
正しいが、最大のテストでは終わらない
考え方
定義を一語一語そのまま翻訳します。fib(0) は 0、fib(1) は 1 で、それより大きい値はすべて fib(n-1) + fib(n-2) を返します。呼び出しの連鎖はすべて、2つの基本ケースのどちらかで終わるので、答えは正しいです。
では、呼び出し回数を数えてみましょう。fib(5) は fib(4) と fib(3) を呼び出しますが、fib(4) も再び fib(3) を呼び出します。最終的に、fib(3) は2回、fib(2) は3回、fib(1) は5回実行され、fib(5) は合計15回呼び出されます。同じ値が何度も再計算されます。
呼び出し回数はフィボナッチ数そのものに従います。F(n) の計算では、2 × F(n+1) - 1 回呼び出されます。n = 45 の場合、呼び出し回数は約 3.7 × 10^9 回となり、制限時間内に処理するには多すぎます。この上限は通常 O(2^n) と表記されます。正確な増加率は約 1.618^n です。再帰の深さはわずか n レベルなので、スタックに必要な領域は O(n) です。
アルゴリズム
nが0または1の場合は、nを返します。- それ以外の場合は、
n-1とn-2に対して関数を呼び出します。 - 2つの結果の合計を返します。
def fib(n):
if n < 2:
return n # F(0) = 0, F(1) = 1
return fib(n - 1) + fib(n - 2)表を下から上に埋める
考え方
再帰が遅いのは、結果を忘れてしまうからです。各フィボナッチ数を初めて計算したときに書き留めておけば、それぞれに必要なのは1回の加算だけです。インデックス0からnまでの要素を持つ表fを作り、f[0] = 0とf[1] = 1を設定して、残りを左から右へf[i] = f[i-1] + f[i-2]で埋めます。
左から右へ進めることが、この方法を機能させる鍵です。f[i]に到達したとき、必要な2つの数値はすでに表に入っています。n = 10の場合、表は0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55と埋まり、答えは最後の要素です。
これは最も基本的な形の動的計画法で、漸化式と、より小さなケースの答えを格納する表から成ります。加算はn-1回で、計算時間はO(n)です。また、表にはn + 1個の数値が入り、空間計算量はO(n)です。n = 45でも、何十億回もの呼び出しの代わりに、44回の加算で済みます。
アルゴリズム
nが0または1の場合は、nを返します。f[0] = 0とf[1] = 1を格納する、n + 1個の数値のテーブルを作成します。iを 2 からnまで増やしながら、f[i] = f[i-1] + f[i-2]を設定します。f[n]を返します。
def fib(n):
if n < 2:
return n
f = [0] * (n + 1) # f[i] will hold F(i)
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]最後の2つの数だけを残す
考え方
テーブルを使うループが何を読み取るか見てみましょう。f[i]を埋めるにはf[i-1]とf[i-2]だけが必要で、それより前の値は必要ありません。つまり、それ以前の要素はすべて無駄です。テーブルの代わりに2つの変数を使います。prevには2つ前の数値を、currには1つ前の数値を保持します。
prev = 0とcurr = 1から始めます。これはそれぞれF(0)とF(1)です。各ステップでnext = prev + currを計算し、次にペアを前へ進めます。古いcurrをprevに、nextをcurrに代入します。n = 4の場合、ペアは(0, 1)から(1, 1)、(1, 2)、(2, 3)へと移り、curr = 3が答えになります。
処理は同じn-1回の加算で、時間計算量はO(n)、メモリには整数を3つ使うため、空間計算量はO(1)です。更新の順序が重要です。加算する前にprevを上書きすると、誤った値を使って合計してしまいます。
アルゴリズム
nが0または1の場合は、nを返します。prev = 0とcurr = 1を設定します。n-1回繰り返します。next = prev + currを計算し、次にprev = currとcurr = nextを設定します。currを返します。
def fib(n):
if n < 2:
return n
prev, curr = 0, 1 # F(0) and F(1)
for _ in range(n - 1):
prev, curr = curr, prev + curr
return curr
落とし穴と境界ケース
フィボナッチ数列は動的計画法の古典的な最初の問題で、バグの多くは再帰処理か最初の2つの値に起因します。
- 素朴な再帰処理を提出してしまう。小さなテストには通りますが、
n = 45では何十億回もの呼び出しが必要になります。結果をテーブルまたは2つの変数に保存しましょう。 - 初期値を間違える。ここでは
F(0) = 0、F(1) = 1なので、F(2) = 1、F(10) = 55です。数列を1、1から始めると、すべての答えがインデックス1つ分ずれます。 nが小さい場合のチェックをせずにテーブルを作る。n = 0の場合、サイズn + 1 = 1のテーブルにはf[1]を格納する場所がなく、そこに書き込むと範囲外になります。n < 2の場合は、すぐにnを返しましょう。- ペアを間違った順序で更新する。
prev = currの後にcurr = prev + currを実行すると、新しいprevを足してcurrが2倍になります。まず合計をnextに計算するか、言語に同時代入がある場合はそれを使いましょう。 - 1ステップ余計に実行する。
F(n+1)も計算するループでは、上限でF(46) = 1836311903に達しますが、これは32ビットに収まるのは運がよい場合だけです。F(47)は収まりません。
よくある質問4
再帰的なフィボナッチ関数の時間計算量はどれくらいですか？
素朴な再帰では2 × F(n+1) - 1回の呼び出しが行われます。この回数は1.618^nのように増加し、通常はO(2^n)と表記されます。n = 45の場合、呼び出し回数は約3.7 × 10^9回です。各結果をテーブルまたは2つの変数に一度だけ保存すれば、計算量はO(n)まで減少します。
動的計画法でフィボナッチ数列をどのように解きますか？
漸化式 F(n) = F(n-1) + F(n-2) から始めて、n の値が小さい順に値を計算し、それぞれを保存します。表を下から順に埋める方法も、再帰関数をそのまま使って結果をキャッシュする方法もあります。後者はメモ化と呼ばれます。どちらの方法でも各値は一度だけ計算されるため、全体の計算量は O(n) です。
フィボナッチ数はO(1)の空間計算量で計算できますか？
はい。各数値はその直前の2つの数値だけに依存するので、変数は2つあれば十分です。最後の2つの値を保持し、各ステップで順に更新します。これにより、時間計算量はO(n)、追加の空間計算量はO(1)になります。
O(n)より速い方法はありますか？
はい。[[1, 1], [1, 0]]をn乗した行列の右上の要素はF(n)であり、繰り返し二乗法を使うと、行列の乗算O(log n)回でその累乗を計算できます。黄金比の累乗を使った閉形式の公式もありますが、浮動小数点数で計算するため、nが大きくなるにつれて精度が失われます。そのため、整数を使う方法が推奨されます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def fib(n):
# ここにコードを書いてくださいケース1
ケース2
入力
n = 4
期待値
3