高精度計算9527

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

2、理好以下幾個問題：高精度計算中需要處理好以下幾個問題：(1)數(shù)據(jù)的接收方法和存貯方法數(shù)據(jù)的接收方法和存貯方法 數(shù)據(jù)的接收和存貯：當輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸數(shù)據(jù)的接收和存貯：當輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運算，將每一位數(shù)取出，存入數(shù)組中。入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。(2) 高精度數(shù)位數(shù)的確定高精度數(shù)位數(shù)的確定 位數(shù)的確定：接收時往往是用字符串的，所以它的位數(shù)就等于字符串的長度。位數(shù)的確定：接收時往

3、往是用字符串的，所以它的位數(shù)就等于字符串的長度。(3) 進位進位,借位處理借位處理 加法進位：加法進位：Ci:= Ai+Bi; if Ci=10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end; 減法借位：減法借位：if aibi then begin ai+1:=ai+1-1; ai:=ai+10 end; ci:=ai-bi; 乘法進位：乘法進位：ci+j-1:= ai*bj+ x + ci+j-1; x:= ci+j-1 div 10; ci+j-1 := x mod 10;(4) 商和余數(shù)的求法商和余數(shù)的求法 商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)

4、情況進行處理商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進行處理.【例【例1】輸入兩個正整數(shù)，求它們的和。輸入兩個正整數(shù)，求它們的和?！痉治觥痉治觥?輸入兩個數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在pascal語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當兩個被加數(shù)很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時，我們做加法都采用豎式方法，如圖1。 這樣，我們方便寫出兩個整數(shù)相加的算法。 8 5 6 + 2 5 5 1 1 1 1 圖1 A3 A2 A1+ B3 B2 B1 C4 C3 C2 C1 圖2 如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)

5、組C存儲結(jié)果。則上例有A1=6，A2=5， A3=8，B1=5，B2=5，B3=2，C4=1，C3=1，C2=1，C1=1，兩數(shù)相加如圖2所示。因此，算法描述如下：因此，算法描述如下：procedure add(a,b;var c); /a,b,c都為數(shù)組，a，b，c分別存儲被加數(shù)、加數(shù)、結(jié)果var i,x:integer;begin i:=1； x:=0; /x是進位 while (i=a數(shù)組長度) or(i=b數(shù)組的長度) do begin ci := ai + bi + x; /第i位相加并加上次的進位 x:=ci div 10; /向高位進位 ci := ci mod 10; /存儲第

6、i位的值 i := i + 1 /位置指針變量 end通常，讀入的兩個整數(shù)用可用字符串來存儲，通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：程序設(shè)計如下：program exam1;const max=200; var a,b,c:array1.max of 0.9; n:string; lena,lenb,lenc,i,x:integer;begin write(Input augend:);readln(n); /輸入加數(shù) lena:=length(n); /加數(shù)放入a數(shù)組 for i:=1 to lena do alena-i+1:=ord(ni)-ord(0); write(I

7、nput addend:); readln(n); /輸入被加數(shù) lenb:=length(n); /被加數(shù)放入b數(shù)組 for i:=1 to lenb do blenb-i+1:=ord(ni)-ord(0); i:=1; x:=0; while (i=lena) or(i0 then /處理最高進位 begin lenc:=i;ci:=x; end else lenc:=i-1; for i:=lenc downto 1 do write(ci); /輸出結(jié)果 writelnend.【例【例2】高精度減法。輸入兩個正整數(shù)，求它們的差。高精度減法。輸入兩個正整數(shù)，求它們的差?！舅惴ǚ治觥舅惴?/p>

8、分析】 類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：program exam2;const max=200; var a,b,c:array1.max of 0.9; n,n1,n2:string; lena,lenb,lenc,i,x:integer;begin write(Input minuend:); readln(n1); /輸入被減數(shù) write(Input subtrahend:);readln(n2); /輸入減數(shù) if (length(n1)length(n2) or (length(n1)=lengt

9、h(n2) and (n1n2) then begin /處理被減數(shù)和減數(shù) n:=n1; n1:=n2; n2:=n; /交換減數(shù)和被減數(shù) write(-) /交換了減數(shù)和被減數(shù)，結(jié)果為負數(shù) end; lena:=length(n1); lenb:=length(n2); for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0); for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0); i:=1; x:=0; while (i=lena) or(i=lenb) do begin if ai1) do dec(lenc)

10、; /最高位的0不輸出 for i:=lenc downto 1 do write(ci);end. 【例【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積高精度乘法。輸入兩個正整數(shù)，求它們的積?！舅惴ǚ治觥舅惴ǚ治觥?類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加，如圖3、圖4。 分析C數(shù)組下標的變化規(guī)律，可以寫出如下關(guān)系式：C i = C i +C ”i +由此可見，C i跟Ai*Bj乘積有關(guān)，跟上次的進位有關(guān)，還跟原C i的值有關(guān)，分析下標規(guī)律，有Ci+j-1:= Ai*Bj+ x + Ci+j-1 ; x:= Ci+j-1 div 1

11、0 ; Ci+j-1 := Ci+j-1mod 10; 8 5 6 2 5 4 2 8 0 1 7 1 2 2 1 4 0 0 圖3A 3 A 2 A 1 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1 圖4高精度乘法的參考程序：高精度乘法的參考程序：const max=200;var a,b,c:array1.max of 0.9; n1,n2:string; lena,lenb,lenc,i,j,x:integer;begin write(Input multiplier:); readln(n1); write(Input

12、multiplicand:); readln(n2); lena:=length(n1); lenb:=length(n2); for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0); for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0); for i:=1 to lena do begin x:=0; /用于存放進位 for j:=1 to lenb do begin /對乘數(shù)的每一位進行處理 ci+j-1 := ai*bj + x + ci+j-1; /當前乘積+上次乘積進位+原數(shù) x:=ci+j-1 div 1

13、0; ci+j-1 := ci+j-1 mod 10; end; ci+j:= x; /進位 end; lenc:=i+j; while (clenc=0) and (lenc1) do dec(lenc); for i:=lenc downto 1 do write(ci); writelnend.【例【例4】高精度除法。輸入兩個正整數(shù)，求它們的商高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）。（做整除）?！舅惴ǚ治觥舅惴ǚ治觥?做除法時，每一次上商的值都在，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當然，為

14、了程序簡潔，可以避免高精度乘法，用09次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法。program exam4;const max=200;var a,c:array1.max of 0.9; x,b:longint; n1,n2:string; lena,code,i,j:integer;begin write(Input dividend:); readln(n1); write(Input divisor:); readln(n2); lena:=length(n1); for i:=1 to lena do ai := ord(n1i)

15、 - ord(0); val(n2,b,code); /字符串n2轉(zhuǎn)成數(shù)值b，code參數(shù)可以省略 x:=0; /按位相除 for i:=1 to lena do begin ci:=(x*10+ai) div b; x:=(x*10+ai) mod b; end; j:=1; while (cj=0) and (j0 DOw beginw w := w+1;w aw := x mod 10;w x := x div 10;w end;wend;begin a1 := 1; w := 1; readln(n); for i := 1 to n do jc(i); for j := w down

16、to 1 do write(aj); writeln;end.3、求、求n累加和累加和【問題描述【問題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)。【輸入樣例【輸入樣例】ja.in 10【輸出樣例【輸出樣例】ja.out 55wprogram ex1-3;wvarw i,w,n : longint;w a : array1.100 of longint;wprocedure jia(k : longint);wvarw j,x : longint;wbeginw x := a1+k;w w := 0;w while x0 dow beginw w := w+1;w aw

17、 := x mod 10;w x := aw+1+x div 10;w end;wend;begin assign(input,ja.in); reset(input); assign(output,ja.out); rewrite(output); readln(n); w := 1; for i := 1 to n do jia(i); for i := w downto 1 do write(ai); writeln; close(input); close(output);end.5、蜜蜂路線、蜜蜂路線(bee.pas)【問題描述【問題描述】 一只蜜蜂在下圖所示的數(shù)字蜂房上爬動,已知它

18、只能從標號小的蜂房爬到標號大的相鄰蜂房,現(xiàn)在問你：蜜蜂從蜂房M開始爬到蜂房N，Mlenb then l:=lena w else l:=lenb; for i:=1 to l do ci:=ai+bi; for i:=1 to l do if ci=10 then begin ci:=ci-10; ci+1:=ci+1+1; end; if cl+10 then l:=l+1; a:=b;lena:=lenb;b:=c;lenb:=l; end; begin readln(m,n); if mn then exit else if n-m=1 then writeln(1) else begi

19、n a1:=1;b1:=1; lena:=1;lenb:=1;l:=0; for i:=3 to n-m+1 do add(a,b,c); for i:=l downto 1 do write(ci); end; end. 3、求、求n累加和累加和【問題描述【問題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)?！据斎霕永据斎霕永縥a.in 10【輸出樣例【輸出樣例】ja.out 554、階乘和、階乘和(sum.pas)【問題描述【問題描述】已知正整數(shù)N（N=100）,設(shè)S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*

20、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非常幸運的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當選的天使一樣，要宣誓。宣誓儀式是每位天

21、使各自表述自己的使命，她們的發(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)了好久都找不到她想找的寶盒?！締栴}求解【問題求解】請幫助這位天使找到她想找的寶盒的編號?！据斎敫袷健据斎敫袷健繌奈募UBIKILI.IN的第一、二行分