大数的阶乘
发布时间:2020-12-14 03:34:44 所属栏目:大数据 来源:网络整理
导读:首先定义一个足够长的数组。 拿10000的阶乘为例,最后的结果长度是35660位,所以我们定义一个40000个成员的数组就可以了。 int result[40000]; 其核心思想就是把计算结果每一位上的数字保存到一个数组成员中,例如: 把124保存至数组中,保存结果应该是 resu
首先定义一个足够长的数组。 拿10000的阶乘为例,最后的结果长度是35660位,所以我们定义一个40000个成员的数组就可以了。int result[40000]; 其核心思想就是把计算结果每一位上的数字保存到一个数组成员中,例如: 把124保存至数组中,保存结果应该是 result[0] 4 result[1] 2 result[2] 1 这样肯定是没有问题的,一个int型数据存放一个小于10的数是绝对不会溢出。但是处理起来就稍微有点麻烦。 把整个数组看成一个数字,这个数字和一个数相乘的时候,需要每一位都和这个乘数进行相乘运算还需要把前一为的进位加上。运算方法和小学数学是一样的,乘积的个位是当前位上应该表示的数字,10位以上的需要进位。因为乘数不可能大于10000,所以乘数和一个小于10的书相乘的时候不会大于100000,再加上前一位的进位用一个int型数据来保持这个结果就没有问题。写法如下: 每一位的计算结果有了,把这个结果的个位数拿出来放到这个数组元素上: result[x] = 结果%10; 接下来的工作就是计算出进位: 进位 = 结果 / 10; 这样一位一位的把整个数组计算一遍,最后可能还有进位,用同样的方法,把进位的数值拆成单个数字,放到相应的数组元素中。
代码如下:
#include <iostream> #define max 500000 //结果最大可保存的数的位数 using namespace std; void Factorial (int n,int ans[]){ int digit,carry,j; ans[0] = 1,digit = 1; for (int i=2;i<=n;i++){ //乘数从2开始循环到 n。 for (carry=0,j=1;j<=digit;j++){ int tmp = ans[j-1] * i + carry; ans[j-1] = tmp % 10; //取出个位数 carry = tmp / 10; //计算进位 } while (carry){ //处理进位 ans[++digit-1] = carry % 10; carry /= 10; } } for (int i=digit;i>=1;i--) //从高位到低位输出结果 cout << ans[i-1]; cout << endl; } int main (){ int n,ans[max]; while (cin >> n){ Factorial (n,ans); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |