資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚
法律大數階乘
計算機中，變數儲存在記憶體單元中。但記憶體單元的大小是固定的，因此當我們要找出像 15! 或 20! 那樣的較大值的時候，階乘值就會超過記憶體範圍，從而返回錯誤結果。
對於大數計算，我們必須使用陣列來儲存結果。結果的不同位數儲存在陣列的各個元素中。但這裡我們無法直接用陣列乘以某個數字，我們必須對結果陣列的所有位數執行手動乘法。
輸入和輸出
Input: A big number: 50 Output: Factorial of given number is: 30414093201713378043612608166064768844377641568960512000000000000
演算法
multiply(x, 被乘數)
輸入: 數字 x，以及作為陣列的大被乘數。
輸出: 乘法後的結果。
Begin carry := 0 for all digits i of multiplicand, do prod := i*x+carry i := prod mod 10 carry := prod / 10 done while carry ≠ 0, do insert (carry mod 10) at the end of multiplicand array carry := carry/10 done End
factorial(n)
輸入: 數字 n。
輸出: 找出 n 的階乘。
Begin define result array. insert 1 in the result for i := 2 to n, do multiply(i, result) done reverse the result return result End
示例
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
void multiply(int x, vector<int>&multiplicand) { //multiply multiplicand with x
int carry = 0; // Initialize carry to 0
vector<int>::iterator i;
for (i=multiplicand.begin(); i!=multiplicand.end(); i++) { //multiply x with all digit of multiplicand
int prod = (*i) * x + carry;
*i = prod % 10; //put only the last digit of product
carry = prod/10; //add remaining part with carry
}
while (carry) { //when carry is present
multiplicand.push_back(carry%10);
carry = carry/10;
}
}
void factorial(int n) {
vector<int> result;
result.push_back(1); //at first store 1 as result
for (int i=2; i<=n; i++)
multiply(i, result); //multiply numbers 1*2*3*......*n
cout << "Factorial of given number is: "<<endl;
reverse(result.begin(), result.end());
vector<int>::iterator it; //reverse the order of result
for(it = result.begin(); it != result.end(); it++)
cout << *it;
}
int main() {
factorial(50);
}輸出
Factorial of given number is: 30414093201713378043612608166064768844377641568960512000000000000
更新於: 17-6-2020
2K+ 瀏覽
廣告