フィボナッチ数は、次の各数値が前の 2 つの数値の合計に等しい一連の数値です: 1、1、2、3、5、8、13、...。 場合によっては、シリーズが 0、1、1、2、3、5、... というようにゼロから始まることがあります。 で この場合最初のオプションに固執します。

式：

F 1 = 1
F 2 = 1
Fn = Fn-1 + Fn-2

計算例：

F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...

while ループを使用してフィボナッチ数列の n 番目の数を計算する

1. 変数 fib1 と fib2 に系列の最初の 2 つの要素の値を割り当てます。つまり、変数に 1 を割り当てます。
2. 値を取得したい要素の番号をユーザーに要求します。 変数 n に数値を代入します。
3. 満たす 次のステップ最初の 2 つの要素がすでに考慮されているため、n - 2 回になります。
   1. fib1 と fib2 を追加し、結果を一時記憶変数 (例: fib_sum ) に割り当てます。
   2. 変数 fib1 を fib2 に設定します。
   3. fib2 変数に値 fib_sum を割り当てます。
4. fib2 の値を表示します。

注記。ユーザーが 1 または 2 を入力すると、ループの本体は実行されず、fib2 の元の値が画面に表示されます。

fib1 = 1 fib2 = 1 n = input() n = int(n) i = 0 while i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

コードのコンパクト版:

fib1 = fib2 = 1 n = int (入力( 「フィボナッチ数列要素番号:」) ) - 2、n > 0 の場合: fib1、fib2 = fib2、fib1 + fib2 n -= 1 print (fib2)

for ループを使用してフィボナッチ数を出力する

この場合、フィボナッチ数列の目的の要素の値だけでなく、それまでのすべての数値も表示されます。 これを行うには、fib2 値の出力をループに配置します。

fib1 = fib2 = 1 n = int (input () ) if n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

実行例:

10 1 1 2 3 5 8 13 21 34 55

フィボナッチ数列の n 番目の数を再帰的に計算する

1. n = 1 または n = 2 の場合、フィボナッチ数列の最初と 2 番目の要素は 1 に等しいため、呼び出し側ブランチに 1 を返します。
2. それ以外の場合は、引数 n - 1 および n - 2 を使用して同じ関数を呼び出します。2 つの呼び出しの結果を加算し、呼び出し側プログラム ブランチに返します。

def fibonacci(n) : (1 , 2 ) に n の場合: 1 を返す return fibonacci(n - 1 ) + fibonacci(n - 2 ) print (fibonacci(10 ) )

n = 4 としましょう。その後、fibonacci(3) と fibonacci(2) への再帰呼び出しが行われます。 2 番目の関数は 1 を返し、最初の関数はさらに 2 つの関数呼び出し fibonacci(2) と fibonacci(1) を返します。 どちらの呼び出しでも 1 つが返され、合計 2 つになります。 したがって、fibonacci(3) への呼び出しは数値 2 を返し、これは fibonacci(2) への呼び出しによる数値 1 と合計されます。 結果 3 はプログラムのメイン ブランチに返されます。 フィボナッチ数列の 4 番目の要素は 3 に等しくなります: 1 1 2 3。

プログラマーはもうフィボナッチ数にはうんざりしているはずです。 彼らの計算例が全体を通して使用されています。 すべてはこれらの数字が何を提供するかによって決まります 最も単純な例再帰。 これらは動的プログラミングの良い例でもあります。 しかし、実際のプロジェクトでこのように計算する必要があるでしょうか? 必要なし。 再帰も動的プログラミングも理想的なオプションではありません。 浮動小数点数を使用した閉じた数式ではありません。 次に、それを正しく行う方法を説明します。 まずは、既知の解決策のオプションをすべて見てみましょう。

このコードは Python 3 を対象としていますが、Python 2 でも動作するはずです。

まず、定義を思い出させてください。

Fn = Fn-1 + Fn-2

そして、F 1 = F 2 =1です。

クローズドフォーミュラ

詳細は省略しますが、興味のある方は公式の導出についてよく理解してください。 アイデアは、F n = x n となる x があると仮定して、x を見つけることです。

それはどういう意味ですか

x n-2 を削減します

二次方程式を解くと次のようになります。

ここで「黄金比」ϕ=(1+√5)/2が大きくなります。 元の値を代入してさらに計算を行うと、次の結果が得られます。

これを Fn の計算に使用します。

__future__ から import Division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)

良い：
小規模な n の場合は迅速かつ簡単
悪い点:
浮動小数点演算が必要です。 n が大きいほど、より高い精度が必要になります。
悪：
複素数を使用して F n を計算することは、数学的な観点からは美しいですが、コンピューターの観点からは醜いものです。

再帰

最も明白な解決策は、おそらく再帰とは何かを示す例として、これまでに何度も見たものです。 完全を期すためにもう一度繰り返します。 Python では次のように 1 行で記述できます。

Fib = ラムダ n: fib(n - 1) + fib(n - 2) if n > 2 else 1

良い：
数学的定義に従った非常に単純な実装
悪い点:
指数関数的な実行時間。 n が大きい場合は非常に遅くなります
悪：
スタックオーバーフロー

暗記

再帰ソリューションには、計算の重複という大きな問題があります。 fib(n) が呼び出されると、fib(n-1) と fib(n-2) がカウントされます。 ただし、fib(n-1) がカウントされると、fib(n-2) も独立してカウントされます。つまり、fib(n-2) は 2 回カウントされます。 引数を続けると、fib(n-3) が 3 回カウントされることがわかります。 交差点が多すぎます。

したがって、再度カウントしないように結果を覚えておく必要があります。 このソリューションは時間とメモリを無駄にします 直線的に。 ソリューションでは辞書を使用していますが、単純な配列も使用できます。

M = (0: 0, 1: 1) def fib(n): M に n の場合: M[n] を返す M[n] = fib(n - 1) + fib(n - 2) M[n] を返す

(Python では、これはデコレータ functools.lru_cache を使用して行うこともできます。)

良い：
再帰をメモリ ソリューションに変えるだけです。 指数関数的な実行時間を線形実行に変換すると、より多くのメモリが消費されます。
悪い点:
大量のメモリを浪費する
悪：
再帰と同様にスタック オーバーフローの可能性

動的プログラミング

暗記して解いた後は、前の結果をすべて必要とするのではなく、最後の 2 つの結果だけが必要であることがわかります。 また、fib(n) から開始して後戻りする代わりに、fib(0) から開始して前に進むこともできます。 次のコードの実行時間は直線的で、メモリ使用量は固定されています。 実際には、再帰的な関数呼び出しや関連する作業がないため、解決速度はさらに速くなります。 そして、コードはよりシンプルに見えます。

このソリューションは、動的プログラミングの例としてよく引用されます。

Def fib(n): a = 0 b = 1 for __ in range(n): a、b = b、a + b return a

良い：
小さい n の単純なコードでは高速に動作します
悪い点:
まだリニアな実行時間
悪：
特別なことは何もありません。

行列代数

そして最後に、照明は最も少ないですが、最も明るいのは、 正しい決断、時間と記憶の両方を賢く使います。 また、任意の同種の線形シーケンスに拡張することもできます。 アイデアは行列を使用することです。 それを見るだけで十分です

そしてこれを一般化すると次のようになります

先ほど取得した x の 2 つの値 (そのうちの 1 つは黄金比) が行列の固有値です。 したがって、閉じた式を導出する別の方法は、行列方程式と線形代数を使用することです。

では、なぜこの定式化が役立つのでしょうか? 累乗は対数時間で実行できるためです。 これは二乗によって行われます。 ポイントは、

最初の式は偶数 A に使用され、2 番目の式は奇数に使用されます。 残っているのは行列の乗算を整理することだけで、準備はすべて完了です。 これにより、次のコードが生成されます。 理解しやすいため、pow の再帰実装を作成しました。 反復バージョンについては、こちらをご覧ください。

Def pow(x, n, I, mult): """ x の n 乗を返します。I が mult で乗算される単位行列であり、n が正の整数であると仮定します。n == 0 の場合、I を返します。 elif n == 1: x を返す else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) y を返す defidentity_matrix (n): """n × n 単位行列を返します""" r = list(range(n)) return [for j in r] def matrix_multiply(A, B): BT = list(zip(*B) ) return [for row_a in A] def fib(n): F = pow([, ], n,identity_matrix(2), matrix_multiply) return F

良い：
固定メモリサイズ、対数時間
悪い点:
コードはさらに複雑です
悪：
行列はそれほど悪くありませんが、行列を扱う必要があります。

性能比較

動的計画法と行列の変形のみを比較する価値があります。 これらを n 番目の文字数で比較すると、行列解は線形であり、動的計画法による解は指数関数的であることがわかります。 実際の例は、20 万桁を超える数である fib(10 ** 6) を計算することです。

N=10**6
fib_matrix の計算: fib(n) には 208988 桁しかなく、計算には 0.24993 秒かかりました。
fib_dynamic: fib(n) の計算には 208988 桁しかなく、計算には 11.83377 秒かかりました。

理論上のメモ

上記のコードとは直接関係はありませんが、この発言は依然として興味深いものです。 次のグラフを考えてみましょう。

A から B までの長さ n のパスの数を数えてみましょう。たとえば、n = 1 の場合、パス 1 が 1 つあります。n = 2 の場合、パス 01 が 1 つあります。n = 3 の場合、パス 001 が 2 つあります。および 101 A から B までの長さ n のパスの数が F n に正確に等しいことを非常に簡単に示すことができます。 グラフの隣接行列を書き留めると、上で説明したものと同じ行列が得られます。 グラフ理論のよく知られた結果として、隣接行列 A が与えられた場合、A n の出現箇所はグラフ内の長さ n のパスの数になります (映画『グッド ウィル ハンティング』で言及された問題の 1 つ)。

なぜ肋骨にこのような模様があるのでしょうか？ グラフ上の往復の無限のパス上の無限のシンボルのシーケンスを考慮すると、記号力学システムの一種である「有限型サブシフト」と呼ばれるものが得られることがわかります。 有限タイプのこの特定のサブシフトは「黄金比シフト」として知られており、一連の「禁止語」(11) によって指定されます。 言い換えれば、両方向に無限のバイナリ シーケンスが得られ、それらのペアは隣接しません。 この力学系の位相エントロピーは黄金比 ϕ に等しい。 この数字が数学のさまざまな分野で定期的に現れるのは興味深いことです。

さまざまなオリンピックで、一見すると単純な力技で解決できると思われるこのような問題に遭遇することがよくあります。 でも数を数えてみると 可能なオプション、その後、このアプローチの非効率性をすぐに確信するでしょう。たとえば、以下に示す単純な再帰関数は、フィボナッチ数の 30 番目ですでにかなりのリソースを消費しますが、オリンピックでは、解法時間は多くの場合 1 ～ 5 秒に制限されます。

Int fibo(int n) ( if (n == 1 || n == 2) ( return 1; ) else ( return fibo(n - 1) + fibo(n - 2); ) )

なぜこのようなことが起こるのか考えてみましょう。 たとえば、fibo(30) を計算するには、まず fibo(29) と fibo(28) を計算します。 しかし同時に、私たちのプログラムは fibo(28) を「忘れて」しまいます。 すでに計算済み fibo(29) を検索するとき。

この正面からのアプローチの主な間違いは、関数の引数の同じ値が何度も計算されることです。これらは非常にリソースを大量に消費する操作です。 動的プログラミング手法は、繰り返しの計算を取り除くのに役立ちます。これは、問題を一般的な反復可能なサブタスクに分割し、それぞれを 1 回だけ解決する手法です。これにより、プログラムの効率が大幅に向上します。 この方法については、他の問題を解決する例も含めて詳しく説明されています。

関数を改善する最も簡単な方法は、すでに計算した値を覚えておくことです。 これを行うには、計算の「キャッシュ」として機能する追加の配列を導入する必要があります。新しい値を計算する前に、それが以前に計算されたことがないかどうかを確認します。 計算した場合は、配列から完成した値を取得します。計算しなかった場合は、以前の値に基づいて計算し、将来のために覚えておく必要があります。

内部キャッシュ。 int fibo(int n) ( if (cache[n] == 0) (if (n == 1 || n == 2) (cache[n] = 1; ) else (cache[n] = fibo(n) - 1) + fibo(n - 2) ) キャッシュ[n]を返します。

この問題では、N 番目の値を計算するには (N-1) 番目の値が必要であることが保証されているため、式を反復形式で書き直すことは難しくありません。目的の値に達するまで配列を連続して埋めるだけです。細胞：

<= n; i++) { cache[i] = cache + cache; } cout << cache;

ここで、 F(N) の値を計算すると、 F(N-3) の値がすでに保証されていることがわかります。 一度もない必要なくなるよ。 つまり、F(N-1) と F(N-2) という 2 つの値をメモリに保存するだけで済みます。 さらに、F(N) を計算するとすぐに、F(N-2) を保存することはまったく意味を失います。 これらの考えをコードの形で書き留めてみましょう。

// 前の 2 つの値: int queue1 = 1; int キャッシュ 2 = 1; //新しい値 int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>反復後、cache2 は関連性を失います。つまり、 //つまり、cache1 -- f(n-2)、cache2 -- f(n-1)、cache3 -- f(n) になるはずです。<< cache3;

// N=n+1 (次の反復で計算する数値) とします。 すると、n-2=N-3、n-1=N-2、n=N-1となります。

//新しい現実に従って、変数の値を書き換えます。<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

キャッシュ2 = キャッシュ3; ) コウト

経験豊富なプログラマーであれば、cache3 は決して使用されず (すぐに cache2 に書き込まれる)、反復全体を 1 つの式だけで書き換えることができるため、一般に上記のコードがナンセンスであることが理解できるでしょう。< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

キャッシュ = 1; キャッシュ = 1; for (int i = 2; i

剰余を使った魔法がどのように機能するのか理解できない人、または単にもっと分かりにくい公式を見たい人のために、別の解決策があります。

Int x = 1; int y = 1; for (int i = 2; i

このプログラムの実行を監視してみてください。アルゴリズムの正しさを確信できるでしょう。