C++ 高精度算法
📋 个人简介
🎉大家好，我是3月份新人榜排名第三的 ༺Blog༒Hacker༻
💬支持我：点赞👍+收藏⭐️+留言📝
🌺格言：༺永做优质༒programmer༻
📣高精度算法
🔥由于计算机数据范围有一定限制,
• ❄️整型int表达范围是(-2 147 483 648 ~ 2 147 483 647), 约为几十亿.
• ❄️实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数
• ❄️因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算.
🔥高精度计算通用方法
❄️ 高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位
❄️ 表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上
❄️如数:3485(三千四百八十五)，表达在数组a[10]上情况是:
下标 0 1 2 3 4 5 6 7 8 9
内容 5 8 4 3 0 0 0 0 0 0
说明：个位 十位 百位 千位
❄️另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般还要用变量存储该数的位数
❄️具体在计算加减乘除时方法就是小学时采用的列竖式方法．
注：高精度计算时一般用正数，对于负数，通过处理符号位的修正．
🔥例一
问题描述 ：求两个不超过200位的非负整数的和。输入数据 有两行，每行是一个不超过200位的非负整数，没有多余的前导0。输出要求 一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。 输入样例2222222222222222222233333333333333333333输出样例55555555555555555555☄️【问题分析】
✨1)
用整型数组来存放大整数
an[0]存放个位数，an[1]存放十位数，an[2]存放百位数……
✨2）
模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。
用 an1[201]保存第一个数，用 an2[200]表示第二个数，然后逐位相加，相加的结果直 接存放在an1中。要注意处理进位。
💯CODE
#include#includeusing namespace std;int main(){ char a1[201],b1[201]; int a[210],b[210],c[210],lena,lenb,lenc,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); cin>>a1; cin>>b1; lena=strlen(a1); lenb=strlen(b1); for(i=0;i<=lena-1;i++) a[i]=a1[lena-i-1]-48;//‘0’的ASCII为48 for(i=0;i<=lenb-1;i++)b[i]=b1[lenb-i-1]-48;lenc=lena>lenb?lena:lenb; x=0; for(i=0;i<=lenc-1;i++) { c[i]=a[i]+b[i]+x; x=c[i]/10; c[i]=c[i]%10; } if(x!=0) { c[lenc]+=x; lenc++; } for(i=lenc-1;i>=0;i--) cout<<c[i]; cout<<endl; return 0; }🔥例2：大整数减法
问题描述
求2个大的正整数相减的差
输入数据
第1行是被减数a，第2行是减数b。数据不超过200个字符
输出要求
输出是相应的整数差
输入样例 9999999999999999999999999999999999999 9999999999999 输出样例 9999999999999999999999990000000000000【分析】类似加法，用竖式求减法。需要注意：被减数必须比减数大，同时需要处理借位。💯CODE
#include#includeusing namespace std;int main(){ char a1[201],b1[201],t[201]; int a[210],b[210],c[210],lena,lenb,lenc,lent,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); cin>>a1; cin>>b1; lena=strlen(a1); lenb=strlen(b1); if(lena<lenb || (lena==lenb && strcmp(a1,b1)<0)) { strcpy(t,a1); strcpy(a1,b1); strcpy(b1,t); cout<<'-'; lent=lena; lena=lenb; lenb=lent; }for(i=0;i<=lena-1;i++) a[i]=a1[lena-i-1]-48;//‘0’的ASCII为48 for(i=0;i<=lenb-1;i++) b[i]=b1[lenb-i-1]-48; lenc=lena; for(i=0;i<=lenc-1;i++) { if(a[i]<b[i]) { a[i]+=10; a[i+1]--;} c[i]=a[i]-b[i]; } while(c[lenc-1]==0 && lenc>0) lenc--; for(i=lenc-1;i>=0;i--) cout<<c[i]; cout<<endl; return 0; }🔥例三：大整数乘法
问题描述
求两个不超过200位的非负整数的积。
输入数据
有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
输出要求
一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
输入样例 12345678900 98765432100 输出样例 1219326311126352690000【解题思路】
用unsigned an1[200]和unsigned an2[200]分别存放两个乘数，用aResult[400]来存放积。计算的中间结果也都存在aResult中。aResult长度取400是因为两个200位的数相乘，积最多会有400位。an1[0], an2[0], aResult[0]都表示个位。
一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第i+j位上。这里i, j都是从右往左，从0开始数。
计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。
💯CODE
# 💯CODE```cpp#include#includeusing namespace std;int main(){ char a1[201],b1[201],t[201]; int a[210],b[210],c[210],lena,lenb,lenc,lent,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); cin>>a1; cin>>b1; lena=strlen(a1); lenb=strlen(b1); if(lena<lenb || (lena==lenb && strcmp(a1,b1)<0)) { strcpy(t,a1); strcpy(a1,b1); strcpy(b1,t); cout<<'-'; lent=lena; lena=lenb; lenb=lent; }for(i=0;i<=lena-1;i++) a[i]=a1[lena-i-1]-48;//‘0’的ASCII为48 for(i=0;i<=lenb-1;i++) b[i]=b1[lenb-i-1]-48; lenc=lena; for(i=0;i<=lenc-1;i++) { if(a[i]<b[i]) { a[i]+=10; a[i+1]--;} c[i]=a[i]-b[i]; } while(c[lenc-1]==0 && lenc>0) lenc--; for(i=lenc-1;i>=0;i--) cout<<c[i]; cout<<endl; return 0; }