数据结构
网络
关系型数据库管理系统
操作系统
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+ 浏览
广告