PHPでnの階乗を実装する方法-PHPの問題-php.cn

PHPでnの階乗を実装する方法

藏色散人

リリース： 2023-03-10 10:16:01

オリジナル

5114 人が閲覧しました

n の階乗を実装する

php メソッド: 1. "function fat(int $n): int{...}" のようなコードを使用して、通常の再帰を通じて実装します。 2. 通常のメソッドで実装します。「while ($num

PHPでnの階乗を実装する方法

この記事の動作環境: Windows 10 システム、PHP バージョン 7.2.15、DELL G3 コンピューター

php の仕組みn の階乗を実現しますか?

私の知る限り、階乗の実装方法は大きく 3 種類に分けられます。通常の意味での再帰とループはそれぞれ 1 種類として考えられます。これは、いくつかの賢い数学的手法を使用して演算数 (特に乗算演算の数) を削減し、それによって計算効率を最適化する大きなカテゴリでもあります。

高精度の大きな整数の階乗を考慮する場合、PHP 言語では状況がより複雑になります。たとえば、BCMath 拡張機能で提供されるメソッドを使用する場合、明示的な数値と文字列の変換が必要になります。操作は頻繁に比較されます。

この記事では、n を整数としてのみ考慮し、上記の状況をそれぞれ実装しようとします。利用可能なコード例がそれぞれのケースで示され、いくつかの方法の包括的な比較が記事の最後に添付されています。

通常の再帰的実装

1 つ目は通常の再帰的実装で、一般的な再帰公式、fact(n) = n * fat(n-1) によれば、因数分解のコードを書くのは簡単です。通常の再帰実装の利点は、コードが比較的簡潔であり、一般的な公式と同じ処理なのでコードが理解しやすいことです。欠点は、頻繁に自分自身を呼び出す必要があるため、大量のプッシュおよびポップ操作が必要となり、全体的な計算効率が高くないことです (記事の最後の表を参照)。

function fact(int $n): int
{
    if ($n == 0) {
        return 1;
    }
    return $n * fact($n - 1);
}

ログイン後にコピー

通常のループの実装

通常のループの実装には「動的プログラミング」の趣がありますが、中間状態変数の使用頻度が低いため、追加のストレージは必要ありません。スペースが必要なため、一般的な動的計画法のアルゴリズムよりも簡単です。通常の再帰法はトップダウン (n から 1) の計算プロセスですが、通常のループはボトムアップの計算です。

したがって、比較的コードは上記の方法ほど直感的ではありませんが、頻繁なプッシュとポップの処理がなくなるため、計算効率は高くなります(記事の最後の表を参照) ）。

function fact(int $n): int
{
    $result = 1;
    $num = 1;
    while ($num <= $n) {
        $result = $result * $num;
        $num = $num + 1;
    }
    return $result;
}

ログイン後にコピー

自己実装された大整数階乗

PHP の int 型の範囲制限のため、上記の 2 つのメソッドは最大 20 までの階乗しか正確に計算できません。 20 の階乗のみを考慮する場合は、ルックアップテーブル方式を使用する方が高速です。つまり、0 ～ 20 の階乗を事前に計算して配列に格納し、必要なときに一度クエリします。

大きな数の階乗に適応して正確な計算結果を得ることができるように、この記事は「通常のループ法」に基づいて改良され、計算結果の各ビットを配列を使用して格納します(キャリー方式では、各ビットの結果を順番に計算します。

この方法の利点は、精度の高い多数の階乗状況に適用できることであることは言うまでもありませんが、欠点は、10 進階乗の場合、計算プロセスが複雑で時間がかかることです。

function fact(int $n): array
{
    $result = [1];
    $num = 1;
    while ($num <= $n) {
        $carry = 0;
        for ($index = 0; $index < count($result); $index++) {
            $tmp = $result[$index] * $num + $carry;
            $result[$index] = $tmp % 10;
            $carry = floor($tmp / 10);
        }
        while ($carry > 0) {
            $result[] = $carry % 10;
            $carry = floor($carry / 10);
        }
        $num = $num + 1;
    }
    return $result;
}

ログイン後にコピー

BCMath 拡張メソッド

BCMath は、文字列で表される数値 (任意のサイズと精度) の数値計算を処理する PHP の数学的拡張機能です。 C言語で実装された拡張機能なので、上記の自作実装よりも計算速度が速くなります。

推奨学習: 「PHP ビデオチュートリアル」

私のラップトップでは、2000 の階乗も計算します。実装には平均 0.5 ～ 0.6 秒かかります。 BCMath の使用には 0.18 ～ 0.19 秒かかります。この方法の主な欠点は、対応する拡張機能のインストールが必要であり、これは非コードレベルの変更であるため、環境管理のアップグレードが不便なアプリケーションでは実用性が疑わしいことです。

function fact(int $n): string
{
    $result = &#39;1&#39;;
    $num = &#39;1&#39;;
    while ($num <= $n) {
        $result = bcmul($result, $num);
        $num = bcadd($num, &#39;1&#39;);
    }
    return $result;
}

ログイン後にコピー

最適化アルゴリズム

この記事の冒頭で述べたように、最適化アルゴリズムは演算数 (特に乗算演算の数) をできるだけ削減しようとします。可能な限り高速階乗を達成します。小さな整数の階乗の場合、最も高速なアルゴリズムは時間計算量が O(1) のテーブルルックアップ法であるはずであることを考慮すると、このセクションでは主に大きな整数の正確な階乗について説明し、テストします。

現在、階乗最適化は n! = C(n, n/2) * (n/2)! * (n/2)! 複雑さの最適化を通じてより一般的であることが理解されており、このハイライトはこの式は主に C(n, n/2) の最適化にあります。大きな整数の場合、PHP 言語による C(n, n/2) の実装効率は高くなく、コードの可読性も比較的低い (数値や文字列の明示的な変換が頻繁に発生する) ことを考慮して、この記事ではもう一つのより賢い方法。

乗算は加減算に比べて計算速度が遅いのが一般的ですが、乗算の演算回数を減らすことで全体の計算速度を向上させることができます。数学的帰納法により、n の階乗について、(n/2)^2 より小さい 1、1 3、1 3 5... の値を連続的に見つけて、それらを順番に乗算できることがわかります。目標値を取得します。

このアルゴリズムの利点は計算速度が速いことですが、欠点は実装プロセスが直感的ではなく、理解しにくいことです。テスト後、次のコードは 2000 から 0.11 秒の階乗平均時間を計算します。これは、通常のループ方法の約半分の時間です。

この最適化方法に加えて、1...n の数値が 2 で割り切れるかどうかを繰り返しチェックし、2 x で割り切れる回数を記録するなど、他の同様のアイデアも見てきました。一般的な奇数の乗算公式を見つけて、最後に 2^x を乗算して結果を取得します。

function fact(int $n): string
{
    $middleSquare = pow(floor($n / 2), 2);
    $result = $n & 1 == 1 ? 2 * $middleSquare * $n : 2 * $middleSquare;
    $result = (string)$result;
    for ($num = 1; $num < $n - 2; $num = $num + 2) {
        $middleSquare = $middleSquare - $num;
        $result = bcmul($result, (string)$middleSquare);
    }
    return $result;
}

ログイン後にコピー

综合对比

本文中提到的方法是按照由劣到优的顺序，因此，下列表格中每一行中提到优劣势，主要是和其上一两种方法对比。

表格中「测试耗时」一列的测试环境为个人笔记本，硬件配置为 Dell/i5-8250U/16GB RAM/256GB SSD Disk，软件配置为 Win 10/PHP 7.2.15。

PHPでnの階乗を実装する方法