php如何實(shí)現(xiàn)n的階乘

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

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

本文操作環(huán)境：Windows10系統(tǒng)、PHP 7.2.15版，DELL G3電腦

php怎么實(shí)現(xiàn)n的階乘?

據(jù)本人了解，階乘的實(shí)現(xiàn)方法一般可以分為三種，通常意義下的遞歸和循環(huán)各算一種，還有一大類通過(guò)一些巧妙的數(shù)學(xué)方法減少運(yùn)算次數(shù)（尤其是乘法運(yùn)算次數(shù)），進(jìn)而優(yōu)化計(jì)算效率。

如果要考慮到高精度、大整數(shù)的階乘，對(duì)于 PHP 語(yǔ)言而言，情況會(huì)更復(fù)雜一些，比如使用 BCMath 擴(kuò)展提供的一些方法時(shí)，顯式的數(shù)字與字符串轉(zhuǎn)換操作比較頻繁。

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

普通遞歸實(shí)現(xiàn)

首先是普通遞歸實(shí)現(xiàn)，根據(jù)遞歸的通用公式 fact(n) = n * fact(n-1) 很容易寫(xiě)出階乘的計(jì)算代碼。普通遞歸實(shí)現(xiàn)的優(yōu)點(diǎn)在于代碼比較簡(jiǎn)潔，和通用公式一樣的過(guò)程使得代碼容易理解。缺點(diǎn)則在于由于需要頻繁地調(diào)用自身，需要大量的入棧出棧操作，整體的計(jì)算效率不高（見(jiàn)文末表格）。

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

普通循環(huán)實(shí)現(xiàn)

普通循環(huán)實(shí)現(xiàn)有些「動(dòng)態(tài)規(guī)劃」的味道，但由于中間態(tài)變量使用頻率低，不需要額外存儲(chǔ)空間，所以要比一般的動(dòng)態(tài)規(guī)劃算法簡(jiǎn)單。普通遞歸方法是自頂向下（由 n 到 1）的計(jì)算過(guò)程，而普通循環(huán)是自底向上進(jìn)行計(jì)算。

因此相對(duì)而言，代碼沒(méi)有上述方法直觀，但由于少了頻繁的入棧出棧過(guò)程，計(jì)算效率會(huì)高一些（見(jiàn)文末表格）。

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

自行實(shí)現(xiàn)的大整數(shù)階乘

由于 PHP 中 int 類型的范圍限制，上述兩種方法最多只能精確計(jì)算到 20 的階乘。如果只是考慮到 20 的階乘的情況，那么用查表法實(shí)現(xiàn)會(huì)更快：事先計(jì)算好 0-20 的階乘并存儲(chǔ)到一個(gè)數(shù)組中，需要用時(shí)查詢一次便可。

為了能夠適應(yīng)大數(shù)的階乘，得到精確的計(jì)算結(jié)果，本文基于「普通循環(huán)方法」進(jìn)行改進(jìn)，使用數(shù)組存儲(chǔ)計(jì)算結(jié)果中的每一位（由低到高位），通過(guò)相乘進(jìn)位的方式依次計(jì)算每一位的結(jié)果。

不言而喻，本方法的優(yōu)點(diǎn)在于可以適用于高精度的大數(shù)階乘場(chǎng)合，缺點(diǎn)就是對(duì)于小數(shù)階乘而言，計(jì)算過(guò)程復(fù)雜且速度慢。

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 擴(kuò)展方法

BCMath 是 PHP 的一個(gè)數(shù)學(xué)擴(kuò)展，用于處理字符串表示的數(shù)字（任意大小和精度）的數(shù)值計(jì)算。由于是使用 C 語(yǔ)言實(shí)現(xiàn)的擴(kuò)展，計(jì)算速度會(huì)比上述自行實(shí)現(xiàn)的快。

》

在本人的筆記本上，同樣是計(jì)算 2000 的階乘，自行實(shí)現(xiàn)的需要平均 0.5-0.6 秒，使用 BCMath 耗時(shí) 0.18-0.19 秒。該方法的缺點(diǎn)主要在于需要安裝相應(yīng)的擴(kuò)展，屬于非代碼層面的改動(dòng)，對(duì)于環(huán)境管理升級(jí)不便的應(yīng)用而言，可實(shí)踐性有待商榷。

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

優(yōu)化算法

在本文開(kāi)頭有提到，優(yōu)化算法嘗試盡可能地減少運(yùn)算次數(shù)（尤其是乘法的運(yùn)算次數(shù)）來(lái)實(shí)現(xiàn)快速階乘。考慮到對(duì)于小整數(shù)階乘而言，最快的算法應(yīng)該是查表法，時(shí)間復(fù)雜度為 O(1)，所以本小節(jié)主要針對(duì)大整數(shù)的精確階乘進(jìn)行討論和測(cè)試。

據(jù)了解，目前階乘優(yōu)化比較常見(jiàn)的是通過(guò) n! = C(n, n/2) * (n/2)! * (n/2)! 式子進(jìn)行復(fù)雜度優(yōu)化，而該式子中的亮點(diǎn)主要在于 C(n, n/2) 的優(yōu)化?？紤]到大整數(shù)情況下，PHP 語(yǔ)言實(shí)現(xiàn) C(n, n/2) 的效率不高，而且實(shí)現(xiàn)的代碼可讀性比較差（頻繁的數(shù)字與字符串的顯式轉(zhuǎn)換），所以本文用的是另外一種比較巧妙的方法。

乘法的計(jì)算速度通常要低于加減法運(yùn)算，通過(guò)減少乘法的運(yùn)算次數(shù)可以提高整體運(yùn)算速度。通過(guò)數(shù)學(xué)歸納可以發(fā)現(xiàn)，對(duì)于 n 的階乘，可以依次求出比 (n/2)^2 小 1、1+3、1+3+5... 的數(shù)值，再依次相乘得到目標(biāo)值。

該算法的優(yōu)點(diǎn)在于計(jì)算速度較快，而缺點(diǎn)就是實(shí)現(xiàn)過(guò)程不直觀、不易理解。經(jīng)測(cè)試，以下代碼計(jì)算 2000 的階乘平均時(shí)間為 0.11 秒，大約是普通循環(huán)方法的一半耗時(shí)。

除了這種方法優(yōu)化，也有看到其它的類似的思路，比如對(duì) 1...n 中的數(shù)反復(fù)檢驗(yàn)是否被 2 整除，記錄下被 2 整除的次數(shù) x，并嘗試歸納出共同的奇數(shù)相乘式，最后乘以 2^x 得到結(jié)果。

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;
}

綜合對(duì)比

本文中提到的方法是按照由劣到優(yōu)的順序，因此，下列表格中每一行中提到優(yōu)劣勢(shì)，主要是和其上一兩種方法對(duì)比。

表格中「測(cè)試耗時(shí)」一列的測(cè)試環(huán)境為個(gè)人筆記本，硬件配置為 Dell/i5-8250U/16GB RAM/256GB SSD Disk，軟件配置為 Win 10/PHP 7.2.15。

以上是“php如何實(shí)現(xiàn)n的階乘”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！