高精度計算(C++版)課件

第一章高精度計算第一章高精度計算1

利用計算機(jī)進(jìn)行數(shù)值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計算機(jī)的計算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實(shí)際問題所要求的精度。我們可以利用程序設(shè)計的方法去實(shí)現(xiàn)這樣的高精度計算。介紹常用的幾種高精度計算的方法。

高精度計算中需要處理好以下幾個問題：

(1)數(shù)據(jù)的接收方法和存貯方法

數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。

voidinit(inta[])

//傳入一個數(shù)組

{

strings;

cin>>s;

//讀入字符串s

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲

}另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。 利用計算機(jī)進(jìn)行數(shù)值計算，有時會遇到這樣的問2(2)高精度數(shù)位數(shù)的確定位數(shù)的確定：接收時往往是用字符串的，所以它的位數(shù)就等于字符串的長度。(3)進(jìn)位,借位處理

加法進(jìn)位：c[i]=a[i]+b[i];

if(c[i]>=10){c[i]%=10;++c[i+1];}減法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}

c[i]=a[i]-b[i];乘法進(jìn)位：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];

x=c[i+j-1]/10;

c[i+j-1]%=10;(4)商和余數(shù)的求法商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理.第1章高精度計算(C++版)課件3【例1】高精度加法。輸入兩個正整數(shù)，求它們的和。【分析】輸入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C++語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個被加數(shù)很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數(shù)相加的算法。856+2551111圖1A3A2A1+B3B2B1

C4C3C2C1圖2如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)組C存儲結(jié)果。則上例有A[1]=6，A[2]=5，A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1，C[3]=1，C[2]=1，C[1]=1，兩數(shù)相加如圖2所示?！纠?】高精度加法。輸入兩個正整數(shù)，求它們的和。84因此，算法描述如下：intc[100];voidadd(inta[],intb[])//a,b,c都為數(shù)組，分別存儲被加數(shù)、加數(shù)、結(jié)果{

inti=1,x=0;

//x是進(jìn)位

while((i<=a數(shù)組長度)||(i<=b數(shù)組的長度)){c[i]=a[i]+b[i]+x; //第i位相加并加上次的進(jìn)位x=c[i]/10;

//向高位進(jìn)位c[i]%=10;//存儲第i位的值i++;

//位置下標(biāo)變量}}因此，算法描述如下：5

通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){

chara1[100],b1[100];

inta[100],b[100],c[100],lena,lenb,lenc,i,x;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

gets(a1);

gets(b1);

//輸入加數(shù)與被加數(shù)

lena=strlen(a1);

lenb=strlen(b1);

for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;

//加數(shù)放入a數(shù)組

for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;//加數(shù)放入b數(shù)組

lenc=1;

x=0;

通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：6

while(lenc<=lena||lenc<=lenb)

{

c[lenc]=a[lenc]+b[lenc]+x;

//兩數(shù)相加

x=c[lenc]/10;

c[lenc]%=10;

lenc++;

}

c[lenc]=x;

if(c[lenc]==0)

lenc--;//處理最高進(jìn)位

for(i=lenc;i>=1;i--)

cout<<c[i];

//輸出結(jié)果

cout<<endl; return0;} while(lenc<=lena||lenc<=l7【例2】高精度減法。輸入兩個正整數(shù)，求它們的差?！舅惴ǚ治觥款愃萍臃?，可以用豎式求減法。在做減法運(yùn)算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){

inta[256],b[256],c[256],lena,lenb,lenc,i;

charn[256],n1[256],n2[256];

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

【例2】高精度減法。輸入兩個正整數(shù)，求它們的差。8

printf("Inputminuend:");gets(n1);//輸入被減數(shù)

printf("Inputsubtrahend:");gets(n2);//輸入減數(shù)

if(strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))//strcmp()為字符串比較函數(shù)，當(dāng)n1==n2,返回0;//n1>n2時，返回正整數(shù)；n1<n2時，返回負(fù)整數(shù)

{//處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù)

strcpy(n,n1);//將n1數(shù)組的值完全賦值給n數(shù)組

strcpy(n1,n2);

strcpy(n2,n);

cout<<"-";//交換了減數(shù)和被減數(shù)，結(jié)果為負(fù)數(shù)

}

lena=strlen(n1);lenb=strlen(n2);

for(i=0;i<=lena-1;i++)a[lena-i]=int(n1[i]-'0');//被減數(shù)放入a數(shù)組

for(i=0;i<=lenb-1;i++)b[lenb-i]=int(n2[i]-'0');//減數(shù)放入b數(shù)組

printf("Inputminuend:");9

i=1;

while(i<=lena||i<=lenb)

{

if(a[i]<b[i])

{

a[i]+=10;//不夠減，那么向高位借1當(dāng)10

a[i+1]--;

}

c[i]=a[i]-b[i];//對應(yīng)位相減

i++;

}

lenc=i;

while((c[lenc]==0)&&(lenc>1))lenc--;//最高位的0不輸出

for(i=lenc;i>=1;i--)cout<<c[i];

//輸出結(jié)果

cout<<endl;

return0;} i=1;10【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積?！舅惴ǚ治觥款愃萍臃ǎ梢杂秘Q式求乘法。在做乘法運(yùn)算時，同樣也有進(jìn)位，同時對每一位進(jìn)行乘法運(yùn)算時，必須進(jìn)行錯位相加，如圖3、圖4。分析c數(shù)組下標(biāo)的變化規(guī)律，可以寫出如下關(guān)系式：ci=c’i+c”i+…由此可見，ci跟a[i]*b[j]乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原ci的值有關(guān)，分析下標(biāo)規(guī)律，有c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;856×254280171221400圖3A3A2A1

×B2B1

C’4C’3C’2C’1

C”5C”4C”3C”2

C6C5C4C3C2C1圖4【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積。8511高精度乘法的參考程序：#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){

chara1[100],b1[100];

inta[100],b[100],c[100],lena,lenb,lenc,i,j,x;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

gets(a1);gets(b1);

lena=strlen(a1);lenb=strlen(b1);

for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;

for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;

高精度乘法的參考程序：12

for(i=1;i<=lena;i++)

{

x=0;

//用于存放進(jìn)位

for(j=1;j<=lenb;j++)//對乘數(shù)的每一位進(jìn)行處理

{

c[i+j-1]=a[i]*b[j]+x+c[i+j-1];//當(dāng)前乘積+上次乘積進(jìn)位+原數(shù)

x=c[i+j-1]/10;

c[i+j-1]%=10;

}

c[i+lenb]=x;

//進(jìn)位

}

lenc=lena+lenb;

while(c[lenc]==0&&lenc>1)//刪除前導(dǎo)0

lenc--;

for(i=lenc;i>=1;i--)

cout<<c[i];

cout<<endl; return0;} for(i=1;i<=lena;i++)13【例4】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）?！舅惴ǚ治觥孔龀〞r，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。當(dāng)然，為了程序簡潔，可以避免高精度除法，用0～9次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法?！纠?】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）。14#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){

chara1[100],c1[100];

inta[100],c[100],lena,i,x=0,lenc,b;

memset(a,0,sizeof(a));

memset(c,0,sizeof(c));

gets(a1);

cin>>b;

lena=strlen(a1);

for(i=0;i<=lena-1;i++)

a[i+1]=a1[i]-48;#include<iostream>15

for(i=1;i<=lena;i++)

//按位相除

{

c[i]=(x*10+a[i])/b;

x=(x*10+a[i])%b;

}

lenc=1;

while(c[lenc]==0&&lenc<lena)

lenc++;//刪除前導(dǎo)0

for(i=lenc;i<=lena;i++)

cout<<c[i];

cout<<endl; return0;} for(i=1;i<=lena;i++)16實(shí)質(zhì)上，在做兩個高精度數(shù)運(yùn)算時候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個數(shù)字，而采取保留多位數(shù)（例如一個整型或長整型數(shù)據(jù)等），這樣，在做運(yùn)算（特別是乘法運(yùn)算）時，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運(yùn)算，其他運(yùn)算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成。示例：123456789÷45=1’2345’6789÷45=274’3484∵1/45=0，1%45=1∴取12345/45=274∵12345%45=15∴取156789/45=3484∴答案為2743484,余數(shù)為156789%45=9圖5實(shí)質(zhì)上，在做兩個高精度數(shù)運(yùn)算時候，存儲高精度數(shù)17

【例5】高精除以高精，求它們的商和余數(shù)。

【算法分析】

高精除以低精是對被除數(shù)的每一位（這里的“一位”包含前面的余數(shù)，以下都是如此）都除以除數(shù)，而高精除以高精則是用減法模擬除法，對被除數(shù)的每一位都減去除數(shù)，一直減到當(dāng)前位置的數(shù)字（包含前面的余數(shù)）小于除數(shù)（由于每一位的數(shù)字小于10，所以對于每一位最多進(jìn)行10次計算）具體實(shí)現(xiàn)程序如下： 【例5】高精除以高精，求它們的商和余數(shù)。18

#include<iostream>#include<cstring>usingnamespacestd;inta[101],b[101],c[101],d,i;voidinit(inta[]){

strings;

cin>>s;//讀入字符串s

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲．}voidprint(inta[])//打印輸出{

if(a[0]==0){cout<<0<<endl;return;}

for(inti=a[0];i>0;i--)cout<<a[i];

cout<<endl;

return;}#include<iostream>19

intcompare(inta[],intb[])

//比較a和b的大小關(guān)系，若a>b則為1，a<b則為-1,a=b則為0{

if(a[0]>b[0])return1;

//a的位數(shù)大于b則a比b大

if(a[0]<b[0])return-1;

//a的位數(shù)小于b則a比b小

for(i=a[0];i>0;i--)

//從高位到低位比較

{

if(a[i]>b[i])return1;

if(a[i]<b[i])return-1;

}

return0;

//各位都相等則兩數(shù)相等。}voidnumcpy(intp[],intq[],intdet)//復(fù)制p數(shù)組到q數(shù)組從det開始的地方{

for(inti=1;i<=p[0];i++)q[i+det-1]=p[i];

q[0]=p[0]+det-1;}intcompare(inta[],intb[])20

voidjian(inta[],intb[])

//計算a=a-b{

intflag,i;

flag=compare(a,b);//調(diào)用比較函數(shù)判斷大小

if(flag==0){a[0]=0;return;}//相等

if(flag==1)

//大于

{

for(i=1;i<=a[0];i++)

{

if(a[i]<b[i]){a[i+1]--;a[i]+=10;}//若不夠減則向上借一位

a[i]-=b[i];

}

while(a[0]>0&&a[a[0]]==0)a[0]--;

//修正a的位數(shù)

return;

}}voidjian(inta[],intb[])21

voidchugao(inta[],intb[],intc[]){

inttmp[101];

c[0]=a[0]-b[0]+1;

for(inti=c[0];i>0;i--)

{

memset(tmp,0,sizeof(tmp));

//數(shù)組清零

numcpy(b,tmp,i);

while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}//用減法來模擬

}

while(c[0]>0&&c[c[0]]==0)c[0]--;

return;}voidchugao(inta[],intb[],i22

intmain(){

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

init(a);init(b);

chugao(a,b,c);

print(c);

print(a);

return0;}intmain()23

【例6】回文數(shù)【問題描述】

若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個回文數(shù)。又如，對于10進(jìn)制數(shù)87，STEPl：87＋78=165STEP2：165＋561=726STEP3：726＋627＝1353STEP4：1353+3531=4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個程序，給定一個N（2＜N＜＝10或N=16）進(jìn)制數(shù)M．求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進(jìn)制運(yùn)算1、當(dāng)前位規(guī)范由%10改為%n2、進(jìn)位處理由/10改為/n3、其他運(yùn)算規(guī)則不變【例6】回文數(shù)24

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intn,a[101],b[101],ans,i;voidinit(inta[])

//將數(shù)串s轉(zhuǎn)化為整數(shù)數(shù)組a{

strings;

cin>>n>>s;//讀入字符串s

memset(a,0,sizeof(a));//數(shù)組a清0

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0';

elsea[i]=s[a[0]-i]-'A'+10;}boolcheck(inta[])//判別整數(shù)數(shù)組a是否為回文數(shù){

for(i=1;i<=a[0];i++)

if(a[i]!=a[a[0]-i+1])returnfalse;

returntrue;}【參考程序】25

voidjia(inta[])//整數(shù)數(shù)組a與其反序數(shù)b進(jìn)行n進(jìn)制加法運(yùn)算{

for(inti=1;i<=a[0];i++)b[i]=a[a[0]-i+1];//反序數(shù)b

for(inti=1;i<=a[0];i++)a[i]+=b[i];//逐位相加

for(inti=1;i<=a[0];i++)

//處理進(jìn)位

{a[i+1]+=a[i]/n;

a[i]%=n;

}

if(a[a[0]+1]>0)a[0]++;//修正新的a的位數(shù)（a+b最多只能的一個進(jìn)位）}intmain(){

init(a);

if(check(a)){cout<<0<<endl;return0;}

ans=0;

//步數(shù)初始化為0

while(ans++<=30)

{

jia(a);

if(check(a)){cout<<ans<<endl;return0;}

}

cout<<"Impossible";//輸出無解信息

return0;}voidjia(inta[])26【上機(jī)練習(xí)】1、求N！的值【問題描述】用高精度方法，求N！的精確值(N以一般整數(shù)輸入)?！据斎霕永縩i.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】計算A/B的精確值，設(shè)A，B是以一般整數(shù)輸入，計算結(jié)果精確小數(shù)后20位?！据斎霕永縜b.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例】ab.out6/5=1.2【上機(jī)練習(xí)】1、求N！的值273、求n累加和【問題描述】用高精度方法，求s=1+2+3+……+n的精確值(n以一般整數(shù)輸入)?！据斎霕永縥a.in

10【輸出樣例】ja.out554、階乘和(sum.pas)【問題描述】已知正整數(shù)N（N<=100）,設(shè)S=1!+2!+3!+...N!。其中"!"表示階乘,即N!=1*2*3*……*(N-1)*N，如:3!=1*2*3=6。請編程實(shí)現(xiàn)：輸入正整數(shù)N,輸出計算結(jié)果S的值。【輸入樣例】sum.in4【輸出樣例】sum.out335、高精度求積(MULTIPLY.PAS)【問題描述】輸入兩個高精度正整數(shù)M和N（M和N均小于100位）?！締栴}求解】求這兩個高精度數(shù)的積?！据斎霕永縈ULTIPLY.IN363【輸出樣例】MULTIPLY.OUT1083、求n累加和286、天使的起誓（YUBIKILI.pas）【問題描述】TENSHI非常幸運(yùn)的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當(dāng)選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(fā)言稿被放在N個呈圓形排列的寶盒中。這些寶盒按順時針方向被編上號碼１、２、３……、N-1、N。一開始天使們站在編號為N的寶盒旁。她們各自手上都有一個數(shù)字，代表她們自己的發(fā)言稿所在的盒子是從１號盒子開始按順時針方向的第幾個。例如：有７個盒子，那么如果TENSHI手上的數(shù)字為９，那么她的發(fā)言稿所在盒子就是第２個。現(xiàn)在天使們開始按照自己手上的數(shù)字來找發(fā)言稿，先找到的就可以先發(fā)言。TENSHI一下子就找到了，于是她最先上臺宣誓：“我將帶領(lǐng)大家開啟NOI之門……”TENSHI宣誓結(jié)束以后，陸續(xù)有天使上臺宣誓?？墒怯幸晃惶焓拐伊撕镁枚颊也坏剿陌l(fā)言稿，原來她手上的數(shù)字M非常大，她轉(zhuǎn)了好久都找不到她想找的寶盒。【問題求解】請幫助這位天使找到她想找的寶盒的編號?！据斎敫袷健繌奈募UBIKILI.IN的第一、二行分別讀入正整數(shù)N和M，其中N、M滿足2≤N≤108，2≤M≤101000【輸出格式】把所求寶盒的編號輸出到文件YUBIKILI.OUT，文件只有一行（包括換行符）。樣例一YUBIKILI.IN79YUBIKILI.OUT2樣例二YUBIKILI.IN11108YUBIKILI.OUT96、天使的起誓（YUBIKILI.pas）樣例一YUBIKI297、Hanoi雙塔問題(Noip2007)【問題描述】給定A、B、C三根足夠長的細(xì)柱，在A柱上放有2n個中間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細(xì)柱上的圓盤都要保持上小下大的順序；任務(wù)：設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)，對于輸入的n，輸出An?！据斎敫袷健枯斎胛募anoi.in為一個正整數(shù)n，表示在A柱上放有2n個圓盤?！据敵龈袷健枯敵鑫募anoi.out僅一行，包含一個正整數(shù),為完成上述任務(wù)所需的最少移動次數(shù)An。樣例一hanoi.in

1hanoi.out2樣例二hanoi.inhanoi.out26【限制】對于50%的數(shù)據(jù)，1<=n<=25對于100%的數(shù)據(jù)，1<=n<=200【提示】設(shè)法建立An與An-1的遞推關(guān)系式。7、Hanoi雙塔問題(Noip2007)【輸入格式】樣例一30第一章高精度計算第一章高精度計算31

利用計算機(jī)進(jìn)行數(shù)值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計算機(jī)的計算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實(shí)際問題所要求的精度。我們可以利用程序設(shè)計的方法去實(shí)現(xiàn)這樣的高精度計算。介紹常用的幾種高精度計算的方法。

高精度計算中需要處理好以下幾個問題：

(1)數(shù)據(jù)的接收方法和存貯方法

數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。

voidinit(inta[])

//傳入一個數(shù)組

{

strings;

cin>>s;

//讀入字符串s

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲

}另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。 利用計算機(jī)進(jìn)行數(shù)值計算，有時會遇到這樣的問32(2)高精度數(shù)位數(shù)的確定位數(shù)的確定：接收時往往是用字符串的，所以它的位數(shù)就等于字符串的長度。(3)進(jìn)位,借位處理

加法進(jìn)位：c[i]=a[i]+b[i];

if(c[i]>=10){c[i]%=10;++c[i+1];}減法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}

c[i]=a[i]-b[i];乘法進(jìn)位：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];

x=c[i+j-1]/10;

c[i+j-1]%=10;(4)商和余數(shù)的求法商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理.第1章高精度計算(C++版)課件33【例1】高精度加法。輸入兩個正整數(shù)，求它們的和?！痉治觥枯斎雰蓚€數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C++語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個被加數(shù)很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數(shù)相加的算法。856+2551111圖1A3A2A1+B3B2B1

C4C3C2C1圖2如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)組C存儲結(jié)果。則上例有A[1]=6，A[2]=5，A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1，C[3]=1，C[2]=1，C[1]=1，兩數(shù)相加如圖2所示?！纠?】高精度加法。輸入兩個正整數(shù)，求它們的和。834因此，算法描述如下：intc[100];voidadd(inta[],intb[])//a,b,c都為數(shù)組，分別存儲被加數(shù)、加數(shù)、結(jié)果{

inti=1,x=0;

//x是進(jìn)位

while((i<=a數(shù)組長度)||(i<=b數(shù)組的長度)){c[i]=a[i]+b[i]+x; //第i位相加并加上次的進(jìn)位x=c[i]/10;

//向高位進(jìn)位c[i]%=10;//存儲第i位的值i++;

//位置下標(biāo)變量}}因此，算法描述如下：35

通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){

chara1[100],b1[100];

inta[100],b[100],c[100],lena,lenb,lenc,i,x;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

gets(a1);

gets(b1);

//輸入加數(shù)與被加數(shù)

lena=strlen(a1);

lenb=strlen(b1);

for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;

//加數(shù)放入a數(shù)組

for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;//加數(shù)放入b數(shù)組

lenc=1;

x=0;

通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：36

while(lenc<=lena||lenc<=lenb)

{

c[lenc]=a[lenc]+b[lenc]+x;

//兩數(shù)相加

x=c[lenc]/10;

c[lenc]%=10;

lenc++;

}

c[lenc]=x;

if(c[lenc]==0)

lenc--;//處理最高進(jìn)位

for(i=lenc;i>=1;i--)

cout<<c[i];

//輸出結(jié)果

cout<<endl; return0;} while(lenc<=lena||lenc<=l37【例2】高精度減法。輸入兩個正整數(shù)，求它們的差。【算法分析】類似加法，可以用豎式求減法。在做減法運(yùn)算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){

inta[256],b[256],c[256],lena,lenb,lenc,i;

charn[256],n1[256],n2[256];

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

【例2】高精度減法。輸入兩個正整數(shù)，求它們的差。38

printf("Inputminuend:");gets(n1);//輸入被減數(shù)

printf("Inputsubtrahend:");gets(n2);//輸入減數(shù)

if(strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))//strcmp()為字符串比較函數(shù)，當(dāng)n1==n2,返回0;//n1>n2時，返回正整數(shù)；n1<n2時，返回負(fù)整數(shù)

{//處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù)

strcpy(n,n1);//將n1數(shù)組的值完全賦值給n數(shù)組

strcpy(n1,n2);

strcpy(n2,n);

cout<<"-";//交換了減數(shù)和被減數(shù)，結(jié)果為負(fù)數(shù)

}

lena=strlen(n1);lenb=strlen(n2);

for(i=0;i<=lena-1;i++)a[lena-i]=int(n1[i]-'0');//被減數(shù)放入a數(shù)組

for(i=0;i<=lenb-1;i++)b[lenb-i]=int(n2[i]-'0');//減數(shù)放入b數(shù)組

printf("Inputminuend:");39

i=1;

while(i<=lena||i<=lenb)

{

if(a[i]<b[i])

{

a[i]+=10;//不夠減，那么向高位借1當(dāng)10

a[i+1]--;

}

c[i]=a[i]-b[i];//對應(yīng)位相減

i++;

}

lenc=i;

while((c[lenc]==0)&&(lenc>1))lenc--;//最高位的0不輸出

for(i=lenc;i>=1;i--)cout<<c[i];

//輸出結(jié)果

cout<<endl;

return0;} i=1;40【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積?！舅惴ǚ治觥款愃萍臃?，可以用豎式求乘法。在做乘法運(yùn)算時，同樣也有進(jìn)位，同時對每一位進(jìn)行乘法運(yùn)算時，必須進(jìn)行錯位相加，如圖3、圖4。分析c數(shù)組下標(biāo)的變化規(guī)律，可以寫出如下關(guān)系式：ci=c’i+c”i+…由此可見，ci跟a[i]*b[j]乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原ci的值有關(guān)，分析下標(biāo)規(guī)律，有c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;856×254280171221400圖3A3A2A1

×B2B1

C’4C’3C’2C’1

C”5C”4C”3C”2

C6C5C4C3C2C1圖4【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積。8541高精度乘法的參考程序：#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){

chara1[100],b1[100];

inta[100],b[100],c[100],lena,lenb,lenc,i,j,x;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

gets(a1);gets(b1);

lena=strlen(a1);lenb=strlen(b1);

for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;

for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;

高精度乘法的參考程序：42

for(i=1;i<=lena;i++)

{

x=0;

//用于存放進(jìn)位

for(j=1;j<=lenb;j++)//對乘數(shù)的每一位進(jìn)行處理

{

c[i+j-1]=a[i]*b[j]+x+c[i+j-1];//當(dāng)前乘積+上次乘積進(jìn)位+原數(shù)

x=c[i+j-1]/10;

c[i+j-1]%=10;

}

c[i+lenb]=x;

//進(jìn)位

}

lenc=lena+lenb;

while(c[lenc]==0&&lenc>1)//刪除前導(dǎo)0

lenc--;

for(i=lenc;i>=1;i--)

cout<<c[i];

cout<<endl; return0;} for(i=1;i<=lena;i++)43【例4】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）?！舅惴ǚ治觥孔龀〞r，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。當(dāng)然，為了程序簡潔，可以避免高精度除法，用0～9次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法?！纠?】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）。44#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){

chara1[100],c1[100];

inta[100],c[100],lena,i,x=0,lenc,b;

memset(a,0,sizeof(a));

memset(c,0,sizeof(c));

gets(a1);

cin>>b;

lena=strlen(a1);

for(i=0;i<=lena-1;i++)

a[i+1]=a1[i]-48;#include<iostream>45

for(i=1;i<=lena;i++)

//按位相除

{

c[i]=(x*10+a[i])/b;

x=(x*10+a[i])%b;

}

lenc=1;

while(c[lenc]==0&&lenc<lena)

lenc++;//刪除前導(dǎo)0

for(i=lenc;i<=lena;i++)

cout<<c[i];

cout<<endl; return0;} for(i=1;i<=lena;i++)46實(shí)質(zhì)上，在做兩個高精度數(shù)運(yùn)算時候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個數(shù)字，而采取保留多位數(shù)（例如一個整型或長整型數(shù)據(jù)等），這樣，在做運(yùn)算（特別是乘法運(yùn)算）時，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運(yùn)算，其他運(yùn)算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成。示例：123456789÷45=1’2345’6789÷45=274’3484∵1/45=0，1%45=1∴取12345/45=274∵12345%45=15∴取156789/45=3484∴答案為2743484,余數(shù)為156789%45=9圖5實(shí)質(zhì)上，在做兩個高精度數(shù)運(yùn)算時候，存儲高精度數(shù)47

【例5】高精除以高精，求它們的商和余數(shù)。

【算法分析】

高精除以低精是對被除數(shù)的每一位（這里的“一位”包含前面的余數(shù)，以下都是如此）都除以除數(shù)，而高精除以高精則是用減法模擬除法，對被除數(shù)的每一位都減去除數(shù)，一直減到當(dāng)前位置的數(shù)字（包含前面的余數(shù)）小于除數(shù)（由于每一位的數(shù)字小于10，所以對于每一位最多進(jìn)行10次計算）具體實(shí)現(xiàn)程序如下： 【例5】高精除以高精，求它們的商和余數(shù)。48

#include<iostream>#include<cstring>usingnamespacestd;inta[101],b[101],c[101],d,i;voidinit(inta[]){

strings;

cin>>s;//讀入字符串s

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

a[i]=s[a[0]-i]-'0';//將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲．}voidprint(inta[])//打印輸出{

if(a[0]==0){cout<<0<<endl;return;}

for(inti=a[0];i>0;i--)cout<<a[i];

cout<<endl;

return;}#include<iostream>49

intcompare(inta[],intb[])

//比較a和b的大小關(guān)系，若a>b則為1，a<b則為-1,a=b則為0{

if(a[0]>b[0])return1;

//a的位數(shù)大于b則a比b大

if(a[0]<b[0])return-1;

//a的位數(shù)小于b則a比b小

for(i=a[0];i>0;i--)

//從高位到低位比較

{

if(a[i]>b[i])return1;

if(a[i]<b[i])return-1;

}

return0;

//各位都相等則兩數(shù)相等。}voidnumcpy(intp[],intq[],intdet)//復(fù)制p數(shù)組到q數(shù)組從det開始的地方{

for(inti=1;i<=p[0];i++)q[i+det-1]=p[i];

q[0]=p[0]+det-1;}intcompare(inta[],intb[])50

voidjian(inta[],intb[])

//計算a=a-b{

intflag,i;

flag=compare(a,b);//調(diào)用比較函數(shù)判斷大小

if(flag==0){a[0]=0;return;}//相等

if(flag==1)

//大于

{

for(i=1;i<=a[0];i++)

{

if(a[i]<b[i]){a[i+1]--;a[i]+=10;}//若不夠減則向上借一位

a[i]-=b[i];

}

while(a[0]>0&&a[a[0]]==0)a[0]--;

//修正a的位數(shù)

return;

}}voidjian(inta[],intb[])51

voidchugao(inta[],intb[],intc[]){

inttmp[101];

c[0]=a[0]-b[0]+1;

for(inti=c[0];i>0;i--)

{

memset(tmp,0,sizeof(tmp));

//數(shù)組清零

numcpy(b,tmp,i);

while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}//用減法來模擬

}

while(c[0]>0&&c[c[0]]==0)c[0]--;

return;}voidchugao(inta[],intb[],i52

intmain(){

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

init(a);init(b);

chugao(a,b,c);

print(c);

print(a);

return0;}intmain()53

【例6】回文數(shù)【問題描述】

若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個回文數(shù)。又如，對于10進(jìn)制數(shù)87，STEPl：87＋78=165STEP2：165＋561=726STEP3：726＋627＝1353STEP4：1353+3531=4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫一個程序，給定一個N（2＜N＜＝10或N=16）進(jìn)制數(shù)M．求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進(jìn)制運(yùn)算1、當(dāng)前位規(guī)范由%10改為%n2、進(jìn)位處理由/10改為/n3、其他運(yùn)算規(guī)則不變【例6】回文數(shù)54

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intn,a[101],b[101],ans,i;voidinit(inta[])

//將數(shù)串s轉(zhuǎn)化為整數(shù)數(shù)組a{

strings;

cin>>n>>s;//讀入字符串s

memset(a,0,sizeof(a));//數(shù)組a清0

a[0]=s.length();//用a[0]計算字符串s的位數(shù)

for(i=1;i<=a[0];i++)

if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0';

elsea[i]=s[a[0]-i]-'A'+10;}boolcheck(inta[])//判別整數(shù)數(shù)組a是否為回文數(shù){