php如何實現n的階乘

這篇文章主要介紹php如何實現n的階乘，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

php實現n的階乘的方法：1、通過普通遞歸實現，代碼如“function fact(int $n): int{...}”；2、通過普通循環實現，代碼如“while ($num <= $n) {$result = $result...}”。

本文操作環境：Windows10系統、PHP 7.2.15版，DELL G3電腦

php怎么實現n的階乘?

據本人了解，階乘的實現方法一般可以分為三種，通常意義下的遞歸和循環各算一種，還有一大類通過一些巧妙的數學方法減少運算次數（尤其是乘法運算次數），進而優化計算效率。

如果要考慮到高精度、大整數的階乘，對于 PHP 語言而言，情況會更復雜一些，比如使用 BCMath 擴展提供的一些方法時，顯式的數字與字符串轉換操作比較頻繁。

本文在只考慮 n 為整數的情況下，分別嘗試實現上述的幾種情況，每種情況給出可用的代碼示例，并在文末附上幾種方法的綜合對比情況。

普通遞歸實現

首先是普通遞歸實現，根據遞歸的通用公式 fact(n) = n * fact(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 類型的范圍限制，上述兩種方法最多只能精確計算到 20 的階乘。如果只是考慮到 20 的階乘的情況，那么用查表法實現會更快：事先計算好 0-20 的階乘并存儲到一個數組中，需要用時查詢一次便可。

為了能夠適應大數的階乘，得到精確的計算結果，本文基于「普通循環方法」進行改進，使用數組存儲計算結果中的每一位（由低到高位），通過相乘進位的方式依次計算每一位的結果。

不言而喻，本方法的優點在于可以適用于高精度的大數階乘場合，缺點就是對于小數階乘而言，計算過程復雜且速度慢。

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 語言實現的擴展，計算速度會比上述自行實現的快。

》

在本人的筆記本上，同樣是計算 2000 的階乘，自行實現的需要平均 0.5-0.6 秒，使用 BCMath 耗時 0.18-0.19 秒。該方法的缺點主要在于需要安裝相應的擴展，屬于非代碼層面的改動，對于環境管理升級不便的應用而言，可實踐性有待商榷。

function fact(int $n): string
{
    $result = '1';
    $num = '1';
    while ($num <= $n) {
        $result = bcmul($result, $num);
        $num = bcadd($num, '1');
    }
    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的階乘”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！