高精度計(jì)算C版

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

2、理好以下幾個(gè)問(wèn)題：高精度計(jì)算中需要處理好以下幾個(gè)問(wèn)題：(1)數(shù)據(jù)的接收方法和存貯方法數(shù)據(jù)的接收方法和存貯方法 數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長(zhǎng)時(shí)，可采用字符串方式輸入，數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長(zhǎng)時(shí)，可采用字符串方式輸入，這樣可輸入數(shù)字很長(zhǎng)的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取這樣可輸入數(shù)字很長(zhǎng)的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。void init(int a) /傳入一個(gè)數(shù)組傳入一個(gè)數(shù)組 string s; cins; /讀入字符串讀入字符串s a0=s.le

3、ngth(); /用用a0計(jì)算字符串計(jì)算字符串s的位數(shù)的位數(shù) for(i=1;i=10) ci%=10; +ci+1; 減法借位：減法借位：if (aibi) -ai+1; ai+=10; ci=ai-bi;乘法進(jìn)位：乘法進(jìn)位：ci+j-1= ai*bj + x + ci+j-1; x = ci+j-1/10; ci+j-1 %= 10;(4) 商和余數(shù)的求法商和余數(shù)的求法 商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進(jìn)行處理.【例【例1】高精度】高精度加加法。輸入兩個(gè)正整數(shù)，求它們的和。法。輸入兩個(gè)正整數(shù)，求它們的和?！痉治觥俊痉治觥?輸入兩個(gè)數(shù)到兩個(gè)

4、變量中，然后用賦值語(yǔ)句求它們的和，輸出。但是，我們知道，在c+語(yǔ)言中任何數(shù)據(jù)類型都有一定的表示范圍。而當(dāng)兩個(gè)被加數(shù)很大時(shí)，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時(shí)，我們做加法都采用豎式方法，如圖1。 這樣，我們方便寫(xiě)出兩個(gè)整數(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分別存儲(chǔ)加數(shù)和被加數(shù)，用數(shù)組c存儲(chǔ)結(jié)果。則上例有a1=6，a2=5， a3=8，b1=5，b2=5，b3=2，c4=1，c3=1，c2=1，c1=1，兩數(shù)相加如圖2所示。因此，算法描述如下：因此

5、，算法描述如下：int c100;void add(int a,int b) /a,b,c都為數(shù)組，分別存儲(chǔ)被加數(shù)、加數(shù)、結(jié)果 int i=1,x=0; /x是進(jìn)位 while (i=a數(shù)組長(zhǎng)度)|(i=b數(shù)組的長(zhǎng)度)ci=ai+bi+x; /第i位相加并加上次的進(jìn)位x=ci/10; /向高位進(jìn)位ci%=10; /存儲(chǔ)第i位的值i+; /位置下標(biāo)變量 通常，讀入的兩個(gè)整數(shù)用可用字符串來(lái)存儲(chǔ)，通常，讀入的兩個(gè)整數(shù)用可用字符串來(lái)存儲(chǔ)，程序設(shè)計(jì)如下：程序設(shè)計(jì)如下：#include#include#includeusing namespace std;int main()char a1100,b110

6、0; int a100,b100,c100,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+) alena-i=a1i-48; /加數(shù)放入a數(shù)組 for (i=0;i=lenb-1;i+) blenb-i=b1i-48; /加數(shù)放入b數(shù)組 lenc =1; x=0; while (lenc =lena|le

7、nc =1;i-) coutci; /輸出結(jié)果coutendl;return 0; 【例【例2】高精度減法。輸入兩個(gè)正整數(shù)，求它們的差?！扛呔葴p法。輸入兩個(gè)正整數(shù)，求它們的差?！舅惴ǚ治觥俊舅惴ǚ治觥?類似加法，可以用豎式求減法。在做減法運(yùn)算時(shí)，需要注意的是：被減數(shù)必須比減數(shù)大，同時(shí)需要處理借位。高精度減法的參考程序：#include#include#includeusing namespace std;int main()int a256,b256,c256,lena,lenb,lenc,i;char n256,n1256,n2256;memset(a,0,sizeof(a);memset

8、(b,0,sizeof(b);memset(c,0,sizeof(c);printf(input minuend:); gets(n1); /輸入被減數(shù)printf(input subtrahend:); gets(n2); /輸入減數(shù) if (strlen(n1)strlen(n2)|(strlen(n1)=strlen(n2)&strcmp(n1,n2)n2時(shí)，返回正整數(shù)；n1n2時(shí)，返回負(fù)整數(shù) /處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù) strcpy(n,n1); /將n1數(shù)組的值完全賦值給n數(shù)組 strcpy(n1,n2); strcpy(n2,n); cout-; /交換了減數(shù)和被

9、減數(shù)，結(jié)果為負(fù)數(shù) lena=strlen(n1); lenb=strlen(n2); for (i=0;i=lena-1;i+) alena-i=int(n1i-0); /被減數(shù)放入a數(shù)組 for (i=0;i=lenb-1;i+) blenb-i=int(n2i-0); /減數(shù)放入b數(shù)組 i=1;while (i=lena|i=lenb)if (ai1) lenc-; /最高位的0不輸出 for (i=lenc;i=1;i-) coutci; /輸出結(jié)果coutendl;return 0;【例【例3】高精度乘法。輸入兩個(gè)正整數(shù)，求它們的積】高精度乘法。輸入兩個(gè)正整數(shù)，求它們的積?！舅惴ǚ治觥?/p>

10、【算法分析】 類似加法，可以用豎式求乘法。在做乘法運(yùn)算時(shí)，同樣也有進(jìn)位，同時(shí)對(duì)每一位進(jìn)行乘法運(yùn)算時(shí)，必須進(jìn)行錯(cuò)位相加，如圖3、圖4。分析c數(shù)組下標(biāo)的變化規(guī)律，可以寫(xiě)出如下關(guān)系式：ci = ci +c”i +由此可見(jiàn)，c i跟ai*bj乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原c i的值有關(guān)，分析下標(biāo)規(guī)律，有ci+j-1= ai*bj+ x + ci+j-1; x=ci+j-1/10 ; ci+j-1%=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

11、 c 2 c 1 圖4高精度乘法的參考程序：高精度乘法的參考程序：#include#include#includeusing namespace std;int main() char a1100,b1100; int a100,b100,c100,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+) alena-i=a1i-4

12、8; for (i=0;i=lenb-1;i+) blenb-i=b1i-48; for (i=1;i=lena;i+) x=0; /用于存放進(jìn)位用于存放進(jìn)位 for (j=1;j1) /刪除前導(dǎo)刪除前導(dǎo)0lenc-;for (i=lenc;i=1;i-)coutci;coutendl;return 0;【例【例4】高精度除法。輸入兩個(gè)正整數(shù)，求它們的商】高精度除法。輸入兩個(gè)正整數(shù)，求它們的商（做整除）。（做整除）?！舅惴ǚ治觥俊舅惴ǚ治觥?做除法時(shí)，每一次上商的值都在，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時(shí)，要涉及到乘法運(yùn)算和減法運(yùn)算，還有移位處理。

13、當(dāng)然，為了程序簡(jiǎn)潔，可以避免高精度除法，用09次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結(jié)果，采取的方法是按位相除法。#include#include#includeusing namespace std;int main()char a1100,c1100; int a100,c100,lena,i,x=0,lenc,b; memset(a,0,sizeof(a); memset(c,0,sizeof(c); gets(a1); cinb; lena=strlen(a1); for (i=0;i=lena-1;i+)ai+1=a1i-48; for (i=1;i=le

14、na;i+) /按位相除ci=(x*10+ai)/b; x=(x*10+ai)%b; lenc=1; while (clenc=0&lenclena) lenc+; /刪除前導(dǎo)0 for (i=lenc;i=lena;i+) coutci; coutendl; return 0; 實(shí)質(zhì)上，在做兩個(gè)高精度數(shù)運(yùn)算時(shí)候，存儲(chǔ)高精度數(shù)的數(shù)組元素可以不僅僅只保留一個(gè)數(shù)字，而采取保留多位數(shù)（例如一個(gè)整型或長(zhǎng)整型數(shù)據(jù)等），這樣，在做運(yùn)算（特別是乘法運(yùn)算）時(shí)，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運(yùn)算，其他運(yùn)算也類似。具體程序可以修改上述例題予以解決，程序請(qǐng)讀者完成。示例：1234567

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

16、序如下： #include#includeusing namespace std;int a101,b101,c101,d,i; void init(int a) string s; cins; /讀入字符串s a0=s.length(); /用a0計(jì)算字符串 s的位數(shù) for(i=1;i=a0;i+)ai=sa0-i-0; /將數(shù)串s轉(zhuǎn)換為數(shù)組a，并倒序存儲(chǔ) void print(int a) /打印輸出if (a0=0)cout00;i-) coutai;coutb則為1，ab0) return 1; /a的位數(shù)大于b則a比b大 if(a00;i-) /從高位到低位比較 if (aibi)

17、 return 1; if (aibi) return -1; return 0; /各位都相等則兩數(shù)相等。 void numcpy(int p,int q,int det) /復(fù)制p數(shù)組到q數(shù)組從det開(kāi)始的地方for (int i=1;i=p0;i+) qi+det-1=pi;q0=p0+det-1; void jian(int a,int b) /計(jì)算a=a-b int flag,i; flag=compare(a,b); /調(diào)用比較函數(shù)判斷大小 if (flag=0) a0=0;return; /相等 if(flag=1) /大于 for(i=1;i=a0;i+) if(ai0&

18、;aa0=0) a0-; /修正a的位數(shù) return; void chugao(int a,int b,int c)int tmp101; c0=a0-b0+1;for (int i=c0;i0;i-)memset(tmp,0,sizeof(tmp); /數(shù)組清零 numcpy(b,tmp,i);while(compare(a,tmp)=0)ci+;jian(a,tmp); /用減法來(lái)模擬while(c00&cc0=0)c0-;return ; int main() memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset(c,0,size

19、of(c); init(a);init(b); chugao(a,b,c); print(c); print(a); return 0; 【例6】回文數(shù)【問(wèn)題描述】若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個(gè) 10進(jìn)制數(shù) 56，將 56加 65（即把56從右向左讀），得到 121是一個(gè)回文數(shù)。又如，對(duì)于10進(jìn)制數(shù)87， stepl： 8778= 165 step2： 165561= 726 step3： 7266271353 step4：1353+3531=4884 在這里的一步是指進(jìn)行了一次n進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。 寫(xiě)

20、一個(gè)程序，給定一個(gè)n（2n10或n=16）進(jìn)制數(shù) m求最少經(jīng)過(guò)幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“impossible” 【輸入樣例】：9 87【輸出樣例】：6【算法分析】 n進(jìn)制運(yùn)算 1、當(dāng)前位規(guī)范由%10改為% n 2、進(jìn)位處理由/10改為/n 3、其他運(yùn)算規(guī)則不變 【參考程序】#include#includeusing namespace std;int n,a101,b101,ans,i;void init(int a) /將數(shù)串s轉(zhuǎn)化為整數(shù)數(shù)組a string s; cinns; /讀入字符串s memset(a,0,sizeof(a); /數(shù)

21、組a清0 a0=s.length(); /用a0計(jì)算字符串s的位數(shù) for(i=1;i=0&sa0-i=9) ai=sa0-i-0; else ai=sa0-i-a+10;bool check(int a) /判別整數(shù)數(shù)組a是否為回文數(shù) for(i=1;i=a0;i+) if(ai!=aa0-i+1)return false; return true; void jia(int a) /整數(shù)數(shù)組a與其反序數(shù)b進(jìn)行n進(jìn)制加法運(yùn)算for(int i=1;i=a0;i+)bi=aa0-i+1; /反序數(shù)bfor(int i=1;i=a0;i+) ai+=bi; /逐位相加for(int i=

22、1;i0) a0+; /修正新的a的位數(shù)（a+b最多只能的一個(gè)進(jìn)位） int main()init(a);if(check(a)cout0endl;return 0;ans=0; /步數(shù)初始化為0while(ans+=30) jia(a);if(check(a)coutansendl;return 0;coutimpossible; /輸出無(wú)解信息return 0;【上機(jī)練習(xí)】1、求、求n！的值！的值【問(wèn)題描述】【問(wèn)題描述】 用高精度方法，求n！的精確值(n以一般整數(shù)輸入)。【輸入樣例】【輸入樣例】ni.in 10【輸出樣例】【輸出樣例】ni.out 36288002、求、求a/b高精度值高精

23、度值【問(wèn)題描述】【問(wèn)題描述】 計(jì)算a/b的精確值，設(shè)a，b是以一般整數(shù)輸入，計(jì)算結(jié)果精確小數(shù)后20位?！据斎霕永俊据斎霕永縜b.in 4 3【輸出樣例】【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】【輸入樣例】ab.in 6 5【輸出樣例】【輸出樣例】ab.out6/5=1.23、求、求n累加和累加和【問(wèn)題描述】【問(wèn)題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)?！据斎霕永俊据斎霕永縥a.in 10【輸出樣例】【輸出樣例】ja.out 554、階乘和、階乘和(sum.pas)【問(wèn)題描述】【問(wèn)題描述】已知正整數(shù)n（n=10

24、0）,設(shè)s=1!+2!+3!+.n!。其中!表示階乘,即n!=1*2*3*(n-1)*n，如:3!=1*2*3=6。請(qǐng)編程實(shí)現(xiàn)：輸入正整數(shù)n,輸出計(jì)算結(jié)果s的值?！据斎霕永俊据斎霕永縮um.in4【輸出樣例】【輸出樣例】sum.out335、高精度求積、高精度求積(multiply.pas)【問(wèn)題描述】【問(wèn)題描述】輸入兩個(gè)高精度正整數(shù)m和n（m和n均小于100位）?！締?wèn)題求解】【問(wèn)題求解】求這兩個(gè)高精度數(shù)的積?！据斎霕永俊据斎霕永縨ultiply.in363【輸出樣例】【輸出樣例】multiply.out1086、天使的起誓（、天使的起誓（yubikili.pas）【問(wèn)題描述】【問(wèn)題描述】tenshi非常幸運(yùn)的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當(dāng)選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(fā)言稿被放在n個(gè)呈圓形排列的寶盒中。這些寶盒按順時(shí)針?lè)较虮痪幧咸?hào)碼、n-1、n。一開(kāi)始天使們站在編號(hào)為n的寶盒旁。她們各自手上都有一個(gè)數(shù)字，代表她們自己的發(fā)言稿所在的盒子是從號(hào)盒子開(kāi)始按順時(shí)針?lè)较虻牡趲讉€(gè)。例如：有個(gè)盒子，那么如果tenshi手上的數(shù)字為，那么