フィボナッチ数の意味
フィボナッチ数は、0 から始まる正の整数の特定のシーケンスです。整数は正の整数です。したがって、フィボナッチ数は、0 から始まる整数または自然数の特定のシーケンスです。このシーケンスでは、最初の 2 つの数値は、この順序で 0 と 1 です。残りの数は、前の 2 つの数を加算することによってそこから展開されます。最初の 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
つまり、最初の 12 個のフィボナッチ数は次のとおりです。
0、1、1、2、3、5、8、13、21、34、55、89
もちろん、13 番目の数は 144 = 55 + 89 になります。フィボナッチ数は次のように配列にあると想像できます。
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 3.4 | 55 | 89 |
配列にはインデックスがあります。次の表の 2 行目は、配列内のフィボナッチ数に対応するゼロベースのインデックスを示しています。
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 3.4 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 十一 |
ゼロベースのインデックスでは、12 個の要素がある場合、最後のインデックスは 11 です。
フィボナッチ数は O(n) 時間または O(1) 時間で生成できます。これらの時間計算量の式では、n は n 個の主な操作を意味し、1 は 1 つの主な操作を意味します。 O(n) では、0 から始まる n 個のフィボナッチ数が生成されます。O(1) では、対応するインデックスから 1 つのフィボナッチ数が生成されます。そのため、O(1) は、n 回のメイン操作ではなく、1 回のメイン操作のみを実行します。
この記事の目的は、どちらの方法でも、実際には現在の ECMAScript である JavaScript を使用してフィボナッチ数を生成する方法を説明することです。
コーディング環境
読者が予想したように、node.js 環境は使用されません。代わりに、ブラウザがコードの解釈と結果の表示に使用されます。スクリプト (コード) はテキスト エディター ファイルに記述し、拡張子「.html」を付けて保存する必要があります。スクリプトには最小限のコードが必要です。
DOCTYPE HTML >< html >
< 頭 >
< 題名 > JavaScript によるフィボナッチ数列 題名 >
頭 >
< 体 >
< スクリプトの種類 = 「テキスト/ecmascript」 >
脚本 >
体 >
html >
これは、Web ページに必要な最小限のおおよそのコードです。この記事のすべてのコーディングは、タグ の間にあります。
記述 (追加) されたコードを実行するには、ファイル名のアイコンをダブルクリックするだけで、コンピューターのブラウザーが開きます。
フィボナッチ数の定義
フィボナッチ数には数学的な定義があります。次のように定義されています。
ここで、Fn はゼロから始まるインデックス n に対応するフィボナッチ数です。
最初の 2 つの数値: 0 と 1 は、この順序で事前に宣言されています。この関数の最後の行は、残りの数値が最初の 2 つの数値からどのように発生するかを示しています。
この定義は、フィボナッチ数の公式の 1 つでもあります。
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 個のフィボナッチ整数 (数値) を生成する ECMAscript 関数は次のとおりです。
< スクリプトの種類 = 「テキスト/ecmascript」 >関数 フィボナッチ ( あ ) {
n = A. 長さ ;
もしも ( n > 0 )
あ [ 0 ] = 0 ;
もしも ( n > 1 )
あ [ 1 ] = 1 ;
為に ( 私 = 2 ; 私 < n ; 私 ++ ) { //n=0 と n=2 が考慮されています
通貨番号 = あ [ 私 - 1 ] + あ [ 私 - 2 ] ;
あ [ 私 ] = 通貨番号 ;
}
}
スクリプトの終了タグは表示されていません。関数は配列を受け取ります。最初の 2 つのフィボナッチ数は、その位置に割り当てられます。 for ループは、0 から始まるインデックス 2 から n のすぐ下まで反復します。 for ループで最も重要なステートメントは次のとおりです。
currNo = A[i – 1] + A[i – 2];
これにより、配列内の直前の 2 つの数値が追加され、現在の数値が取得されます。 fibonacci() 関数の実行が終了するまでに、配列のすべての要素は最初の n 個のフィボナッチ数になります。 fibonacci() 関数を呼び出してフィボナッチ数を表示する適切なコードは次のとおりです。
N = 12 ;到着 = 新着 配列 ( N ) ;
フィボナッチ ( 到着 ) ;
為に ( 私 = 0 ; 私 < N ; 私 ++ )
資料。 書きます ( 到着 [ 私 ] + ' ' ) ;
資料。 書きます ( 「
」 ) ;
脚本 >
このコードは、スクリプトの終了タグを示しています。コードは上記のコードの下に入力されます。 Web ページに表示される出力は次のとおりです。
0 1 1 2 3 5 8 13 21 34 55 89
予想通り。
O(1) 時間で 1 つのフィボナッチ数を生成する
O(1) は定数時間です。これは、1 つの主要な操作を指します。フィボナッチ数を生成する別の数式は次のとおりです。
式の右辺では、5 の平方根を n 乗したものではないことに注意してください。 n 乗されるのは、括弧内の式です。このような表現が 2 つあります。
n が 0 の場合、Fibn は 0 になります。n が 1 の場合、Fibn は 1 になります。n が 2 の場合、Fibn は 1 になります。n が 3 の場合、Fibn は 2 になります。n が 4 の場合、Fibn は 3 になります –等々。読者は、n に異なる値を代入して評価することにより、この式を数学的に検証できます。 n は、この式の 0 から始まるインデックスです。結果は、対応するフィボナッチ数です。
この数式の ECMAScript (JavaScript) コードは次のとおりです。
< スクリプトの種類 = 「テキスト/ecmascript」 >関数 fib番号 ( n ) {
FibN = ( 算数 . 捕虜 ( ( 1 + 算数 . 平方根 ( 5 ) ) / 2 、 n ) - 算数 . 捕虜 ( ( 1 - 算数 . 平方根 ( 5 ) ) / 2 、 n ) ) / 算数 . 平方根 ( 5 ) ;
戻る FibN ;
}
スクリプトの終了タグは表示されていません。累乗 (pow) と平方根 (sqrt) の定義済み関数がどのように使用されているかに注意してください。 ECMAScript (JavaScript) では、Math モジュールをインポートする必要はありません。関数 fibNo() は式を直接実装します。 Web ページでの fibNo() 関数の適切な呼び出しと表示は次のとおりです。
N = 十一 ;右 = fib番号 ( N ) ;
資料。 書きます ( 右 ) ;
脚本 >
このコードは、スクリプトの終了タグを示しています。出力は次のとおりです。
89.00000000000003
回答から不要な小数桁を削除することができます。ただし、それは別の機会に議論します。
複数のフィボナッチ数が必要な場合、コードはゼロベースの対応する n インデックスごとに式を 1 回呼び出す必要があります。
結論
フィボナッチ数は、0 から始まる正の整数の特定のシーケンスです。整数は正の整数です。したがって、フィボナッチ数は、0 から始まる整数または自然数の特定のシーケンスです。このシーケンスでは、最初の 2 つの数値は、この順序で 0 と 1 です。これらの最初の 2 つの数値は、そのように定義されています。残りの数は、直前の 2 つの数を追加することによってそこから展開されます。
最初の 2 つのフィボナッチ数を生成した後、残りのフィボナッチ数を生成して合計 n 個の数になるようにするには、次のステートメントで for ループを使用する必要があります。
currNo = A[i – 1] + A[i – 2];
これにより、直前の 2 つのフィボナッチ数が現在のフィボナッチ数に追加されます。
ゼロから始まるインデックスを指定した場合、対応するフィボナッチ数を取得するには、次の式を使用します。
