HOWTO · C++
在 C++ 中計算數字的階乘
本文演示瞭如何在 C++ 中計算數字的階乘
本頁內容
在 C++ 中,若要計算非負整數的階乘 n!,可將從 2 到 n 的因數依序相乘。迴圈通常是最簡單的方法;遞迴則更直接地呈現數學定義。以下範例展示這兩種方法,並說明 unsigned long long 的限制。
階乘的定義與輸入
對於非負整數 n,階乘 n! 是從 1 到 n 的所有正整數的乘積。依定義,0! 等於 1;即使沒有因數可相乘,這項定義也能讓相關公式保持一致。例如,5! 表示 5 * 4 * 3 * 2 * 1。
以下範例會計算非負整數輸入的階乘。階乘可用於排列、組合與機率計算。階乘的值會快速增長,因此輸入有效,不代表結果一定能放入特定的 C++ 整數型別。
使用迴圈計算階乘
迴圈會保留目前的乘積,並依序乘上從 2 到 n 的每個整數。將乘積初始值設為 1,就能同時正確處理 0 和 1:此時迴圈不會執行,而初始值就是正確結果。
執行以下範例:
本節中的程式碼以及顯示的標籤或輸出仍為英文。
#include <iostream>
unsigned long long factorial(unsigned int n) {
unsigned long long result = 1;
for (unsigned int factor = 2; factor <= n; ++factor) {
result *= factor;
if (factor == n) {
break;
}
}
return result;
}
int main() {
std::cout << "5! = " << factorial(5) << '\n';
}
5! = 120
累加變數 result 會保存目前的乘積。每次迴圈都會乘上下一個因數。當 factor 到達 n 時,break 會在迴圈遞增前結束迴圈,避免無號計數器在達到最大值時發生回繞。當 n 為 0 或 1 時,迴圈不會執行,初始結果會維持為 1。這個版本使用固定的呼叫堆疊空間。
使用遞迴計算階乘
遞迴會表示這個等式:n! = n * (n - 1)!。當 n 為 0 或 1 時,基底情況會回傳 1;其他每次呼叫都會使用較小的引數,因此最後會到達基底情況。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
#include <iostream>
unsigned long long factorial(unsigned int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
std::cout << "5! = " << factorial(5) << '\n';
}
5! = 120
這個函式容易與數學定義對照,但每往下計算一步就會建立一次函式呼叫。遞迴層數太深會額外占用呼叫堆疊空間。由於參數是無號型別,這個函式不接受負值;若呼叫端收到有號輸入,應先檢查數值,再轉換成無號型別。提供的範例執行結果會印出 5! = 120。
處理輸入限制與整數溢位
此處將階乘定義為非負整數的運算。有號輸入傳入接受 unsigned int 的函式之前,應先檢查其值;將負數轉成無號型別會使它變成很大的正數。
兩個範例都使用 unsigned long long。C++ 保證這個型別至少能表示到 20!,但無法表示所有階乘。乘法結果超過型別上限後,無號算術會以大於該上限 1 的數為模數回繞。回繞後的值並非數學上的階乘。若要處理更大的輸入,可以使用大整數函式庫,或在每次乘法前檢查 result <= max / factor;其中 max 是 std::numeric_limits<unsigned long long>::max()。
選擇合適的方法
若要直接計算並維持固定的呼叫堆疊用量,請使用迴圈。若遞迴與階乘定義的直接對應能讓周遭演算法更容易理解,也可以使用遞迴,但輸入必須小到能符合可用的堆疊空間。無論使用哪種方法,都應根據應用程式所需的最大結果選擇數值表示方式,並明確處理輸入與溢位限制。階乘範例適用於組合學與機率計算;若數值超出內建整數型別的範圍,實際應用通常可透過代數化簡或大整數型別處理。