php怎麼實現n的階乘

php實現n的階乘的方法：1、透過普通遞歸實現，程式碼如「function fact(int $n): int{...}」；2、透過普通循環實現，程式碼如「 while ($num

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

推薦學習：《PHP影片教學》

在本人的筆記本上，同樣是計算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, &#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。

总结

虽然本文将实现方法分为三大类，但其实也可以分为循环和递归两大类，在这两类中分别使用相应的算法优化计算效率。But，总体而言，循环的效率要优于递归。

讲道理，本文中使用的优化算法并不是最优解，只是用 PHP 相对好实现，代码易读性也比较高。有兴趣的读者可以谷歌了解更多的骚操作。

以上是php怎麼實現n的階乘的詳細內容。更多資訊請關注PHP中文網其他相關文章！