基本介紹
- 中文名：高精度算法
- 外文名：High Accuracy Algorithm
Pascal,高精度加法,高精度乘法（低對高）,高精度乘法（高對高）,高精度除法,C++,C,算法一,算法二,
Pascal
Procedure HPule(a,b:Arr;Var c:Arr);//高精度加法Var i:Integer;Begin FillChar(c,SizeOf(c),0); For i:=1 To Max n-1 Do Begin c[i]:=c[i]+a[i]+b[i]; c[i+1]:=c[i] Div k; c[i]:=c[i] Mod k； End;End;Procedure HPule(a:Arr;b:Integer;Varc:Arr);//高精度乘以單精度Var i:Integer;Begin FillChar(c,SizeOf(c),0); For i:=1 To Maxn-1 Do Begin c[i]:=c[i]+a[i]*b; c[i+1]:=c[i]Divk; c[i]:=c[i]Modk End;End;Procedure HPule(a,b:Arr;;Varc:Arr);//高精度乘以高精度Var i,j:Integer; Begin FillChar(c,SizeOf(c),0); For i:=1 To Maxn Do For j:=1 To Maxn Begin c[i+j-1]:=c[i+j-1]+a[i]*b[j]; c[i+j]:=c[i+j]+(c[i+j-1]Divk); c[i+j-1]:=c[i+j-1] Mod k End;End;
高精度加法
var a,b,c: array[1..201] of 0..9; n:string; lenalenb,lenc,i,x:integer;begin write('Inputaugend:'); readln(n); lena:=length(n); for i:=1 to lena do a[lena-i+1]:=ord(n)-ord('0');{加數放入a數組} write('Inputaddend:'); readln(n); lenb:=length(n); for i:=1 to lenb do b[lenb-i+1]:=ord(n)-ord('0');{被加數放入b數組} i:=1; while (i<=lena)or(i<=lenb) do begin x:=a[i]+b[i]+xdiv10;{兩數相加，然後加前次進位} c[i]:=xmod10;{保存第i位的值} i:=i+1 end; if x>=10 {處理最高進位} then begin lenc:=i; c:=1; end else enc:=i-1; for i:=lenc downto 1 do write(c); writeln;{輸出結果}end.高精度乘法（低對高）
constmax=100;n=20;vara:array[1..max]of0..9;i,j,k,x:integer;begink:=1;a[k]:=1;{a=1}fori:=2tondo{a*2*3….*n}beginx:=0;{進位初始化}forj:=1tokdo{a=a*i}beginx:=x+a[j]*i;a[j]:=xmod10;x:=xdiv10end;whilex>0do{處理最高位的進位}begink:=k+1;a[k]:=xmod10;x:=xdiv10end;end;writeln;fori:=kdownto1write(a);{輸出a}end.高精度乘法（高對高）
vara,b,c:array[1..200]of0..9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;beginwrite('Inputmultiplier:');readln(n1);write('Inputmultiplicand:');readln(n2);lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1)-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2)-ord('0');fori:=1tolenadobeginx:=0;forj:=1tolenbdo{對乘數的每一位進行處理}beginx:=a[j]*b[j]+xdiv10+c;{當前乘積+上次乘積進位+原數}c:=xmod10;end;c:=xdiv10;{進位}end;lenc:=i+j;while(c[lenc]=0)and(lenc>1)dodec(lenc);{最高位的0不輸出}fori:=lencdownto1dowrite(c);writeln;end.高精度除法
算法一
procedurehigh_devide(a,b:hp;varc,d:hp);vari,len:integer;beginfillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);len:=a[0];d[0]:=1;fori:=lendownto1dobeginmultiply(d,10,d);d[1]:=a[i];while(compare(d,b)>=0)do{即d>=b}beginSubtract(d,b,d);inc(c[i]);end;end;while(len>1)and(c.s[len]=0)dodec(len);c.len:=len;end;算法二
fillchar(s,sizeof(s),0);{小數部分初始化}fillchar(posi,sizeof(posi),0);{小數值的位序列初始化}len←0;st←0;{小數部分的指針和循環節的首指針初始化}read(x,y);{讀被除數和除數}write(xdivy);{輸出整數部分}x←xmody;{計算x除以y的餘數}ifx=0thenexit;{若x除盡y，則成功退出}whilelenlimitdo{若小數位未達到上限，則循環}begininc(len);posix←len;{記下當前位小數，計算下一位小數和餘數}x←x*10;slen←xdivy;x←xmody;ifposix0{若下一位餘數先前出現過，則先前出現的位置為循環節的開始}thenbeginst←posix;break;end;{then}ifx=0thenbreak;{若除盡，則成功退出}end;{while}iflen=0thenbeginwriteln;exit;end;{若小數部分的位數為0，則成功退出；否則輸出小數點}write(.);ifst=0{若無循環節，則輸出小數部分，否則輸出循環節前的小數和循環節}thenfori←1tolendowrite(s)elsebeginfori←1tost-1dowrite(s);write();fori←sttolendowrite(s);write();end;{else}C++
#include<iostream>#include<vector>#include<string>using namespace std;struct Wint:vector<int>//用標準庫vector做基類，完美解決位數問題，同時更易於實現{ //將低精度轉高精度的初始化，可以自動被編譯器調用 //因此無需單獨寫高精度數和低精度數的運算函式，十分方便 Wint(int n=0)//默認初始化為0，但0的保存形式為空 { push_back(n); check(); } Wint& check()//在各類運算中經常用到的進位小函式，不妨內置 { while(!empty()&&!back())pop_back();//去除最高位可能存在的0 if(empty())return *this; for(int i=1; i<size(); ++i) { (*this)[i]+=(*this)[i-1]/10; (*this)[i-1]%=10; } while(back()>=10) { push_back(back()/10); (*this)[size()-2]%=10; } return *this;//為使用方便，將進位後的自身返回引用 }};//輸入輸出istream& operator>>(istream &is,Wint &n){ string s; is>>s; n.clear(); for(int i=s.size()-1; i>=0; --i)n.push_back(s[i]-'0'); return is;}ostream& operator<<(ostream &os,const Wint &n){ if(n.empty())os<<0; for(int i=n.size()-1; i>=0; --i)os<<n[i]; return os;}//比較，只需要寫兩個，其他的直接代入即可//常量引用當參數，避免拷貝更高效bool operator!=(const Wint &a,const Wint &b){ if(a.size()!=b.size())return 1; for(int i=a.size()-1; i>=0; --i) if(a[i]!=b[i])return 1; return 0;}bool operator==(const Wint &a,const Wint &b){ return !(a!=b);}bool operator<(const Wint &a,const Wint &b){ 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 0;}bool operator>(const Wint &a,const Wint &b){ return b<a;}bool operator<=(const Wint &a,const Wint &b){ return !(a>b);}bool operator>=(const Wint &a,const Wint &b){ return !(a<b);}//加法，先實現+=，這樣更簡潔高效Wint& operator+=(Wint &a,const Wint &b){ if(a.size()<b.size())a.resize(b.size()); for(int i=0; i!=b.size(); ++i)a[i]+=b[i]; return a.check();}Wint operator+(Wint a,const Wint &b){ return a+=b;}//減法，返回差的絕對值，由於後面有交換，故參數不用引用Wint& operator-=(Wint &a,Wint b){ if(a<b)swap(a,b); for(int i=0; i!=b.size(); a[i]-=b[i],++i) if(a[i]<b[i])//需要借位 { int j=i+1; while(!a[j])++j; while(j>i) { --a[j]; a[--j]+=10; } } return a.check();}Wint operator-(Wint a,const Wint &b){ return a-=b;}//乘法不能先實現*=，原因自己想Wint operator*(const Wint &a,const Wint &b){ Wint n; n.assign(a.size()+b.size()-1,0); for(int i=0; i!=a.size(); ++i) for(int j=0; j!=b.size(); ++j) n[i+j]+=a[i]*b[j]; return n.check();}Wint& operator*=(Wint &a,const Wint &b){ return a=a*b;}//除法和取模先實現一個帶餘除法函式Wint divmod(Wint &a,const Wint &b){ Wint ans; for(int t=a.size()-b.size(); a>=b; --t) { Wint d; d.assign(t+1,0); d.back()=1; Wint c=b*d; while(a>=c) { a-=c; ans+=d; } } return ans;}Wint operator/(Wint a,const Wint &b){ return divmod(a,b);}Wint& operator/=(Wint &a,const Wint &b){ return a=a/b;}Wint& operator%=(Wint &a,const Wint &b){ divmod(a,b); return a;}Wint operator%(Wint a,const Wint &b){ return a%=b;}//順手實現一個快速冪，可以看到和普通快速冪幾乎無異Wint pow(const Wint &n,const Wint &k){ if(k.empty())return 1; if(k==2)return n*n; if(k.back()%2)return n*pow(n,k-1); return pow(pow(n,k/2),2);}//通過重載運算符，還可以實現++、--、^、!、邏輯運算符等很多運算，十分簡單，此處都不寫了int main()//現在你完全可以像int一般便捷地使用Wint，如下{ Wint a,b; //可以把b改成int型，仍能正常使用 cin>>a>>b; cout<<(a<b)<<endl <<(a==b)<<endl <<a+b<<endl <<a-b<<endl <<a*b<<endl <<a/b<<endl <<a%b<<endl <<pow(a,b);}C
算法一
#include<stdio.h> #include<string.h> #define MAXLEN200;//設定數的最大長度 int main(){ int a[MAXLEN+10],b[MAXLEN+10],len1,len2,c[2*MAXLEN+10],i,j;char str1[MAXLEN+10],str2[MAXLEN+10];for(i=0;i<MAXLEN+10;i++)a[i]=b[i]=0;//將a,b兩個數組都置為零for(i=0;i<2*MAXLEN+10;i++)c[i]=0;//將c置為零//scanf("%s%s",str1,str2);gets(str1);gets(str2);//以字元的形式讀入兩個乘數len1=strlen(str1);len2=strlen(str2);for(i=len1-1,j=0;i>=0;i--)//將字元型數轉換成數字，低位存在數組的低位(倒置)a[j++]=str1[i]-'0';//字元型減去'0'的ASCIII碼值轉換為數字for(i=len2-1,j=0;i>=0;i--)b[j++]=str2[i]-'0';//同上for(i=0;i<len2;i++)//循環相乘，用第二個數的每一位去乘以第一個數，a的第i位乘以b的第j位之後存在c的第i+j位上for(j=0;j<len1;j++)c[i+j]+=b[i]*a[j];for(i=0;i<len1+len2+2;i++)//處理進位問題，如果大於10，則進位if(c[i]>=10){c[i+1]+=c[i]/10;c[i]%=10;}for(i=len1+len2+2;(c[i]==0)&&(i>=0);i--);//過濾掉高位的數字零，使之不輸出if(i>=0)for(;i>=0;i--) printf("%d",c[i]);elseprintf("0");printf("\n");return0;}算法二
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<malloc.h>int an,bn,fa=1,fb=1;/*把an,bn,k設為全局變數,an紀錄第一個高精度數組的位數,bn紀錄第二個高精度數組的位數,k紀錄輸出結果的位數*/char b1[250],b2[250];/*紀錄需要計算的兩個高精度數據*/void input(int a1[],int a2[]){ /*函式input為輸入函式,用來紀錄兩個待計算的高精度數據,以數組首地址為參數.以實現返回兩個高精度數據*/ int i,ai=1,bi=1; scanf("%s%s",b1,b2);/*輸入兩個高精度數據*/ an=strlen(b1);/*an紀錄b1的位數*/ bn=strlen(b2);/*bn紀錄b2的位數*/ if(b1[0]==45){an--;fa=-1;ai=0;}/*判斷數組的符號*/ if(b2[0]==45){bn--;fb=-1;bi=0;} for(i=0;i<an;i++,ai++){a1[i]=b1[an-ai]-'0';printf("%d",a1[i]);} /*把字元形數據b1轉為整數形數據,同樣用數組紀錄*/ for(i=0;i<bn;i++,bi++)a2[i]=b2[bn-bi]-'0';/*同上*/ return;}void subtraction(int a[],int b[],int q);void addition(int a[],int b[],int q)/*高精度加法運算*/{ int i,c[251]={0},k; if(fa*fb>0||q) { if(an>bn) k=an; else k=bn;/*用k紀錄結果的最小位數*/ for(i=0;i<k;i++) { c[i]=a[i]+b[i]+c[i]; c[i+1]=(int)c[i]/10; c[i]=(int)c[i]%10; }/*高精度加法運算過程*/ if(c[k])k++;/*判斷最後結果的位數*/ if(fa<0&&q||fa<0)printf("-"); for(i=k-1;i>=0;i--)printf("%d",c[i]);/*輸出結果*/ return; } else subtraction(a,b,1); return;}void subtraction(int a[],int b[],int q)/*高精度減法運算*/{ int i,f=0,c[251]={0},k; if(fa*fb>0||q) { if(an>bn) k=an; else/*用k紀錄結果的最大位數*/ { k=bn; for(i=k;a[i]<=b[i]&&i>=0;i--) if(a[i]<b[i])f=1;/*f紀錄結果符號*/ } if(!f)/*高精度減法運算過程*/ for(i=0;i<k;i++) { if(a[i]<b[i]) {a[i+1]--; a[i]+=10; } c[i]=a[i]-b[i]; } else/*當a<b時的處理*/ for(i=0;i<k;i++) { if(b[i]<a[i]) {b[i+1]--; b[i]+=10; } c[i]=b[i]-a[i]; } while(!c[k-1]&&k>1)k--;/*判斷最後結果的位數*/ if(q&&(fa>0&&f||fa<0&&!f)||fa>0&&(fb>0&&!f||f&&!q))printf("-");/*如果f為真是輸出負號*/ for(i=k-1;i>=0;i--)printf("%d",c[i]); return; } else addition(a,b,1);}void multiplication(int a[],int b[])/*高精度乘法運算*/{ int i,j,c[501]={0},k; k=an+bn-1;/*用k紀錄結果的最大位數*/ for(i=0;i<an;i++)/*高精度乘法運算過程*/ for(j=0;j<bn;j++) { c[i+j]=a[i]*b[j]+c[i+j]; c[i+j+1]=c[i+j]/10+c[i+j+1]; c[i+j]=c[i+j]%10; } while(!c[k])k--;/*判斷最後結果的位數*/ if(fa*fb<0)printf("-"); for(i=k;i>=0;i--)printf("%d",c[i]);/*輸出結果*/}int main(){ int a[250]={0},b[250]={0}; input(a,b); printf("\n%s+%s=",b1,b2); addition(a,b,0); printf("\n%s-%s=",b1,b2); subtraction(a,b,0); printf("\n%s*%s=",b1,b2); multiplication(a,b); system("pause"); return 0;}