高精度算法
计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值。这种情况下，就需要进行“高精度运算”。
高精度运算首先要处理好数据的接受和存储问题，其次要处理好运算过程中的“进位”和“借位”问题。
高精度加法
用字符串输入两个数，再导入数组，然后每位相加，如果某位数字>10，则此位模10，下一位加一，最后用while循环去除前导零再输出即可。
高精度加法说白了就是两个大数之间相加，数字长度不超过10^6。注意这里是长度，而不是数据大小!但是这种数字如果放到变量中肯定是存不下的，所以我们一般用数组来存储，在 C++ 中一般用 vector 容器。如果存入数组中，就需要考虑存储顺序，究竟应该正着存还是倒着存？实际上，倒着存,是很合适的，因为对于数组来说，给一个数的后面一个数加1 很简单，但是在一个数的前面加上1 就很麻烦。就比如这张图:
如果我们 倒着存 那么 a[0]+ b[0]= 11是需要进位的。如果倒着存就可以 很快的进行进位，直接在下标1处进行自增即可;但是如果正着存，那么进位就需要到 -1 下标了，这样就不麻烦，我们算法就是为了更快解决问题，所以自然选择最合适的方式:倒着存
而高精度加法运算其实就像我们小学列竖式 一样
· 从最低位开始计算，如果两个数相加超过 10 ，就需要进位。
思想:
假如数组 a 和6分别用来存数据，c用来存储答案。
通过循环同时遍历 a、b数组，在遍历的同时，使用t来判断是否进位。将 a[i]+ b[i]的数据累加到t中。数据相加有两种结果:
· 如果 a[i] + b[i]<10 ，直接将 t放入c，让 t /= 10 ，以便下一次计算。
· 如果 a[i]+b[i]=10，将t%10=0放入c，让t/= 10
· 如果 a[i] + b[i] >10 ，将t%10 放入c数组，将 t/= 10 作为 进位，下一次t初始就是1.
就拿这张图理解:
这里就是对最后一位进行运算时，所做的进位操作。
而 t%10 最终的结果肯定在0~ 9之间，如果t< 10 小，那么 %10 不会对运算结果产生影响;对于t> 10的情况，则会将结果控制到0~9之间。
模板：
vector<int> Add(vector<int> &A, vector<int> &B)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size())
t += A[i];
if (i < B.size())
t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t)
C.push_back(1);
return C;
}
简单讲一下模板:
a和b是倒着存的，并同步遍历，由于数据大小不确定，所以只要a和b有一个符合条件，则就可以被t累加，符合条件的就加上该位置的元素，否则就不处理，默认为0。每次将 t%10 尾插到结果数组c中，然后将 t/10，以便下次运算，如果有进位，那么下次t的初值就为1。最后循环结束后，再判断一下是否还有进位没进，如果有进位，则将1尾插到c中。
模板题+详解
题目:
给定两个正整数(不含前导 0)，计算它们的和。
输入格式:
共两行，每行包含一个整数。
输出格式:
共一行，包含所求的和。
数据范围:
< 整数长度 < 100000
输入样例:
12
23
输出样例
35
#include <iostream>
#include <vector>
using namespace std;
const int N=1e6+10;//定义常变量方便改范围
vector<int> Add(vector<int> &A,vector<int> &B)//高精度加算法模板
{
vector<int> C;//定义C用于返回add的结果
int t=0;//存放进位
for(int i=0;i<A.size()||i<B.size();i++)//A和B全都运算完才结束
{
if(i<A.size())
t+=A[i];//要是没超过A的长度就加上A当前位的数据
if(i<B.size())
t+=B[i];//要是没超过B的长度就再加上B当前位的数据
C.push_back(t%10);//刚刚两次相加模拟了两数相加，把个位存放到C
t/=10;//把十位存回给t，用作下一位数的进位
}
if(t)
C.push_back(1);//要是全都结束了还有进位没用完就再补上一个1
return C;//返回Add的结果
}
int main()
{
string a,b;//用于输入两个大数
vector<int> A,B;//用于存放两个大数
cin>>a>>b;//输入两个大数
for(int i=a.size()-1;i>=0;i--)
A.push_back(a[i]-'0');//倒序存放大数
for(int i=b.size()-1;i>=0;i--)
B.push_back(b[i]-'0');//倒序存放大数
auto C=Add(A,B);//auto用于自动推导变量类型，使代码更简洁
for(int i=C.size()-1;i>=0;i--)
printf("%d",C[i]);//由于之前倒序运算，此时倒序输出结果会变正序
return 0;
}
auto用于自动推导变量类型，使代码更简洁
高精度减法
用字符串输入两个数，再导入数组，判断是否后数比前数，如果是则输出负号再交换数组。然后按位相减不够借1，最后用while循环去除前导零再输出即可。
高精度减法是对大整数的减法，数据长度不超过 10^6
我们讲解的 高精度减法是基于对正整数的算法 ，如果计算的是负数，那么需要微调。
高精度减法使用的存储方式为 倒序存储 。还是和竖式计算十分相似。
模板:
bool cmp(vector<int> &A,vector<int> &B)//比较A和B大小，若A>=B则返回true
{
if(A.size()!=B.size())
return A.size()>B.size();//若长度不同，则谁长谁的值就更大
for(int i=A.size()-1;i>=0;i--)
{
if(A[i]!=B[i])
return A[i]>B[i];//若长度相同，则逐位比较
}
return true;//若都相同，也返回true
}
vector<int> sub(vector<int> &A,vector<int> &B)//高精度减算法模板
{
vector<int> C;//定义C用于返回sub的结果
int t=0;//存放进位
for(int i=0;i<A.size();i++)//A运算完了才结束
{
t=A[i]-t;//先让A[i]减去进位的数，结果存回给t
if(i<B.size())
t-=B[i];//再在B的长度范围内，减去B[i]，存回t
C.push_back((t+10)%10);//临时存放当前运算位结果的绝对值
if(t<0)
t=1;//要是当前运算结果是负数，表示要借1位，所以t更新为1
else
t=0;//否则没进位，t更新为0
}
while(C.size()>1&&C.back()==0)
C.pop_back();//删除多余的0
return C;//返回sub的结果
}
讲一下这块是什么意思:
while(c.size()>1&&c.back()==0)
{
c.pop_back();
}
由于我们的数据时是倒着存放的，而两个数相减结果为0，就会在该位填上0。比如 666 ~ 665 倒着存储并在经过上方的高精度运算后，c中结果为 100 ，所以这种情况就需要去前导0。上面的操作就是检查长度是否至少为1，且c尾部是否为0。
模板题+详解
题目：
给定两个正整数(不含前导0)，计算它们的差，计算结果可能为负数。
输入格式:
共两行，每行包含一个整数。
输出格式：
共一行，包含所求的差。
数据范围:
<整数长度 < 105
输入样例:
32
11
输出样例：
22
#include<iostream>
using namespace std;
bool cmp (vector<int> &A, vector<int> &B){ //用来比较A,B的大小
if(A.size() != B.size())//若A和B的位数不同
{
return A.size() > B.size(); //则可以直接比较，位数多的数大
}else//若A和B的位数相同
{
for(int i = A.size() - 1; i >= 0; i--)
{ //比大小，需将逆序输入的数再次逆序，然后从最高位开始往后，分别对两个数的每一位比较大小
if(A[i] != B[i]) //如果某位上的数字A和B的不相等
return A[i] > B[i]; //就可以直接比较A和B在那一位上的数的大小
}
}
return true;
}
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;//定义C用于返回sub的结果
int t = 0; //借位
for(int i = 0; i < A.size(); i++)
{
t = (A[i] - t); //如果有借位，则在减法刚开始时先减去借位数t
if(i < B.size())
t = t - B[i]; //如果B还有位数没有减的话
C.push_back((t + 10) % 10);//(t+10)%10作为某一位上相减的结果,+10为了防止出现负数
if(t < 0) //某一位上不够减
t = 1; //向后面借1
else
t = 0;
}
while(C.size() > 1 && C.back() == 0){ //while循环去掉前导零
//C.size() > 1，说明如果结果就一位数，不用去除前导零 C.back() == 0，容器最后一个的位数是零的话
C.pop_back(); //去掉容器的最后一个位数
}
return C;
}
int main(){
vector<int> A, B;//A，B用于存放两个大数
string a, b;//用于输入两个大数
cin >> a >> b; //输入两个大数
//逆序输入容器 ，因为逆序好处理进制
for(int i = a.size() - 1; i >= 0; i--)
A.push_back(a[i] - '0');//a[i]-'0'将字符串a中字符形式的数字转换成真实数字值。通过减去字符 '0' 的ASCII码，获得对应的数字值。
for(int i = b.size() - 1; i >= 0; i--)
B.push_back(b[i] - '0');
if(cmp(A, B))//比大小，若A大于B
{
auto C=sub(A, B); //说明是大数减去小数，A直接减B
for(int i = C.size() - 1; i >= 0; i--) //逆序输入，所以逆序输出
cout << C[i];
}
else//A小于B
{
cout << "-"; //说明是小数减去大数，要在前面添加负号
auto C=sub(B , A); //用大数B减小数A后在前面加负号即可
for(int i = C.size() - 1; i >= 0; i--) //逆序输出
cout << C[i];
}
return 0;
}
高精度乘法
导入方法与前面一样，导入后按乘法竖式思路相乘，再按常规思路进位。最后去除前导零就行了。
我们这里讲的高精度乘法为大整数 x 小整数，大整数长度不超过 10^6 ，小整数数据范围不超过10^9 高精度乘法就不只是单单的数学计算了，这里有些不同。首先大数 a 倒序存储到 vector 中，这样也是为了方便进位，首先设定进位t。再看一个例子，了解一下进位规则:
就比如这个例子，大数α 的单独位数直接和b相乘，将结果累加到t中，将乘得的结果 %10 存放到c数组中，然后 t/= 10，将进位去掉一位 。其实这里的进位也很好理解，无非就是要让t到下一位，而下一位是当前位次 x10 ，所以t要前进一位就要 /10.
这就是高精度乘法的运算规则，也不需要分类讨论，就记住这个规律就好。虽然运算方法和我们从前计算方式有些不同，但是最终计算结果是相同的。
模板
vector<int> mul(vector<int> &A,int b)//高精度乘算法模板
{
vector<int> C;//定义C用于返回mul的结果
int t=0;//存放进位
for(int i=0;i<A.size()||t;i++)//A运算完了并且还要t为0才结束
{
if(i<A.size())
t+=A[i]*b;//每一位上进行乘法,并加上进位数t
C.push_back(t%10);//即保留乘出结果的个位数到对应位上
t/=10;//算出进位数t
}
return C;//返回mul的结果
}
模板题+详解
描述:
给定两个非负整数(不含前导0)A和 B，请你计算 A xB的值。
输入格式:
共两行，第一行包含整数 A，第二行包含整数 B
输出格式:
共一行，包含 A x B 的值。
数据范围:
1 <= A的长度 <= 100000
0<=B<=10000
输入样例:
2
3
输出样例:
6
#include <iostream>
#include <vector>
using namespace std;
const int N=1e6+10;//定义常变量方便改范围
vector<int> mul(vector<int> &A,int b)//高精度乘算法模板
{
vector<int> C;//定义C用于返回mul的结果
int t=0;//存放进位
for(int i=0;i<A.size()||t;i++)//A运算完了并且还要t为0才结束
{
if(i<A.size())
t+=A[i]*b;//每一位上进行乘法,并加上进位数t
C.push_back(t%10);//取末尾数字作为当前结果压入栈中 即保留乘出结果的个位数到对应位上
t/=10;//算出进位数t
}
return C;//返回mul的结果
}
int main()//调用算法模板测试
{
string a;//用于输入一个大数
int b; //用于输入一个整数
vector<int> A;//用于存放一个大数 和上面不同，这里b是int型，故不用压入容器
cin>>a>>b;//输入两个数相乘
for(int i=a.size()-1;i>=0;i--)
A.push_back(a[i]-'0');//倒序存放大数
vector<int>C=mul(A,b);//调用高进度乘算法
for(int i=C.size()-1;i>=0;i--)
printf("%d",C[i]);//输出mul的结果
return 0;
}
在C++中，可以在同一个作用域内多次声明同一个类型的变量，只要每次声明的变量名是唯一的。因此，虽然vector< int >C在前面已经定义过了，但是在 vector< int >C=mul(A,B); 这行代码中又声明了一个同样类型的新变量C，这是完全允许的
高精度除法
我们这里讲的高精度除法为大整数 / 小整数，大整数长度不超过 10^6 ，小整数数据范围不超过10^9我们人在做除法时，会先看第一位，如果第一位大于除数，则在结果相应位置写下除以除数之后的数据，否则看下一位，这样以此类推。所以人算除法第一位都是有效数据位。
但是对于计算机不是这样，计算机则会默认从第一位算起，举个例子，比如 1234/11:如果以人的角度，第一位肯定为1，但是计算机,会从第一位开始看，第一位为 0。而除法可能产生余数 ，所以还需要一个变量来记录余数。有了这个概念，我们先看模板:
我们的模板是倒着存数据的，但是高精度除法是可以正着存的，因为除法需要从第一位开始除，所以正着存完全没有问题，但是之后可能会有高精度的混合运算，所以我们这边保持一致，也是倒着存
模板
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0)
C.pop_back();
return C;
}
看完模板之后，我们对里面的一些代码进行讲解
第1块:
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
首先看这一步，高精度除法比另外三个算法难的原因就是出在这一步上，因为运算规则可能不太好理解。
我们知道，如果要做除法运算，那么就需要一定的 补位，r*18+ A[i]就是在补位，因为下一次的需要被除的数据，就是第一次相除后的余数 x10 ，然后加上当前元素 A[i]。而除之后的结果就是r/6，每次除完都有相应的余数，所以，r%=b。下面我们就用一张图演示一下
通过这张图，我们就可以完美的解释代码究竟在干什么，实际上这就是一个计算的过程，过程涉及补位，相除，得余数等操作…而最后，在进行完所有的操作之后，其实就是最终的余数。
第2块:
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0)
C.pop_back();
这两步就是在去前导 0上面的图中我们也可以发现，高精度除法也是有前导0的，但是对于顺序表来说，前导 0不太好去，所以就逆置一下再去前导 0最后倒着输出 c即可。
模板题+详解
描述:
给定两个非负整数(不含前导0)A，B 请你计算 A/B 的商和余数。
输入格式:
共两行，第一行包含整数 A，第二行包含整数 B
输出格式:
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围:
1< =A的长度< =100000
1<=B<=10000
B 一定不为 0
输入样例:
7
2
输出样例：
3
1
#include <iostream>
#include <vector>
#include <algorithm>//调用reverse函数
using namespace std;
const int N=1e6+10;//定义常变量方便改范围
vector<int> div(vector<int> &A,int b,int &r)//高精度除算法模板
{
vector<int> C;//定义C用于返回div的结果
r=0;//存放余数
for(int i=A.size()-1;i>=0;i--)//由于倒序，所以从最高位运算
{
r=r*10+A[i];//当前运算时的被除数
C.push_back(r/b);//算商
r%=b;//算余数
}
reverse(C.begin(),C.end());//此时结果为正序，把他反转成倒序 //逆序，是为了方便去除前导零
//不逆序的话，从前往后去除前导零不方便
//其一是因为vector没有如pop_back类似的方法去去除第一个位置的元素
// 其二是因为先去除前面的数，那后面的数也要相应地整体往前移动,过于复杂
while(C.size()>1&&C.back()==0)
C.pop_back();//去除前导零
return C;//返回div的结果
}
int main()//调用算法模板测试
{
string a;//用于输入一个大数
int b; //用于输入一个整数
int r; //用于存放余数
vector<int> A;//用于存放一个大数
cin>>a>>b;//输入两个数相除
for(int i=a.size()-1;i>=0;i--)
A.push_back(a[i]-'0');//倒序存放大数
auto C=div(A,b,r);
for(int i=C.size()-1;i>=0;i--)
printf("%d",C[i]);//前面逆序了，故这里逆序输出div的结果
cout<<endl<<r<<endl;//输出余数 这行代码的意思：先输出一个换行，然后输出变量 r 的值，再输出一个换行
return 0;
}