大数问题

这学期开了算法课,老师课上出了一个问题,就是求10000的阶乘。

说实话,第一次听到这个问题我很快就想到了去年实验室纳新时的一道笔试题

那道题是这么说的,写一个函数求两个很大很大很大的整数的和(感觉真的暴力)。

当时我大一,c语言刚自己看完,完全没有思路,甚至脑子里面都没有常用数据类型的范围这种概念,后来问了下出题的学长,他就只告诉我把这两个数存到数组里面,然后处理一下进位就行了。

他说的很轻松…

后来就查了一下,发现网上有很多答案,有用BigInteger的,还有用python直接算的…

具体思路

很多语言的int类型的最大值都是2147483647,当然也有什么long类型,long long类型,unsigned long long类型。

这些类型能存的数一个比一个大,但是都存不下这个10000的阶乘。

但是如果你问10000的阶乘有几位,就未必有这么大了,网上也有大佬推导出了这个阶乘的位数,可惜我没有看懂…

我们可以定义一个数组,把我们计算得到的数一位一位的存到数组中。在计算的过程中处理好进位就好了。

假设已经得到的结果是5040,这是7的阶乘,在数组中实际存储的是:

0 4 0 5

下面它要乘8了,按照我们正常乘法的顺序,先用8和该数的个位相乘,这里也正好是数组中的第一位,结果是0,这时还将0写到数组第一位即可。

0

用8乘第二位4时,结果是32,这时候就需要考虑进位了,我们先将32的个位2取出来写到数组第二个位置上,然后将32的最高位3保存起来。

0 2

然后用8乘第三位,结果是0,再加上上一步的进位3,写到数组第三个位置上。

0 2 3

用8乘最后一位,结果是40,同样的方法,先将个位0写在第四位,剩下进位4,这时的数组就要扩充一位来放这个最后的进位4。

0 2 3 0 4

但是这里要考虑全面,如果最后剩下的进位不是一位数,而是很多很多位数,这时数组扩充的位数就不是1了,这时可以用一个循环将最后的进位拆开,同时扩充数组,直到没有进位。

很明显,这里的计算得到的结果是倒序存储的,所以输出最后结果的时候只需要倒序输出一下数组就行了。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#define RESULTLEN 50000

using namespace std;


int main()
{
int result[RESULTLEN];//结果数组,50000位
int temp = 0;//每步计算后的临时结果
int carry = 0;//进位
int result_len = 1;//结果的位数

result[0] = 1;

for(int i = 1; i <= 10000; i++)//每次与结果数组相乘的数
{
carry = 0; //每次与一个数相乘过后进位都清零
for(int j = 0; j < result_len; j++)//循环结果数组的每一位,但是是倒序循环
{
temp = carry + result[j] * i; //临时结果就是结果数组中的第j位与i的乘积加上上一次的进位
result[j] = temp % 10; //当前位的数值成为临时结果的个位数
carry = temp / 10; //计算进位,注意这个进位到后面是一个相当大的数字
}

while(carry) //将进位拆开写到对应的位置上
{
result[result_len++] = carry % 10;
carry = carry / 10;
}
}

//输出
for(int i = result_len - 1; i >= 0; i--)
{
cout << result[i];
}

cout << endl ;
cout << "10000!的长度为:"<< result_len << endl;

}

结果: