C++實現高效階乘計算

一、遞歸實現階乘

遞歸是一種常見的計算階乘的方法，它可以用簡潔的代碼來實現。遞歸實現階乘的代碼如下：

unsigned long long factorialRecursion(unsigned int n) {
    if(n == 0) {
        return 1;
    } else {
        return n * factorialRecursion(n-1);
    }
}

這裡定義了一個函數factorialRecursion，該函數使用了遞歸方法來計算n的階乘。當n=0時，返回1；否則，返回n * factorialRecursion(n-1)。

遞歸的思路很清晰簡單，但是在計算大數階乘時，會造成棧溢出的問題。因此，我們需要尋找其他更加高效的實現方法。

二、循環實現階乘

循環是一種常用的計算階乘的方法，也是比較高效的方式。循環實現階乘的代碼如下：

unsigned long long factorialLoop(unsigned int n) {
    unsigned long long result = 1;
    for(int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

這裡定義了一個函數factorialLoop，該函數使用循環來計算n的階乘。在循環過程中，通過result變量來保存階乘結果。循環從1到n遍歷，每次將i乘以result保存，最終返回result。

循環實現的階乘計算方法不會產生棧溢出等問題，同時由於代碼量較少，執行效率也比較高。

三、優化階乘實現

在實際計算過程中，當計算的數較大時，循環計算的時間會變得很長。因此，我們需要尋找一些優化方法來減少計算時間。

3.1 質因數分解

質因數分解指的是將一個數分解為質因數的乘積，並利用質因數的性質計算出階乘。例如10的階乘可以表示為10! = 2^8 * 3^4 * 5^2 * 7。

這種方法的優點是可以大大減少計算的時間，但缺點則是需要先把數分解為質因數的乘積，這一計算也需要一定的時間。因此，該方法適用於計算大數階乘。

unsigned long long factorial(unsigned int n) {
    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
    int cnt = 8;
    unsigned long long result = 1;
    for(int i = 0; i < cnt; ++i) {
        int factor = primes[i];
        unsigned long long count = 0;
        while(factor <= n) {
            count += n / factor;
            factor *= primes[i];
        }
        result *= pow(primes[i], count);
    }
    return result;
}

上述代碼中，我們先將待計算階乘的數分解為質因數的乘積。然後，通過循環計算每個質因數出現的次數，並乘以相應的質因數的指數，最終返回階乘結果。

3.2 斯特林公式

斯特林公式是一種計算階乘的數學公式，可以用於計算大數階乘。該公式的形式如下：

$$n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$$

下面是使用斯特林公式計算階乘的代碼實現：

unsigned long long factorialStirling(unsigned int n) {
    double e = exp(1.0);
    return (unsigned long long)round(sqrt(2*M_PI*n) * pow(n/e, n));
}

上述代碼中，函數factorialStirling使用了斯特林公式計算階乘。其中，exp(1.0)表示以e為底數的指數函數，pow(n/e, n)表示n/e的n次方，round表示進行四捨五入操作。

四、總結

本文介紹了多種計算階乘的方法，包括遞歸、循環、質因數分解和斯特林公式等方法。對於不同的問題，我們可以選擇不同的方法進行計算。在實際編程中，我們需要綜合考慮計算效率、精度和代碼複雜度等因素，來選擇最適合的方法。