高精度運算及其應用.doc

Jsoi2010春季函授講義（B2） 13/13高精度運算及其應用一、引言利用計算機進行數值運算，經常會遇到數值太大，超出Longint、int64等系統(tǒng)標準數據類型的有效范圍，如計算mn，而m、n100；有時又會遇到對運算的精度要求特別高的情況，如計算圓周率，要求精確到小數點后100位，此時real、double等數據類型也無能為力。這些情況下，我們都要用“高精度運算”來解決。一般我們將小數點后幾百位或者更多，當然也可能是幾千億幾百億的大數字統(tǒng)稱為高精度數。高精度運算首先要解決存儲問題。一般都是定義一個一維數組來存儲一個高精度數，用每一個數組元素存儲該數的每一位或某幾位。高精度數的讀入可以采用兩種方法，一是采用字符串（String,AnsiString）方式一起讀入，再逐位處理成數字存儲在數組中；另一種方法是一位一位讀入并存儲到數組中。在實際使用時，請大家注意比較各自的優(yōu)、缺點。高精度運算一般都是采用模擬的方法解決。輸出時一定要注意格式和精度。二、高精度運算1、編程實現高精度加法問題描述 輸入兩個正整數（最多250位），輸出它們的和。 比如輸入：99999999999999999999999999999999999999999999999999999912345678999999999999999999999999 輸出：add=1000000000000000000000012345678999999999999999999999998問題分析只要模擬“加法運算”的過程，從低位（對齊）開始逐位相加，最后再統(tǒng)一處理進位即可。參考程序Program ex1(input,output);const max=250;var s1,s2:string; a,b,c:array1.max of byte; l1,l2,l,i:integer;begin writeln(input two large integer:); readln(s1); readln(s2); 用字符串方式讀入兩個高精度數 l1:=length(s1); l2:=length(s2); for i:=1 to max do begin ai:=0;bi:=0;ci:=0;end; 注意一定要初始化 for i:=1 to l1 do ai:=ord(s1l1+1-i)-48; for i:=1 to l2 do bi:=ord(s2l2+1-i)-48; 以上是把兩個高精度數逐位處理并轉存到a、b兩個數組中 if l1l2 then l:=l1 else l:=l2; for i:=1 to l do ci:=ai+bi; 對應位相加 for i:=1 to l do 從低位到高位，統(tǒng)一處理進位 if ci=10 then begin ci:=ci-10; ci+1:=ci+1+1; end; if cl+10 then l:=l+1; write(add=); 輸出 for i:=l downto 1 do write(ci); readln;end.思考和練習1、 如果要一邊加一邊進位，程序怎么修改？你覺得好不好？2、 如果輸入的數再大一點，比如1000位，還好用String類型讀入嗎？程序怎么修改？3、 請你編寫一個高精度減法的程序，注意結果的正負。2、高精度乘法例2、編程求n!的值，n=10 then begin aj+1:=aj+1+aj div 10; 和高精度加法有何區(qū)別？ aj:=aj mod 10; end; while ah+10 do 最高位的進位處理，和高精度加法有何區(qū)別？ begin h:=h+1; ah+1:=ah div 10; ah:=ah mod 10; end; if ah+10 then h:=h+1; end; write(n,!=); 輸出for i:=h downto 1 do write(ai); readln;end.運行示例輸入：input n:500輸出：500!=1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000思考和練習1、 如果要問你n!的結果有多少位，要不要做高精度運算，怎么做最好？請編程完成。2、 如果要問你n!的結果后面有多少個連續(xù)的0，要不要做高精度運算，怎么做最好？請編程完成。例3、輸入兩個高精度正整數m,n（m,n都在200位以內），輸出它們的乘積。問題分析本題為一個高精度數乘以另一個高精度數。算法思想仍然是模擬乘法的過程，用一個數的每一位（從低位開始）逐位與另一個數的每一位相乘，同時處理進位。程序如下：參考程序Program ex3(input,output);const max=200;var s1,s2:string; a,b:array1.max of integer; c:array1.max*max of integer; l1,l2,w,jw,h,i,j,f:longint;begin assign(input,t3.in); 文件輸入輸出 assign(output,t3.out); reset(input); rewrite(output); readln(s1); 讀入及預處理 readln(s2); l1:=length(s1); l2:=length(s2); for i:=1 to max do begin ai:=0;bi:=0;end; for i:=1 to max*max do ci:=0; for i:=1 to l1 do ai:=ord(s1l1+1-i)-48; for i:=1 to l2 do bi:=ord(s2l2+1-i)-48; jw:=0; 逐位乘 for i:=1 to l1 do for j:=1 to l2 do begin f:=ai*bj; jw:=f div 10; f:=f mod 10; w:=i+j-1; cw:=cw+f; cw+1:=cw+1+jw+cw div 10; cw:=cw mod 10; end; h:=l1+l2; while ch=0 do h:=h-1; 判斷最高位 f:=0; 輸出 for i:=h downto 1 do begin write(ci); f:=f+1; if f mod 30=0 then writeln; 30位換一行 end; close(input); close(output)end.運行示例輸入：234234535436546546098948569895349583947593532459999999999999999999999999999999999999999999999999999999999900000000354348594543988989898989898988999898989898898776655432123456789765432456789輸出：830006784256044531573047212363730755471182948895939218737538376740503405551785126396123228045386811816943500803653644720410101010101011000101010101101223344567876543210234567543211000000003、高精度除法例4、計算n/m的值，設n，m是integer范圍內的正整數，要求精確到小數點后500位。問題分析依然采用模擬的方法。由數學知識可知： 除法運算中被除數、除數和商、余數的關系為： 新的被除數 = 10 * 余數；商 = trunc(被除數除數)；余數 = 被除數mod 除數。程序如下：參考程序Program ex4(input,output);const e=500;var a,d,x:array0.e of integer; n,m,t:integer;begin write(input n,m:); readln(n,m); write(n,/,m,=); a0:=n; d0:=n div m; x0:= n mod m; write(d0,.); 初始化處理，得到整數部分的商 for t:=1 to e do begin if xt-1=0 then exit; at:=xt-1 * 10; 將余數擴大10倍 dt:=at div m; write(d t); 計算商 xt:=at mod m; 生成新余數 end; readln;end.運行示例輸入:input n，m: 355 113 輸出:355/113=3.14159292035398230088495575221238938053097345132743362831858407079646017699115044247787610619469026548672566371681415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654867256637168141592920353982300884955752212389380530973451327433628318584070796460176991150442477876106194690265486725663716814159292035398230088495575221238938053097345132743362831858407079646017699115044247787610619469026548672566371681415929203539823008849557522123893805309734513274336練習請修改程序，要求達到如下輸出要求：1、 如果除得盡，則有多少位就輸出多少位，如輸入：1 2，則輸出0.5；2、 如果輸出的是循環(huán)小數，則要用小括號將循環(huán)部分括起來輸出，如輸入：3 7，則輸出：0.(428571)；思考其實，如果是一個真正的高精度數除以另一個高精度數（或單精度數），方法雖然比較明確，但是編程工作還是比較復雜的，留給有興趣的同學自己去思考完成。一般程序中，我們都應該盡量避免做高精度除法。例5、麥森數【問題描述】形如2P-1的素數稱為麥森數，這時P一定也是個素數。但反過來不一定，即如果P是個素數，2P-1不一定也是素數。到1998年底，人們已找到了37個麥森數。最大的一個是P=3021377，它有909526位。麥森數有許多重要應用，它與完全數密切相關。 任務：輸入P（P1000），計算2P-1的位數和最后500位數字（用十進制高精度數表示）輸入：只包含一個整數P（P1000）輸出：第一行：十進制高精度數2P-1的位數。 第2-11行：十進制高精度數2P-1的最后500位數字。（每行輸出50位，共輸出10行，不足500位時高位補0）不必驗證2P-1與P是否為素數。 樣例輸入 1279樣例輸出 38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087問題分析第一問是很簡單的，只需要求一個對數而已，數學原理：十進制正整數n的位數為int(log10(n)+1。所以2P-1的位數int(p*log102)+1 。 第二問的關鍵是高精度乘法和指數冪的運算，而且由于題目要求最后500位數字，所以在計算乘法的時候我們只要求計算乘數的低500位就好了。指數冪的運算不能硬乘，而要采用分治算法，否則就超時了。分治遞歸算法求指數冪是非常經典的，其數學原理是an = a(n div 2)*a(n div 2)*f(a)，其中f(a) = 1(n MOD 2=0)或f(a) = a(n MOD 2=1)。參考程序Program ex5(input,output);Var a,b:array 0.1001 of Longint; n,i,j:Longint; Procedure quick(k:Longint); Var i,c,j,l:Longint; Begin If k=0 Then Exit; quick(k div 2); If k mod 20 Then c:=2 Else c:=1; For l:=1 to 500 Do For i:=1 to 500 Do Inc(bi+l-1,ai*al*c); For i:=1 to 500 DoBegin bi+1:=bi+1+bi div 10; bi:=bi mod 10; End; a:=b; Fillchar(b,sizeof(b),0); End; Begin Readln(n); Writeln(trunc(ln(2)/ln(10)*n)+1); a1:=1; quick(n); Dec(a1); For i:=500 downto 2 Do Begin Write(ai); If i mod 50=1 Then Writeln; End; Writeln(a1); End.例6、組合數的末十位問題描述求出C(n,r)的最后十位，其中00 do t:=t+s s:=s div p end u:=send方法之三是利用公式C（n，r）= C（n-1，r）+ C（n-1，r-1），將計算C（n，r）的過程化為加法來做，該方法即為求楊輝三角中的第n行中的第r列上的數，行列從0開始。以下是一個參考程序，請大家研究，它用的是哪種方法？參考程序program ex6(input,output);const max=20;var a:array0.30000 of integer; t,i,j,n,r,s:longint;b:array1.max of byte;procedure divide(n:integer);var m:integer;begin m:=2; while m=trunc(sqrt(n) do begin while (n mod m=0) and (n0) do begin n:=n div m; am:=am-1; end; m:=m+1; end; an:=an-1;end;procedure times(n:integer);var m:integer;begin m:=2; while m=trunc(sqrt(n) do beginwhile (n mod m=0) and (n0) do begin n:=n div m; am:=am+1; end; m:=m+1; end; an:=an+1;end;procedure add(d:integer);var dd,i,t:longint;begin i:=1;j:=0; while i=max do begin t:=bi*d+j; bi:=t mod 10; j:=t div 10; i:=i+1; end; i:=1;j:=0; while i=max do begin t:=bi+j; bi:=t mod 10; j:=t div 10; i:=i+1;end;end;begin main write(Input n,r:); readln(n,r); fillchar(a,sizeof(a),0); i:=n-r+1;j:=r; repeat if i1 then begin divide(j);j:=j-1;end; until (in) and (j0 do begin add(i); ai:=ai-1; end; end; for j:=10 downto 1 do write(bj);writelnend.部分測試數據Input n,r:10 40000000210Input n,r:1067 6224592928000Input n,r:29999 199995854060848Input n,r:29999 149979718772800Input n,r:29999 273814531330240三、作業(yè)（只要交源程序)1、蜜蜂路線（bee.pas,bee.in,bee.out,時限1秒）問題描述一只蜜蜂在下圖所示的數字蜂房上爬動,已知它只能從標號小的蜂房爬到標號大的相鄰蜂房,現在問你：蜜蜂從蜂房M開始爬到蜂房N，MN=10000，有多少種爬行路線