第1章高精度計算

第一章高精度計算

利用計算機(jī)進(jìn)行數(shù)值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計算機(jī)的計算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實際問題所要求的精度。我們可以利用程序設(shè)計的方法去實現(xiàn)這樣的高精度計算。介紹常用的幾種高精度計算的方法。高精度計算中需要處理好以下幾個問題：(1)數(shù)據(jù)的接收方法和存貯方法數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。(2)高精度數(shù)位數(shù)的確定位數(shù)的確定：接收時往往是用字符串的，所以它的位數(shù)就等于字符串的長度。(3)進(jìn)位,借位處理加法進(jìn)位：C[i]:=A[i]+B[i];ifC[i]>=10thenbeginC[i]:=C[i]mod10;C[i+1]:=C[i+1]+1end;

減法借位：ifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10end;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]div10;c[i+j-1]:=xmod10;(4)商和余數(shù)的求法商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理.【例1】輸入兩個正整數(shù)，求它們的和。【分析】

輸入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在pascal語言中任何數(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所示。因此，算法描述如下：procedureadd(a,b;varc);//a,b,c都為數(shù)組，a，b，c分別存儲被加數(shù)、加數(shù)、結(jié)果vari,x:integer;begini:=1；

x:=0; //x是進(jìn)位

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

x:=c[i]div10; //向高位進(jìn)位

c[i]:=c[i]mod10;//存儲第i位的值

i:=i+1//位置指針變量

end通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：programexam1;constmax=200;vara,b,c:array[1..max]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);//輸入加數(shù)

lena:=length(n);//加數(shù)放入a數(shù)組fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');write('Inputaddend:');readln(n);//輸入被加數(shù)

lenb:=length(n);//被加數(shù)放入b數(shù)組

fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');i:=1;x:=0;while(i<=lena)or(i<=lenb)dobeginc[i]:=a[i]+b[i]+x; //兩數(shù)相加，然后加前次進(jìn)位

x:=c[i]div10;//向高位進(jìn)位

c[i]:=c[i]mod10;//保存第i位的值

i:=i+1end;ifx>0then//處理最高進(jìn)位

beginlenc:=i;c[i]:=x;endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);//輸出結(jié)果

writelnend.【例2】高精度減法。輸入兩個正整數(shù)，求它們的差?！舅惴ǚ治觥?/p>

類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：programexam2;constmax=200;vara,b,c:array[1..max]of0..9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputminuend:');readln(n1);//輸入被減數(shù)

write('Inputsubtrahend:');readln(n2);//輸入減數(shù)

if(length(n1)<length(n2))or(length(n1)=length(n2))and(n1<n2)thenbegin//處理被減數(shù)和減數(shù)

n:=n1;n1:=n2;n2:=n;

//交換減數(shù)和被減數(shù)

write('-')//交換了減數(shù)和被減數(shù)，結(jié)果為負(fù)數(shù)

end;lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');i:=1;x:=0;while(i<=lena)or(i<=lenb)dobeginifa[i]<b[i]then //不夠減，那么向高位借1當(dāng)10begina[i]:=a[i]+10;a[i+1]:=a[i+1]-1;end;c[i]:=a[i]-b[i];//對應(yīng)位相減

i:=i+1end;lenc:=i;while(c[lenc]=0)and(lenc>1)dodec(lenc);//最高位的0不輸出

fori:=lencdownto1dowrite(c[i]);end.【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積?！舅惴ǚ治觥?/p>

類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進(jìn)位，同時對每一位進(jì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]div10;C[i+j-1]:=C[i+j-1]mod10;856×254280171221400

圖3A3A2A1

×B2B1

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

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

C6C5C4C3C2C1

圖4高精度乘法的參考程序：constmax=200;vara,b,c:array[1..max]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[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');fori:=1tolenadobeginx:=0; //用于存放進(jìn)位

forj:=1tolenbdobegin//對乘數(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]div10;c[i+j-1]:=c[i+j-1]mod10;end;c[i+j]:=x;

//進(jìn)位

end;lenc:=i+j;while(c[lenc]=0)and(lenc>1)dodec(lenc);fori:=lencdownto1dowrite(c[i]);writelnend.【例4】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）。【算法分析】

做除法時，每一次上商的值都在０～９，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當(dāng)然，為了程序簡潔，可以避免高精度乘法，用0～9次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法。programexam4;constmax=200;vara,c:array[1..max]of0..9;x,b:longint;n1,n2:string;lena,code,i,j:integer;beginwrite('Inputdividend:');readln(n1);write('Inputdivisor:');readln(n2);lena:=length(n1);fori:=1tolenadoa[i]:=ord(n1[i])-ord('0');val(n2,b,code);//字符串n2轉(zhuǎn)成數(shù)值b，code參數(shù)可以省略

x:=0;//按位相除

fori:=1tolenadobeginc[i]:=(x*10+a[i])divb;x:=(x*10+a[i])modb;end;j:=1;while(c[j]=0)and(j<lena)doinc(j);//去除高位的0fori:=jtolenadowrite(c[i]);writelnend.

實質(zhì)上，在做兩個高精度數(shù)運算時候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個數(shù)字，而采取保留多位數(shù)（例如一個整型或長整型數(shù)據(jù)等），這樣，在做運算（特別是乘法運算）時，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運算，其他運算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成。示例：123456789÷45=1’2345’6789÷45=274’3484∵1div45=0，1mod45=1∴取12345div45=274∵12345mod45=15∴取156789div45=3484∴答案為2743484,余數(shù)為156789mod45=9圖5【上機(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.23、求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。請編程實現(xiàn)：輸入正整數(shù)N,輸出計算結(jié)果S的值。【輸入樣例】sum.in4【輸出樣例】sum.out335、高精度求積(MULTIPLY.PAS)【問題描述】輸入兩個高精度正整數(shù)M和N（M和N均小于100位）?！締栴}求解】求這兩個高精度數(shù)的積?！据斎霕永縈ULTIPLY.IN363【輸出樣例】MULTIPLY.OUT1086、天使的起誓（YUBIKILI.pas）【問題描述】TENSHI非常幸運的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當(dāng)選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(fā)言稿被放在N個呈圓形排列的寶盒中。這些寶盒按順時針方向被編上號碼１、２、３……、N-1、N。一開始天使們站在編號為N的寶盒旁。她們各自手上都有一個數(shù)字，代表她們自己的發(fā)言稿所在的盒子是從１號盒子開始按順時針方向的第幾個。例如：有７個盒子，那么如果TENSHI手上的數(shù)字為９，那么她的發(fā)言稿所在盒子就是第２個?，F(xiàn)在天使們開始按照自己手上的數(shù)字來找發(fā)言稿，先找到的就可以先發(fā)言。TENSHI一下子就找到了，于是她最先上臺宣誓：“我將帶領(lǐng)大家開啟NOI之門……”TENSHI宣誓結(jié)束以后，陸續(xù)有天使上臺宣誓?？墒怯幸晃惶焓拐伊撕镁枚颊也坏剿陌l(fā)言稿，原來她手上的數(shù)字M非常大，她轉(zhuǎn)了好久都找不到她想找的寶盒?！締栴}求解