PHPアルゴリズム:フィボナッチ数列のN種類のアルゴリズム

前言
この間、フィボナッチ数列を最適化して計算する通常の再帰方法に出会ったが、しばらくは良い方法を思いつかなかったので、後で関連資料を探して、多種の計算解法をまとめたので、分かち合って、みんなと一緒に交流して勉強した.
フィボナッチの数は?
フィボナッチ数列(Fibonacci sequence)は、黄金分割数列とも呼ばれ、数学者レオナルド・フィボナッチ(Leonardoda Fibonacci)がウサギの繁殖を例に導入したことから「ウサギ数列」とも呼ばれ、1、1、2、3、5、8、13、21、34、・・・数学的には、フィボナッチ数列は、F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2)(n≧3,n∈N*)という繰返し方法で定義される. が分かったので,N位フィボナッチの取得数を様々な方法で計算した.
通常再帰
この方法は最も一般的であり、定義F(n)=F(n - 1)+F(n - 2)に基づいて直接再帰的に計算すればよいが、性能は最も低い.

/**
 *     
 * @param int $n
 * @return int
 */
function fib($n = 1)
{
    //     
    if ($n < 3) {
        return 1;
    }
    //        
    return fib($n - 1) + fib($n - 2);
}

さいきてきさいてきか
以上の再帰法から,多くの繰返し計算が行われており,性能が極めて劣っており,Nが大きいほど計算の回数が恐ろしくなると,繰返し計算が性能に影響を及ぼす以上,最適化は繰返し計算を減らすことから着手し,すなわち前に計算したメモリを蓄積することで,過剰な繰返し計算を回避し,再帰アルゴリズムを最適化することができる.

/**
 *     
 * @param int $n
 * @param int $a
 * @param int $b
 * @return int
 */
function fib_2($n = 1, $a = 1, $b = 1)
{
    if ($n > 2) {
        //      ，      
        return fib_2($n - 1, $a + $b, $a);
    }
    return $a;
}

記憶は底から上へ
フィボナッチ数のサブ問題を下から上へ反復して計算し,計算した値を格納し,計算した値により計算した.forサイクルを使用して、再帰による繰返し計算の問題を低減します.

/**
 *        
 * @param int $n
 * @return int
 */
function fib_3($n = 1)
{
    $list = [];
    for ($i = 0; $i <= $n; $i++) {
        //       ，       
        if ($i < 2) {
            $list[] = $i;
        } else {
            $list[] = $list[$i - 1] + $list[$i - 2];
        }
    }
    //        ，  N  
    return $list[$n];
}

ボトムアップ反復
最低ビット初期化賦値は、forを用いて低位から高位への反復計算を行い、N番目の数を得る.

/**
 *         
 * @param int $n
 * @return int
 */
function fib_4($n = 1)
{
    //     
    if ($n <= 0) {
        return 0;
    }
    if ($n < 3) {
        return 1;
    }
    $a = 0;
    $b = 1;
    //     
    for ($i = 2; $i < $n; $i++) {
        $b = $a + $b;
        $a = $b - $a;
    }
    return $b;
}

こうしきほう
フィボナッチ配列と金分割比との関係を理解することによって,金分割率を用いてN番目のフィボナッチ数を計算した.

/**
 *    
 * @param int $n
 * @return int
 */
function fib_5($n = 1)
{
    //      
    $radio = (1 + sqrt(5)) / 2;
    //                    
    $num = intval(round(pow($radio, $n) / sqrt(5)));
    return $num;
}

無敵な殴り方
この方法は、あまり言わないでください.みんな知っていますが、簡単にやってはいけません.

/**
 *      
 * @param int $n
 * @return int
 */
function fib_6($n = 1)
{
    //    30  
    $list = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269];
    return $list[$n];
}

最後に
はい、私は大体いくつかの解法を書いて、もし間違っているところがあれば、皆さんに指摘してください.私はすぐに修正します.皆さんは他の計算方法があります.分かち合って一緒に交流して勉強してください.ありがとうございます.