フィボナッチジェネレーター

フィボナッチ数列は各数が前の2つの数の和である数列です：0、1、1、2、3、5、8、13、21、34、55、89、144... ピサのレオナルド（フィボナッチ）にちなんで名付けられ、1202年の著書「算盤の書（Liber Abaci）」でヨーロッパ数学に紹介されました。この数列は自然界に見られます：ヒマワリの種の螺旋配置、松ぼっくりのウロコ、葉の葉序、オウムガイの殻、木の分枝など。

黄金比（φ ≈ 1.6180339887...）はnが無限大に近づくにつれたF(n+1)/F(n)の極限値です。正確な値は(1 + √5) / 2です。2つの量が黄金比にあるとき、それらの比はその和と大きい方の量の比と同じになります：(a+b)/a = a/b = φ。黄金比はユークリッド幾何学、芸術、建築（パルテノン神殿）に現れ、数学者たちを長い間魅了してきました。

ヒマワリ、松ぼっくり、パイナップルの螺旋の数は連続したフィボナッチ数です（通常21と34、または34と55）。多くの花の花びらの数はフィボナッチ数（3、5、8、13）です。茎の葉の配置は日光を最大化するためにフィボナッチ分数に従っています。フィボナッチが数列を紹介するために使用したウサギの個体数モデル：ウサギのペアが2ヶ月目から毎月新しいペアを産む場合、個体数はフィボナッチ数列に従って増加します。

単純な再帰：O(2^n) — 指数時間。メモ化再帰または反復：O(n)。行列指数：O(log n)。閉形式のビネの公式：F(n) = (φ^n − ψ^n) / √5（ψ = (1−√5)/2）— 理論的にはO(1)ですが、大きなnでは浮動小数点エラーにより精度が失われます。正確な大きなフィボナッチ数には任意精度整数演算を使用してください（PythonのintやJavaのBigInteger）。F(100)は21桁、F(1000)は209桁です。

フィボナッチヒープ（ダイクストラのアルゴリズムで使用）、フィボナッチ探索（二分探索の代替）、疑似乱数生成器、ゼッケンドルフの定理（すべての正の整数は連続しないフィボナッチ数の和として一意に表現できる）、フィボナッチ符号（整数圧縮のための普遍コード）、スキップリストのランダムレベル生成、ユークリッドのGCDアルゴリズムなど特定のアルゴリズムの最悪ケース入力の分析などがあります。