Math

PHP でフィボナッチ数列をプログラムに落とし込む方法

はじめに

エンジニアの採用選考では、コーディングテストにフィボナッチ数列の問題が出題されることがあります。フィボナッチ数は、中学受験の算数で見たことがあると思います、大人になると忘れちゃいますよね。アルゴリズムの学習に良いので、PHP でプログラム化して、簡単に解説してみました。

検証環境

解説

フィボナッチ数列 は、1202 年にイタリアの数学者 レオナルド・フィボナッチ によって書かれた書籍 算盤の書 で紹介された数列です。

この数列は、下記のような最初の 2 つの数が 0, 1 で、3 つ目以降は前の 2 つの数の和を並べたものです。

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...

花弁の数、松毬や仙人掌の螺旋構造、葉序、向日葵の種の配列などが フィボナッチ数 になっており、自然界には フィボナッチ数 が多く存在していると言われています。

漸化式は、F0 = 0, F1 = 1, Fn+2 = Fn + Fn+1 (n ≥ 0) のように定義されています。

PHP でプログラムに落とし込むと下記のようになります。

function getFibonacciNumber(int $n): int {
  return $n < 2 ? $n : getFibonacciNumber($n - 1) + getFibonacciNumber($n - 2);
}

再帰処理のコストはかかるけど、シンプルです。

一般項（コーシー・ビネの公式）の場合は、Fn = 1 / √5 { (1 + √5 / 2 )n – (1 – √5 / 2 )n } になります。

PHP でプログラムに落とし込むと下記のようになります。

function getFibonacciNumber(int $n): int {
  return 1 / sqrt(5) * (((1 + sqrt(5)) / 2) ** $n - ((1 - sqrt(5)) / 2) ** $n);
}

ちょっと 可読性 が低いですね。

四捨五入による計算 の場合は、φ = 1 + √5 / 2, Fn = ⌊φn / √5⌉ になります。

PHP でプログラムに落とし込むと下記のようになります。

function getFibonacciNumber(int $n): int {
  return round((((sqrt(5) + 1) / 2) ** $n) / sqrt(5));
}

読みやすいけど、数学が苦手な人に優しくないですね。

二項係数 の場合、Fn = 1 / 2n – 1 Σ [k = 0, ⌊n – 1 / 2⌋] (n), (2k + 1) 5k になります。

…切りが無いのでここまでにします。

で、実務で何の役に立つんですかって話なんですけど、アルゴリズム の学習に良いのと、投資関係の案件で テクニカル分析 の フィボナッチ・リトレースメント などの理解に役立つぐらいでしょうか。

以上です。

おわりに

余談ですが、フィボナッチ数 と 黄金比 の都市伝説を 1 つ紹介します。

オウムガイの 対数螺旋 は 黄金螺旋 である！

…というのはオカルトで、黄金比 は 無理数 なので現実世界に完全なる黄金比を裏付ける科学的根拠は存在しません。

実際に自分で 黄金長方形 の透過画像を重ねてみると、ネット情報の事実から真実が見えるかもしれません。

参考