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

まえがき

少し前に、私はフィボナッチ数列の計算を最適化する従来の再帰的手法に出会いました。しかし、あるとき、良い方法が間に合わなかったので、後で関連する情報を検索し、さまざまな計算ソリューションをまとめて、それをみんなで共有し、コミュニケーションをとり、一緒に学びました。

お勧め: 「PHP ビデオ チュートリアル 」

フィボナッチ数とは

フィボナッチ フィボナッチ数列とも呼ばれます黄金分割数列として知られるこの数列は、数学者レオナルドダ フィボナッチがウサギの繁殖を例として紹介したものであるため、「ウサギ数列」とも呼ばれています。 、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);
}

再帰的最適化

上記の再帰的手法からわかるように、多くの繰り返し計算が実行され、パフォーマンスが非常に低下します。計算の数が多すぎます。ひどいことです。繰り返しの計算はパフォーマンスに影響するため、最適化は繰り返しの計算を減らすことから始まります。つまり、以前に計算された計算を保存することで、過度の繰り返し計算を回避し、再帰的アルゴリズムを最適化します。

/**
 * 递归优化
 * @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];
}

最後に

わかりました。解決策をいくつか書きました。何か間違っている場合は、指摘してください。他の計算方法がある場合は、共有して一緒に学び、コミュニケーションを図ることができます。ありがとうございます。

以上がPHP のフィボナッチ数列の N アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。