GESP5级语法知识（十一）：高精度算法（一）

高精度加法：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=501;//高精度数的最长长度
//c[]=a[]+b[]:高精度加法方案一：对应位相加，同时处理进位
void h_add_1(int a[],int b[],int c[]) 
{int la=a[0]	;int lb=b[0];int lc=max(la,lb);int x=0; //进位for(int i=1;i<=lc;i++) {c[i]=a[i]+b[i]+x;x=c[i]/10;c[i]%=10;}//处理最高进位if(x>0) {lc++;c[lc]=x;}c[0]=lc;
}
//c[]=a[]+b[]:高精度加法方案二：先对应位相加，然后处理进位。 void h_add_2(int a[],int b[],int c[]) {int la=a[0]	;int lb=b[0];int lc=max(la,lb);//对应位相加 for(int i=1;i<=lc;i++) {c[i]=a[i]+b[i];}//处理进位for(int i=1;i<=lc;i++) {c[i+1]+=c[i]/10;c[i]%=10;}c[0]=(c[lc+1]!=0)? (lc+1):lc;}//把字符串转换成按位表示的整型数组int convert(string s,int n[]) {int length=s.length();//将数串s转换为 数组n[] ,并倒序存储for(int i=1;i<=length;i++) {n[i]=s[length-i]-'0';}//n[0]存储位数 n[0]=length;return length;}//删除先导0;修正位数 int trim(int n[]){int length=n[0];for(int i=n[0];i>=0;i--){//找到不是0的最高位 if(n[i]!=0){length=i;break;}}n[0]=length;return length;}void output(int n[]){int length=n[0];//0需要特别处理if(length==0) {cout<<0<<endl;return ;}//从高位向低位输出 for(int i=length;i>=1;i--){cout<<n[i];}cout<<endl;}int a[N+1];  //第一个加数 int b[N+1];  //第二个加数 int c1[N+2]; //方法一计算结果 int c2[N+2]; //方法二计算结果int main() {string s1,s2;cin>>s1>>s2;convert(s1,a);convert(s2,b);//方案一h_add_1(a,b,c1);trim(c1) ;output(c1);//方案二h_add_2(a,b,c2) ;trim(c2);output(c2);return 0;}

高精度减法：

#include<iostream>
#include<string>     //C++string类
#include<algorithm>
using namespace std;
const int N=10001;//高精度数的最长长度
//c[]=a[]-b[]:高精度减法方案一：对应位相减，同时处理借位
void h_minus_1(int a[],int b[],int c[]) 
{int lc=c[0]=a[0];int q=0; //借位 for(int i=1;i<=lc;i++) {//对应位相减，并减去上一位的借位 c[i]=a[i]-b[i]-q;if(c[i]<0) //不够减就借位 {c[i]+=10;q=1; }else q=0;}}
//c[]=a[]-b[]:高精度减法方案二：先对应位相减，然后处理进位。 void h_minus_2(int a[],int b[],int c[]) {int lc=c[0]=a[0];//对应位相减for(int i=1;i<=lc;i++) {c[i]=a[i]-b[i];}//处理借位for(int i=1;i<=lc;i++) {if(c[i]<0){//计算借位数字为负数int k=(c[i]%10)?(c[i]/10-1):c[i]/10;c[i+1]+=k;  //高位c[i]-=10*k;  //当前位 	}} }//比较高精度数字的大小，a>b为1， a<b为-1， a=b为0 int compare(int a[],int b[]){//a的位数大于b,则a比b大if(a[0]>b[0]) {return 1;}//a的位数小于b,则a比b小 if(a[0]<b[0]) {return -1;}int la=a[0];for(int i=la;i>0;i--){if(a[i]>b[i]){return 1;}if(a[i]<b[i]){return -1;}}return 0;}//把字符串转换成按位表示的整型数组int convert(string s,int n[]) {int length=s.length();//将数串s转换为 数组n[] ,并倒序存储for(int i=1;i<=length;i++) {n[i]=s[length-i]-'0';}//n[0]存储位数 n[0]=length;return length;}//删除先导0;修正位数 int trim(int n[]){int length=n[0];for(int i=n[0];i>=0;i--){//找到不是0的最高位 if(n[i]!=0){length=i;break;}}n[0]=length;return length;}//输出高精度数据 void output(int n[]){int length=n[0];//0需要特别处理if(length==0) {cout<<0<<endl;return ;}//从高位向低位输出 for(int i=length;i>=1;i--){cout<<n[i];}cout<<endl;}int a[N+1];  //被减数 int b[N+1];  //减数int c1[N+2]; //方法一计算结果 int c2[N+2]; //方法二计算结果int main() {string s1,s2;cin>>s1>>s2;convert(s1,a);convert(s2,b);//比较被减数与减数int sign=compare(a,b) ;if(sign<0){swap(a,b);}//方案一h_minus_1(a,b,c1);trim(c1) ;if(sign<0){cout<<"-";}output(c1);//方案二h_minus_2(a,b,c2) ;trim(c2);if(sign<0){cout<<"-";}output(c2);return 0;}

高精度数的比较：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=501;//高精度数的最长长度int convert(string s,int n[]) {int length=s.length();//将数串s转换为 数组n[] ,并倒序存储for(int i=1;i<=length;i++) {n[i]=s[length-i]-'0';}//n[0]存储位数 n[0]=length;return length;}//删除先导0;修正位数 int trim(int n[]){int length=n[0];for(int i=n[0];i>=0;i--){//找到不是0的最高位 if(n[i]!=0){length=i;break;}}n[0]=length;return length;}int compare(int a[],int b[]){//a的位数大于b,则a比b大if(a[0]>b[0]) {return 1;}//a的位数小于b,则a比b小 if(a[0]<b[0]) {return -1;}int la=a[0];for(int i=la;i>0;i--){if(a[i]>b[i]){return 1;}if(a[i]<b[i]){return -1;}}return 0;}int a[N+1];  int b[N+1];int main() {string s1,s2;cin>>s1>>s2;convert(s1,a);convert(s2,b);trim(a);trim(b);cout<<compare(a,b)<<endl;return 0;}

高精度数的存储与存储：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N=501;//高精度数的最长长度int convert(string s,int n[]) {int length=s.length();//将数串s转换为 数组n[] ,并倒序存储for(int i=1;i<=length;i++) {n[i]=s[length-i]-'0';}//n[0]存储位数 n[0]=length;return length;}//删除先导0;修正位数 int trim(int n[]){int length=n[0];for(int i=n[0];i>=0;i--){//找到不是0的最高位 if(n[i]!=0){length=i;break;}}n[0]=length;return length;}void output(int n[]){int length=n[0];//0需要特别处理if(length==0) {cout<<0<<endl;return ;}//从高位向低位输出 for(int i=length;i>=1;i--){cout<<n[i];}cout<<endl;}int a[N+1];  //第一个加数 int main() {string s1;cin>>s1;convert(s1,a);trim(a);output(a);return 0;}

2的乘方（高精度）

#include<iostream>
int a[100001];
using namespace std;
int main()
{int n,i,j,x,len=1;  //len=1,位数初始化为1 cin>>n;a[1]=1;             //得数初始化为1 for(i=1;i<=n;i++)   //计算n次 {x=0;            //x表示进位，初始化为0 for(j=1;j<=len;j++){a[j]=a[j]*2+x;//得数每一位都*2，再加进位 x=a[j]/10;    //计算进位a[j] %=10;    //保留个位数if(x!=0&&j==len) len++;   //计算到最高位，并且有进位，长度加1 }} for(i=len;i>=1;i--) cout<<a[i];return 0;
}