c120 - 00623 - 500!
題目描述
題目要求計算並輸出 n 的階乘，其中 n 的範圍是 0 到 1000。由於 500! 的長度超過了標準整數資料型態的表示範圍，因此需要使用字元陣列來模擬大數的乘法運算。
解題思路
程式使用一個整數陣列 b 來儲存階乘的每一位數字。陣列的每個元素代表一個數字，從 b[1] 到 b[10000]。程式首先初始化 b[1] 為 1。然後，對於每個從 1 到 n 的數字 k，程式將 b 陣列中的每個元素乘以 k。由於乘法可能會產生進位，程式會處理進位，將進位加到下一位。在計算完 k 的階乘後，程式將結果轉換為字串 ans[k] 並儲存。最後，程式讀取輸入的 n，輸出 n! 的結果。
複雜度分析
- 時間複雜度: O(n * m^2)，其中 n 是輸入的數字，m 是陣列
b的大小 (10001)。外層迴圈迭代 n 次，內層迴圈迭代 m 次進行乘法和處理進位。 - 空間複雜度: O(n + m)，其中 n 是儲存結果的字串陣列
ans的大小，m 是儲存中間計算結果的陣列b的大小。
程式碼
#include<iostream>
using namespace std;
int b[10001],k,i,j,start=0;
string ans[1002]={"1\n"};
int main(){
cin.tie(0); ios::sync_with_stdio(false);
b[1]=1;
for(k=1;k<=1000;k++){
for(j=1;j<=10000;j++)
b[j]*=k;
for(j=1;j<=9999;j++){
if(b[j]>=10){
b[j+1]+=b[j]/10;
b[j]%=10;
}
}
for(i=9999;i>=1;i--){
if(b[i]!=0){
start=i;
break;
}
}
for(i=start;i>=1;i--)
ans[k]+=b[i]+48;
ans[k]+='\n';
}
while(cin >> k){
cout << k << "!\n";
cout << ans[k];
}
}