思路
用数组存储过多的数位,如357568341
下标 0 1 2 3 4 5 6 7 8
内容 1 4 3 8 6 5 7 5 3
对应的是个,十,百,千,万,十万,百万,千万,亿
即:a[0]=1,a[1]=4,a[2]=3.....a[8]=3
具体在数学运算中基本上用竖式的方法解决
例题
高精度加法
给定两个正整数(不含前导 0),计算它们的和。
输入格式
共两行,每行包含一个整数。
输出格式
共一行,包含所求的和。
数据范围
1≤整数长度≤100000
输入样例:
12
23
输出样例:
35
整数位数不超过100000位,这么大用普通的方法固然不行
这时我们就需要一些长度超过100000位的数组来储存
具体做法如下
#include<bits/stdc++.h>
using namespace std;
int main()
{
string str1,str2;//字符串读入
int a[100010],b[100010],c[100010];//数组储存
int len1,len2;
int i;
cin>>str1>>str2;
len1=str1.length();
len2=str2.length();//求字符串长度
if(len1< len2)
for(i=1; i<=len2-len1; i++)
str1="0"+str1;
else
for(i=1; i<=len1-len2; i++)
str2="0"+str2;//将两字符串位数统一
len1=str1.length();
len2=str2.length();//统计长度
for(i=0; i<=len1-1; i++)
a[len1-i]=str1[i]-'0';
for(i=0; i<=len2-1; i++)
b[len2-i]=str2[i]-'0';//倒着转化数字
int x=0;//存储进位的数字
int lenc=1;
while((lenc<=len1)||(lenc<=len2))//处理加法
{
c[lenc]=a[lenc]+b[lenc]+x;
x=c[lenc]/10;
c[lenc]%=10;
lenc++;
}
c[lenc]=x;
while(c[lenc]==0)
lenc--;
for(i=lenc; i>0; i--)
cout<<c[i];
cout<<endl;
return 0;
}
但是以上这种做法貌似过时了QAQ
大家好像都喜欢用vector(唉,时代变了T-T)
借用一下y总(yxc)大神的代码
#include<bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B,A);//如果a的位数更少进行交换
vector<int> C;
int t=0;
for (int i=0;i<A.size();i++)
{
t+=A[i];
if (i<B.size())t+=B[i];
C.push_back(t%10);
t/=10;//进位偶
}
if (t) C.push_back(t);
return C;
}//高精加模板
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');//各个位上的数字弄出来 !v!
auto C=add(A, B);
for (int i=C.size()-1;i>=0;i--)cout<<C[i];//倒着输出
cout << endl;
return 0;
}
高精减的做法类似
c[i] = (A[i] - B[i] - t) >= 0 ? (A[i] - B[i] - t) % 10 : ((A[i] - B[i] - t) + 10) % 10
借位
t = (A[i] - B[i] - t) >= 0 ? 0 : 1
以及会出现的两种可能
A-B两种情况:
A>B正常处理
A<B若B比A大,将A-B变为B-A,加上负号
需要注意的就是对于0的处理,减法对于数位的要求十分严格qwq
高精乘的做法也差不多
acwing中高精度乘法是高精乘低精(针不戳)
也就是先乘:
c[i] = (A[i] * b) % 10
再进位:
t = (A[i] * b) / 10
特立独行高精除
高精除与其他的不同,要从高位往低位算,算完还要反转商
除的过程: r = r * 10 + A[i], c[i] = r / b, r = r % b
对于前导零的处理基本使用函数即可完成