数値がフィボナッチ数であるかどうかをテストする方法
1. 概要
このチュートリアルでは、フィボナッチ数列について説明します。 フィボナッチ数列を定義し、例を使用してフィボナッチ数を生成するさまざまな方法を検討します。
最後に、指定された番号がフィボナッチ数であるかどうかを確認するための擬似コードを提示します。
2. フィボナッチ数列
フィボナッチ数列は、数列として定義できます。 フィボナッチ数列は当初、ピンガラによってインドの数学で作成され、使用されました。 しかし、それは後にフィボナッチとして知られるレオナルド・ピサーノ・ボゴッロによって世界に示されました。
さらに、フィボナッチ数列は興味深い特性に従います。 プロパティはです。その前に表示される2つの要素を追加することで、シリーズの次の要素を見つけることができます。
プロパティを確認しましょう。 要素34は、前の2つの要素21と13(21 + 13 = 31)を追加することで見つけることができます。 同様に、前の2つの要素5と3を追加することで、要素8を見つけることができます。 さらに、シリーズの34の次の要素を見つけることができます。 55(34 + 21)になります。
それでは、フィボナッチ数列を生成するための一般化された方程式を導き出しましょう。 最初は、事前に与えられた初期データと、から始まります。 さらに、シリーズは、2つの前の隣接する要素を追加することによってさらに進みます。 したがって、シリーズの位置にある要素は次のように計算できます。
さらに、フィボナッチ数列の一部である番号は、フィボナッチ数として知られています。 したがって、フィボナッチ数列は、特定の数がフィボナッチ数であるかどうかを確認するのに役立ちます。
3. ビネットの公式
一般的なプロパティに加えて、フィボナッチ数列の要素を見つける別の方法があります。 黄金比法を使用してフィボナッチ数列の要素を生成できます。さらに、一般にBinetの式として知られています。 したがって、シリーズ内の要素を見つけるための方程式は次のとおりです。
変数は黄金比を表します。 さらに、変数はの共役です。 したがって、次の形式で表すことができます。
したがって、Binetの式を単純化できます。
さらに、黄金比は次のように表すことができます。
したがって、最終的な方程式は次のようになります。
それでは、この式を確認しましょう。 したがって、フィボナッチ数列からいくつかの要素を計算し、前のセクションで示したフィボナッチ数列と比較します。 5を確認しましょう:
次に、6に設定しましょう:
最後に、7を設定します。
したがって、Binetの式を使用してわかるように、フィボナッチ数列の要素を生成できます。
4. フィボナッチ数をチェックするためのアプローチ
今のところ、フィボナッチ数列の要素を生成する方法を知っています。 次に、特定の番号がフィボナッチ数であるかどうかを確認する方法について説明します。 まず、フローチャートを見てみましょう。
最初に、チェックプロセスを開始するための数値を入力します。 次のステップでは、2つの変数と:を計算します。
さらに、それらのいずれかが完全な正方形であるかどうかをチェックします。数学では、2つの等しい整数の積として表現できる場合、数値は完全な正方形です。 との場合、数値は完全な正方形です。
したがって、またはが完全な正方形であるかどうかを確認するために、とを計算します。 最後に、またはの少なくとも1つが完全な正方形である場合、指定された数はフィボナッチ数です。
5. 擬似コード
次に、擬似コードを見てみましょう。
最初に、指定された数値を入力として受け取り、その数値がフィボナッチであるかどうかを擬似コードが返します。 擬似コードの時間計算量を分析してみましょう。 この擬似コードでは、1つの数値しか入力できません。 したがって、時間と空間の両方の複雑さはです。 さらに、配列を入力する場合、配列内の要素の総数が の場合、時間計算量はになります。
6. 擬似コードの検証
いくつかの例を使用して擬似コードを検証しましょう。入力として擬似コードを実行してみましょう。
この例では、ご覧のとおりです。 したがって、入力番号5はフィボナッチ数です。 別の例を見てみましょう。 この場合、指定された入力番号は7です。 数字の7はフィボナッチ数列の一部ではありません。 したがって、それはフィボナッチ数ではありません。 擬似コードを実行して検証してみましょう。
ここでは、どちらでもありません。 249と241はどちらも完全な正方形ではありません。 したがって、指定された入力はフィボナッチ数ではありません。
7. アプリケーション
フィボナッチ数列と数値は、コンピュータサイエンスと数学の分野でいくつかのアプリケーションで使用されています。コンピュータサイエンスでは、フィボナッチ数は、オーディオファイル形式の損失圧縮、で使用されます。 ]バイナリツリー表現、フィボナッチヒープデータ構造、フィボナッチキューブグラフ、ソートアルゴリズム、ゴールデンセクション検索、 疑似乱数ジェネレーター。
数学の分野では、最適化法、最大公約数の取得、数値ゲーム予測、動的整数生成など、多くの重要なアプリケーションでフィボナッチ数が使用されます。
高エネルギー物理学、量子力学、暗号化などの他の分野では、さまざまなアプリケーションでフィボナッチ数列を利用しています。
8. 概要
このチュートリアルでは、フィボナッチ数列と数について説明しました。 数値例を使用して、フィボナッチ数列のフィボナッチ数を生成する2つの方法について説明しました。
最後に、特定の数がフィボナッチ数であるかどうかをテストするための擬似コードを提示しました。 例を使用して擬似コードを検証しました。