Python 言語のフィボナッチ数

フィボナッチ数は、最初の値が 0 として事前に宣言され、2 番目の値が 1 として事前に宣言されている特定のシーケンスです。すべてのフィボナッチ数は、0 から始まる正の整数です。最初の 12 のフィボナッチ数とその取得方法は次のとおりです。

0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89

合計式がなければ、これらのフィボナッチ数は次のようにテーブルに入れることができます。

最初の行にはフィボナッチ数があります。 2 番目の行には、フィボナッチ数が配列内にあると仮定して、0 から始まるインデックスがあります。

フィボナッチ数は、O(n) 時間と O(1) 時間で生成できます。これらの時間計算量の式では、n は n 個の主な操作を意味し、1 は 1 つの主な操作を意味します。 O(n) では、0 から始まる n 個のフィボナッチ数が生成されます。O(1) では、対応するインデックスから 1 つのフィボナッチ数が生成されます。そのため、n 回のメイン操作ではなく、1 回のメイン操作しか必要としません。

この記事の目的は、Python を使用していずれかの方法でフィボナッチ数を生成する方法を説明することです。

フィボナッチ数の公式

フィボナッチ数の正式な定義は次のとおりです。

ここで F _n ゼロベースの n

O(n) 時間でフィボナッチ数を生成する

n が 1 の場合、0 のみがフィボナッチ数として出力されます。 n が 2 の場合、0 と 1 がフィボナッチ数としてこの順序で出力されます。 n が 3 の場合、0、1、1 がフィボナッチ数としてこの順序で出力されます。 n が 4 の場合、0、1、1、および 2 がフィボナッチ数としてこの順序で出力されます。 n が 5 の場合、0、1、1、2、および 3 がフィボナッチ数としてこの順序で出力されます。 n が 6 の場合、0、1、1、2、3、および 5 がこの順序でフィボナッチ数として出力されます。

最初の n 個のフィボナッチ数を生成する Python 関数は次のとおりです。

まず、すべてゼロに初期化された n 要素の配列を作成します。この配列はフィボナッチ数を保持します。最初のフィボナッチ数 0 はすでにそこにあります。 2 番目のフィボナッチ数 1 は、(関数内の) 次のステートメントによって割り当てられます。次に、インデックス 2 から n の直前までの for ループがあります。次のステートメントがあります。

これにより、直前の 2 つの数値が加算されます。

関数を呼び出して最初の 12 個のフィボナッチ数を出力するコードは次のようになります。

N = 12
A = フィボナッチ(N)
for i in range(N):
印刷 (A[i], end='')
印刷()

出力は次のとおりです。

一定時間で 1 つのフィボナッチ数を生成する

ゼロベースのインデックスを対応するフィボナッチ数に関連付ける数式があります。式は次のとおりです。

式の右辺では、5 の平方根を n 乗したものではないことに注意してください。 n 乗されるのは、括弧内の式です。このような表現が 2 つあります。

n が 0 の場合、Fibn は 0 になります。n が 1 の場合、Fib _n n が 2 の場合、Fib _n n が 3 の場合、Fib _n n が 4 の場合、Fib _n 3 などです。読者は、n に異なる値を代入して評価することにより、この式を数学的に検証できます。 n は、この式の 0 から始まるインデックスです。

この数式の Python コードは次のとおりです。

インポート数学

数学モジュールがインポートされました。平方根機能があります。演算子 ** はべき乗に使用されます。関数 fibNo() は式を直接実装します。 fibNo() 関数の適切な呼び出しと出力は次のとおりです。

N = 11
右 = fibNo(N)
印刷(再)

出力は次のとおりです。

回答から不要な小数桁を削除することができます。ただし、それは別の機会に議論します。

n 個のインデックスごとに異なるフィボナッチ数が必要な場合は、n 個のインデックスごとに関数 fibNo() を 1 回呼び出して、対応する異なるフィボナッチ数を返す必要があります。次のプログラムは、ゼロベースのインデックス 7 から 9 (両端を含む) に対してこれを行います。

インポート数学

出力は次のとおりです。

Python での for ループのコーディング方法に注意してください。最初のインデックスは 7 です。次のインデックスは 8 で、最後のインデックスは 9 です。range 引数の 10 は 9 + 1 です。10 の位置の値は、最後のゼロベースのインデックスに 1 を加えたものでなければなりません。引数 7 は、ゼロベースの開始インデックスです。

結論

フィボナッチ数は、整数 (正の整数) の特定のシーケンスです。 0 から始まり、無条件に 1 が続きます。残りの数は、直前の 2 つの数を追加することによってそこから展開されます。

最初の n 個のフィボナッチ数を取得するには、0 と 1 を最初の 2 つとして受け入れ、残りについては、次のようなステートメントで for ループを使用します。

直前の 2 つの数値を加算します。

ゼロ ベースのインデックス n から 1 つのフィボナッチ数を取得するには、次の式を使用します。