php怎麼實現n的階乘 - tw511教學網

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。

總結

雖然本文將實現方法分為三大類，但其實也可以分為迴圈和遞迴兩大類，在這兩類中分別使用相應的演演算法優化計算效率。But，總體而言，迴圈的效率要優於遞迴。

講道理，本文中使用的優化演演算法並不是最優解，只是用 PHP 相對好實現，程式碼易讀性也比較高。有興趣的讀者可以谷歌瞭解更多的騷操作。

以上就是php怎麼實現n的階乘的詳細內容，更多請關注TW511.COM其它相關文章！