简单高精度入门总结（无除法）

2019-11-08 00:47:09

字体：大中小

来源：转载

供稿：网友

高精度算法入门总结

之前写题目的时候看过一些博客，但有些减法写的考虑情况不全，所以自己决定总结一下。

简单高精度加法（codevs 天梯黄金）

由于数据大小限制所以计算高精度大都采用char数组的形式来读入数据，然后对每一位模拟计算并向前进位。大致思路：用char数组读入数后将其反向放入int型数组，然后从第一位开始计算，最后倒序输出结果（其中要注意当为最后一位相加时需进位时，len要++。 code：

#include<iostream>#include<stdio.h>#include<fstream>#define maxn 5001using namespace std;int add(int x[],int y[],int z[],int len){ int i,j,r; for(j=0;j<len;j++) { z[j]+=x[j]+y[j]; for(i=j;i<len;i++) { if(z[i]>=10) { z[i+1]++; z[i]-=10; if(z[len]>0) len++; if(z[i+1]<10) break; } } } return len;}void output(int z[],int len){ for(int i=len-1;i>=0;i--) cout<<z[i];}void init(int x[],string str,int len){ for(int i=0;i<len;i++) { x[len-i-1]=str[i]-'0'; }}int main(void){ string str1,str2; int a[maxn]={0},b[maxn]={0},z[maxn]={0}; int la,lb,len; cin>>str1>>str2; la=str1.size(); lb=str2.size(); init(a,str1,la); init(b,str2,lb); if(la>lb) { len=add(a,b,z,la); } else len=add(b,a,z,lb); output(z,len);}

简单高精度减法（codevs 天梯黄金）

这里只写两个整数之间的减法，负数的话再判断第一位读入的是否是‘-’。大致思路：减法大致情况同加法一致，即进位改为借位，唯一不同的地方就是必须用绝对值大数减小数，这里分两种情况，一种是len1>len2,一种是len1==len2,此时我们采用字符串函数strcmp()来判断两个数值的大小。 code：

#include<iostream>#include<stdio.h>#include<string.h>#define maxn 501using namespace std;void init(char a[],int x[],int len){ for(int i=0;i<len;i++) { x[i]=a[len-i-1]-'0'; }}void sub(int x[],int y[],int len,bool on){ for(int i=0;i<len;i++) { x[i]-=y[i]; if(x[i]<0) { x[i+1]--; x[i]+=10; } if(x[len-1]==0) len--; } for(int i=len-1;i>=0;i--) { if(x[i]==0) len--; else break; } if(on==1) x[len-1]=-x[len-1]; for(int i=len-1;i>=0;i--) { cout<<x[i]; }}int main(void){ int x[maxn]={0},y[maxn]={0}; char a[maxn]={0},b[maxn]={0}; cin>>a>>b; int la=strlen(a),lb=strlen(b); init(a,x,la); init(b,y,lb); if(la>lb) sub(x,y,la,0); else if(la<lb) sub(y,x,lb,1); else { int k=strcmp(a,b); if(k>0) sub(x,y,la,0); else if(k<0) sub(y,x,lb,1); else { cout<<'0'<<endl; return 0; } }}

简单高精度乘法 (codevs 天梯黄金)

乘法的话要比减法和加法复杂一些，但和我们正常手算的方式一致，但是如果仔细观察的话可以发现第一个数的第i位和第二个数的第j位相乘则乘积保存在另一个数组的第i+j-1位，最后实现进位功能，差不多就这样，但是还是存在一些细节，比如最后判断完毕需要从后往前找到第一个不为0的数以确定数打印的起点，不然可能会出现0345的情况。 code：

#include<iostream>#include<stdio.h>#include<string.h>#define maxn 5001using namespace std;void init(char x[],int a[],int len){ for(int i=0;i<len;i++) { a[i]=x[len-1-i]-'0'; }}void mult(int a[],int b[],int la,int lb){ int i,j,c[maxn]={0},len,maxlen=la+lb,k; for(i=0;i<lb;i++) { for(j=la-1;j>=0;j--) { c[i+j]+=b[i]*a[j]; } for(k=0;k<maxlen;k++) { if(c[k]>=10) { c[k+1]+=c[k]/10; c[k]=c[k]%10; } } } for(i=maxlen;c[i]==0;i--); len=i+1; for(i=len-1;i>=0;i--) { cout<<c[i]; } }int main(void){ int a[maxn]={0},b[maxn]={0}; char x[maxn]={0},y[maxn]={0}; cin>>x>>y; int la=strlen(x),lb=strlen(y); init(x,a,la); init(y,b,lb); if((la==1&&a[0]==0)||(lb==1&&b[0]==0)) { cout<<'0'<<endl; return 0; } else { mult(a,b,la,lb); } return 0;}

最后附上一道今天写的回文数（vijos 1304） 题目详见网站。。。大致是其中实现了一个简单的n进制的加法，注意：加法的进位条件是if(a[i]>=n)以为到n的时候也要进位，当时就是因为这个而错了一个点orz…其他的就是细心一点的模拟了 code:

#include<iostream>#include<stdio.h>#include<string>using namespace std;string m;int len,n,a[100001]={0};void repeat(){ int c[100001]={0}; for(int i=0;i<len;i++) { c[i]+=a[i]+a[len-i-1]; if(c[i]>=n) { c[i]%=n; c[i+1]++; if(i==len-1) { len++; break; } } } for(int i=0;i<len;i++) { a[i]=c[len-i-1]; }}bool judge(int y[]){ for(int i=0;i<len;i++) { if(y[i]!=y[len-i-1]) return 0; } return 1;}int main(void){ cin>>n>>m; len=m.size(); for(int i=0;i<len;i++) { if(m[i]<65) a[i]=m[i]-'0'; else a[i]=m[i]-55; } for(int i=0;i<30;i++) { if(judge(a)) { cout<<"STEP="<<i<<endl; return 0; } else { repeat(); } } cout<<"Impossible!"<<endl;}

上一篇：window对象常用的方法、注册事件的方式、常用的事件、地址栏对象、Screen(屏幕)对象

下一篇：策略模式