大数问题

大数是指计算的数值非常大或者对运算的精度要求非常高，用已知的数据类型无法精确表示的数值。

大数问题主要有以下四种：

==================================

1. 大数相加

2. 大数相乘

3. 大数阶乘

4. 大数幂乘

==================================

下面我们一起解决这四种问题。

Problem 1 大数相加

一般的int，long等类型无法精确表达数值。

我们就考虑以字符串的形式读入这两个数，利用vector来表示这两个数值，

代码：

 1 string s1, s2;
 2 cin>>s1>>s2;
 3 int i;
 4 vector<int> v1(s1.size()), v2(s2.size());
 5 for(i = 0; i < s1.size(); i++)
 6 {
 7     v1[i] = s1[i] - '0';
 8 }
 9 for(i = 0; i < s2.size(); i++)
10 {
11     v2[i] = s2[i] - '0';
12 }

利用vector的空间可以无限扩展，因此我们利用vector来模拟计算这两个数的相加。

根据加法规则我们可以知道，个位与个位相加，十位与十位相加...

代码：

 1 vector<int> f(vector<int> v1, vector<int> v2)
 2 {
　　　　#将两个数字的位置倒过来，个位数字放在最前面，例如：123，倒过来即为321
 3     reverse(v1.begin(),v1.end());
 4     reverse(v2.begin(),v2.end());
 5     int maxsize = v1.size();
　　　　#比较两个数字的位数，找到最长的
 6     if(v2.size() > maxsize)
 7     {
 8         maxsize = v2.size();
 9     }
10     vector<int> v3(maxsize);
　　　　#记录每一位计算的进位
11     int carry = 0;
12     int i;
13     for(int i = 0; i < maxsize; i++)
14     {
15         int t = carry;
16         if(i < v1.size())
17             t = t + v1[i];
18         if(i < v2.size())
19             t = t + v2[i];
　　　　　　#当相同位置上的数字相加超过10时，应该向高位进位
20         carry = t / 10;
21         v3[i] = t % 10; 
22     }
　　　　#若最高位相加之后，需要进位，那么我们需要扩展vector
23     if(carry > 0)
24         v3.push_back(carry);
　　　　#最后将vector倒置，可以得到最终的相加结果
25     reverse(v3.begin(),v3.end());
26     return v3;
27 }

Problem 2 大数相乘

例如：

位置： 4　　3　　2　　1　　0

数值1：　　 4　　3　　2

数值2：　　 * 4 5

------------------------------------

结果：　　20 15　 10

　　　　 16 　12　 8

-----------------------------------

　　　　16　 32　　23　 10

-----------------------------------

　　1 9 　 4 　　4　 0

从上面的例子中我们可以看出位置i和位置j的结果放在i+j的位置，最后再依次进行进位操作。

代码：

这里要注意初始结果申请的空间，最后在输出的时候需要进行处理。

 1 vector<int> m(vector<int> v1, vector<int> v2)
 2 {
 3     reverse(v1.begin(),v1.end());
 4     reverse(v2.begin(),v2.end());
 5     int maxsize = v1.size();
 6     if(v2.size() > maxsize)
 7         maxsize = v2.size();
 8     maxsize *= 2;
 9     vector<int> v3(maxsize, 0);
10     int carry = 0;
11     for(int i = 0; i < v1.size(); i++)
12         for(int j = 0; j < v2.size(); j++)
13         {
14             v3[i+j] += v1[i]*v2[j];
15         }
16     for(int i = 0; i < v3.size(); i++)
17     {
18         if(v3[i] >= 10)
19         {
20             v3[i+1] += v3[i]/10;
21             v3[i] = v3[i] % 10;
22         }
23     }
24     reverse(v3.begin(),v3.end());
25     
26     return v3;    
27 }

输出处理：因为开始申请的空间可能有部分没有用到，但是在倒置的时候最前面可能出现多个0，利用flag记录非0的起点。

代码：

int flag = 0;
while(v4[flag] == 0)
    flag++;
for(i = flag; i < v4.size(); i++)
    cout<<v4[i];
cout<<endl;

Problem 3大数阶乘

一般阶乘很快就会超过int的表达范围，因此同样采用上面大数相乘的思想来计算大数阶乘，这里需要注意的是开始输入的n不是一个大数，但是随着计算，结果会越来越大。

利用循环来计算大数阶乘。

代码：

 1 vector<int> m(vector<int> v1, vector<int> v2)
 2 {
 3     reverse(v1.begin(),v1.end());
 4     reverse(v2.begin(),v2.end());
 5     int maxsize = v1.size();
 6     if(v2.size() > maxsize)
 7         maxsize = v2.size();
 8     maxsize *= 2;
 9     vector<int> v3(maxsize, 0);
10     int carry = 0;
11     for(int i = 0; i < v1.size(); i++)
12         for(int j = 0; j < v2.size(); j++)
13         {
14             v3[i+j] += v1[i]*v2[j];
15         }
16     for(int i = 0; i < v3.size(); i++)
17     {
18         if(v3[i] >= 10)
19         {
20             v3[i+1] += v3[i]/10;
21             v3[i] = v3[i] % 10;
22         }
23     }
24     reverse(v3.begin(),v3.end());
25     
26     return v3;    
27 }
28 
29 vector<int> intTovector(int x)
30 {
31     vector<int> v;
32     while (x)
33     {
34         v.push_back(x%10);
35         x /= 10;
36     }
37     reverse(v.begin(),v.end());
38     return v;
39 }
40 
41 vector<int> pre(vector<int> v)
42 {
43     vector<int> v1;
44     int flag = 0;
45     while(v[flag] == 0)
46         flag++;
47     for(int i = flag; i < v.size(); i++)
48         v1.push_back(v[i]);
49     return v1;
50 }
51 
52 void p(vector<int> v)
53 {
54     for(int j = 0; j < v.size(); j++)
55             cout<<v[j];
56         cout << endl;
57 }
58 
59 vector<int> jiecheng(int n)
60 {
61     vector<int> v1(1,1);
62     if(n == 1)
63         return v1;
64     vector<int> v2(1,2);
65     if(n == 2)
66         return v2;
67     vector<int> v3 = v2;
68     for(int i = 3; i <= n; i++)
69     {
70         vector<int> t1 = intTovector(i);
71         p(t1);
72         vector<int> t2 = v3;
73         p(t2);
74         v3 = pre(m(t1,t2));
75         p(v3);
76         cout << "===============" <<endl;
77     }
78     return v3;
79 }

Problem 4大数幂乘

一般阶乘很快就会超过int的表达范围，因此同样采用上面大数相乘的思想来循环计算大数阶乘。

代码：

 1 vector<int> micheng(int n, int s)
 2 {
 3     vector<int> v = intTovector(n);
 4     for(int i = 1; i < s; i++)
 5     {
 6         v = pre(m(v,intTovector(n)));
 7         
 8     }
 9     return v;
10 }