高精度四则运算

算法学习的第三天

算法学习之高精度四则运算

高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。

1、高精度存储

我们使用数组来存储高精度数字，并且采用倒序的方法，如下图。

计算过程中常常涉及到进位，如果把高位放在第一位要频繁的移动，所以我们采用倒序的方法将数字存储在数组里面。

2、 高精度加法

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 vector<int> add( vector<int> &A,vector<int> &B ) //引入两个vector （使用vector是因为vector自带size函数，不用另创建数组存储数组大小）
 8 {
 9     vector<int> C; // C为计算结果
10     
11     if(A.size() < B.size()) return add(B,A); //如果A的长度小于B的长度 就swap一下。
12     
13     int t = 0;//引用进位
14     for(int i = 0 ; i < A.size(); i++) // A.size()一定大于B.size()
15     {
16         t += A[i];
17         if(i < B.size())  t += B[i];// A.size()一定小于B.size()
18         C.push_back(t % 10); //C为t进位的余数
19         t /= 10; //t当前为整数
20     }
21     if (t) C.push_back(1); //如果循环完毕t仍为1，那么C最高位再进1
22     return C;
23 }
24 
25 int main()
26 {
27     string a,b;
28     vector<int> A,B;
29     
30     cin >> a >> b; // 输入两个做高精度加法的数字
31     for(int i = a.size() -1 ; i >=0 ;i--) A.push_back(a[i] - '0'); //将a倒序存入vectorA中
32     for(int i = b.size() -1 ; i >=0 ;i--) B.push_back(b[i] - '0'); //将b倒叙存入vectorB中
33     
34     auto C = add(A,B); //auto 可以写成vector<int> add(A,B)引用上面写的函数
35     
36     for(int i = C.size() -1 ; i >= 0 ;i--) printf("%d",C[i]); //逐位输出并拼接
37     return 0;
38 }

3、高精度减法

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 vector<int> mul(vector<int>&A,int B)
 8 {
 9 vector<int> C;
10 
11 int t = 0;
12 for(int i = 0 ;i < A.size() || t ; i++) // i 小于A的个数或者t的大小
13 {
14 if(i < A.size()) t += A[i] *B; //模拟乘法运算
15 C.push_back( t % 10); //保留结果
16 t /= 10; //中间数减去结果，只保留进位
17 }
18 return C;
19 }
20 
21 int main()
22 {
23 string a;
24 int b ;
25 vector<int> A,C;
26 cin >> a >>b;
27 for(int i = a.size() - 1; i >= 0 ;i --) A.push_back(a[i] - '0');
28 
29 //防止存在前导0的情况
30 if(b) C=mul(A,b); //如果b不为0，就做乘法运算
31 else C.push_back(0); //如果b为0，则结果为0
32 
33 for(int i = C.size() - 1; i >= 0 ;i --) printf("%d",C[i]);
34 return 0;
35 
36 }

 4、高精度乘法

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 
 5 using namespace std;
 6 
 7 vector<int> mul(vector<int>&A,int B) //引入高精度A和低精度B
 8 {
 9 vector<int> C;
10 
11 int t = 0; //进位
12 for(int i = 0 ;i < A.size() || t ; i++) // i 小于A的个数或者t的大小就继续
13 {
14 if(i < A.size()) t += A[i] *B; //模拟乘法运算
15 
16 C.push_back( t % 10); //保留运算结果
17 t /= 10; //中间数减去结果，只保留进位
18 }
19 return C;
20 }
21 
22 int main()
23 {
24 string a;
25 int b ;
26 vector<int> A,C; //提前定义 C
27 
28 cin >> a >>b;
29 for(int i = a.size() - 1; i >= 0 ;i --) A.push_back(a[i] - '0');
30 
31 //防止存在前导0的情况
32 if(b) C=mul(A,b); //如果b不为0，就做乘法运算
33 else C.push_back(0); //如果b为0，则结果为0
34 
35 for(int i = C.size() - 1; i >= 0 ;i --) printf("%d",C[i]);
36 return 0;
37 
38 }

 5、高精度除法

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 vector<int> div(vector<int> &A , int b ,int &r) //A是除数 b是被除数 r是余数  加&是引用 引用速度会更快一点，不加速度会慢一点
 9 {
10     vector<int> C; //定义商
11     r= 0 ; //刚开始余数定义为0
12     for(int i = A.size() - 1; i >= 0 ;i--) //倒着读入
13     {
14         r = r * 10 + A[i]; //模拟除法运算结果 每做一次除法，都要把余数向前一位，把应作除的位数直接拉下来
15         C.push_back(r / b); //存入计算结果
16         r %= b;
17     }
18     reverse(C.begin(),C.end()); //倒着计算完后反转一下 如果不理解的可以试着注释一下再运行
19     while(C.size() > 1 && C.back() == 0) C.pop_back(); //删除前导0
20     return C;
21 }
22 int main()
23 {
24     string a;
25     int b;
26     vector<int> A,C;
27     
28     cin >>a >>b;
29     for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
30     
31     int r ;
32     C = div(A,b,r);
33     for(int i = C.size() - 1; i >= 0; i--) printf("%d",C[i]); //输出商
34     cout << endl << r; //输出余数
35     return 0;
36 }