直接式を使用して最初の n 個のフィボナッチ数を出力する

この記事では、直接式を使用して最初の n 個のフィボナッチ数を出力する問題を解決します。

数学では、フィボナッチ数は通常 Fn (n 番目のフィボナッチ数) で表され、各数値が前の 2 つの数値の合計に等しいシーケンスを形成します。 n 番目のフィボナッチ数は次のように表現できます -

$$\mathrm{Fn\:=\:F_{n-1}\: \:F_{n-2}}$$

シリーズは 0 と 1 から始まります。 0 と 1 から始まるフィボナッチ数列の最初のいくつかの値は -

リーリー

したがって、この問題では、数値 N が与えられ、直接公式を使用して最初の N 個のフィボナッチ数を出力する必要があります。

＃＃＃例＃＃＃

: 4 と入力してください

出力

: 0 1 1 2

入力

: 8

出力

: 0 1 1 2 3 5 8 13 この問題では、n 番目のフィボナッチ数を取得するための直接的な式を与えるビネーの公式の概念を理解する必要があります。これについては、アルゴリズムのセクションで詳しく説明します。

＃＃＃アルゴリズム＃＃＃

式 $\mathrm{Fn\:=\:F_{n-1}\: \:F_{n-2}}$ によれば、(n-1) 番目の項目と (n- 2) 番目の項目 これらを追加すると、n 番目の項が得られます。この問題では、n 番目のフィボナッチ数を取得するには、直接公式を使用して最初の n 個のフィボナッチ数を出力する必要があるためです。

フィボナッチ数列の n 番目のフィボナッチ数を取得するには、

Binet の公式

と呼ばれる明示的な公式を適用できます。数学者のジャック・フィリップ・マリー・ビネによって作成されました。

＃＃＃式＃＃＃

$\mathrm{Fn}$ がフィボナッチ数列の n 番目のフィボナッチ数を表す場合、 と表現できます。 $$\mathrm{F_n\:=\:\frac{1}{\sqrt5}((\frac{1 {\sqrt5}}{2})^n\:-\:(\frac{ 1 -{\sqrt5}}{2})^n)}$$

NOTE

- この式は、1 と 1 から始まるフィボナッチ数列を与えます。 0 と 1 から始まるフィボナッチ数列を取得するには、n-1 を使用して n 番目のフィボナッチ数を取得します。

二次方程式の概念を使用してこの式を導き出すことができます。この式を使用して、n 番目のフィボナッチ数までの各フィボナッチ数を出力し、最初の n 個のフィボナッチ数を出力します。

＃＃＃方法＃＃＃

0 と 1 から始まるフィボナッチ数列を考慮しているため、for ループを使用して、0 から n 回の反復までの N 個のフィボナッチ数をすべて出力します。

変数をフィボナッチ数に初期化し、i

• 各反復でフィボナッチ数の出力を続けます。これにより、最初の N 個のフィボナッチ数が得られます。

• ＃＃＃例＃＃＃

  以下は、上記のメソッドを C で実装したものです - リーリー ＃＃＃出力＃＃＃ リーリー

• 時間計算量: O(n),

  for ループは i が n 未満になるまで実行されるためです。

スペースの複雑さ: O(1)、

余分なスペースを使用しないため。

＃＃＃結論は＃＃＃

この記事では、再帰を使用する代わりに直接式を使用して最初の N 個のフィボナッチ数を出力する方法を学びました。フィボナッチ数列のn番目のフィボナッチ数を直接求めることができるビネーの公式も学びました。

この記事がこのトピックに関するすべての概念を理解するのに役立つことを願っています。

以上が直接式を使用して最初の n 個のフィボナッチ数を出力するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。