第1章高精度計算(C++版)

1、第一章 高精度計算,利用計算機進行數(shù)值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數(shù)的位數(shù)可達幾十位甚至幾百位，雖然計算機的計算精度也算較高了，但因受到硬件的限制，往往達不到實際問題所要求的精度。我們可以利用程序設計的方法去實現(xiàn)這樣的高精度計算。介紹常用的幾種高精度計算的方法。 高精度計算中需要處理好以下幾個問題： (1)數(shù)據(jù)的接收方法和存貯方法 數(shù)據(jù)的接收和存貯：當輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。 void init(int a) /傳入一個數(shù)組 str

2、ing s; cins; /讀入字符串s a0=s.length(); /用a0計算字符串s的位數(shù) for(i=1;i=a0;i+) ai=sa0-i-0; /將數(shù)串s轉換為數(shù)組a，并倒序存儲 另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù),2) 高精度數(shù)位數(shù)的確定 位數(shù)的確定：接收時往往是用字符串的，所以它的位數(shù)就等于字符串的長度。 (3) 進位,借位處理 加法進位：ci=ai+bi; if (ci=10) ci%=10; +ci+1; 減法借位：if (aibi) -ai+1; ai+=10; ci=ai-bi; 乘法進位：ci+j-1= ai*bj + x + ci+j-1; x = ci+j

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

4、1，C2=1，C1=1，兩數(shù)相加如圖2所示,因此，算法描述如下： int c100; void add(int a,int b) /a,b,c都為數(shù)組，分別存儲被加數(shù)、加數(shù)、結果 int i=1,x=0; /x是進位 while (i=a數(shù)組長度)|(i=b數(shù)組的長度) ci=ai+bi+x; /第i位相加并加上次的進位 x=ci/10; /向高位進位 ci%=10; /存儲第i位的值 i+; /位置下標變量,通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設計如下： #include #include #include using namespace std; int main() char a

5、1100,b1100; 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

6、=1;i-) coutci; /輸出結果 coutendl; return 0;,例2】高精度減法。輸入兩個正整數(shù)，求它們的差。 【算法分析】 類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：#include #include #include using namespace std; int main() int a256,b256,c256,lena,lenb,lenc,i; char n256,n1256,n2256; memset(a,0,sizeof(a); memset(b,0,sizeof(b); memset

7、(c,0,sizeof(c,printf(Input minuend:); gets(n1); /輸入被減數(shù) printf(Input subtrahend:); gets(n2); /輸入減數(shù) if (strlen(n1)n2時，返回正整數(shù)；n1n2時，返回負整數(shù) /處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù) strcpy(n,n1); /將n1數(shù)組的值完全賦值給n數(shù)組 strcpy(n1,n2); strcpy(n2,n); cout-; /交換了減數(shù)和被減數(shù)，結果為負數(shù) lena=strlen(n1); lenb=strlen(n2); for (i=0;i=lena-1;i+) alena-i

8、=int(n1i-0); /被減數(shù)放入a數(shù)組 for (i=0;i=lenb-1;i+) blenb-i=int(n2i-0); /減數(shù)放入b數(shù)組,i=1; while (i1) lenc-; /最高位的0不輸出 for (i=lenc;i=1;i-) coutci; /輸出結果 coutendl; return 0;,例3】高精度乘法。輸入兩個正整數(shù)，求它們的積。 【算法分析】 類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加，如圖3、圖4。 分析c數(shù)組下標的變化規(guī)律，可以寫出如下關系式：ci = ci +c”i +由此可見，c i跟ai

9、*bj乘積有關，跟上次的進位有關，還跟原c i的值有關，分析下標規(guī)律，有ci+j-1= ai*bj+ x + ci+j-1; x=ci+j-1/10 ; ci+j-1%=10,高精度乘法的參考程序： #include #include #include using 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

10、); lena=strlen(a1);lenb=strlen(b1); for (i=0;i=lena-1;i+) alena-i=a1i-48; for (i=0;i=lenb-1;i+) blenb-i=b1i-48,for (i=1;i1) /刪除前導0 lenc-; for (i=lenc;i=1;i-) coutci; coutendl; return 0;,例4】高精度除法。輸入兩個正整數(shù)，求它們的商（做整除）。 【算法分析】 做除法時，每一次上商的值都在，每次求得的余數(shù)連接以后的若干位得到新的被除數(shù)，繼續(xù)做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當

11、然，為了程序簡潔，可以避免高精度除法，用09次循環(huán)減法取代得到商的值。這里，我們討論一下高精度數(shù)除以單精度數(shù)的結果，采取的方法是按位相除法,include #include #include using 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

12、=lena;i+) /按位相除 ci=(x*10+ai)/b; x=(x*10+ai)%b; lenc=1; while (clenc=0,實質上，在做兩個高精度數(shù)運算時候，存儲高精度數(shù)的數(shù)組元素可以不僅僅只保留一個數(shù)字，而采取保留多位數(shù)（例如一個整型或長整型數(shù)據(jù)等），這樣，在做運算（特別是乘法運算）時，可以減少很多操作次數(shù)。例如圖5就是采用4位保存的除法運算，其他運算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成,示例：123456789 45 = 1 2345 6789 45 = 274 3484 1 / 45 = 0 ， 1%45=1 取12345 / 45 = 274 123

13、45 % 45 = 15 取156789/45 = 3484 答案為2743484, 余數(shù)為156789%45 = 9 圖5,例5】高精除以高精，求它們的商和余數(shù)。 【算法分析】 高精除以低精是對被除數(shù)的每一位（這里的“一位”包含前面的余數(shù)，以下都是如此）都除以除數(shù)，而高精除以高精則是用減法模擬除法，對被除數(shù)的每一位都減去除數(shù)，一直減到當前位置的數(shù)字（包含前面的余數(shù)）小于除數(shù)（由于每一位的數(shù)字小于10，所以對于每一位最多進行10次計算）具體實現(xiàn)程序如下,include #include using namespace std; int a101,b101,c101,d,i; void init

14、(int a) string s; cins; /讀入字符串s a0=s.length(); /用a0計算字符串 s的位數(shù) for(i=1;i0;i-) coutai; coutendl; return ;,int compare (int a,int b) /比較a和b的大小關系，若ab則為1，ab0) return 1; /a的位數(shù)大于b則a比b大 if(a00;i-) /從高位到低位比較 if (aibi) return 1; if (aibi) return -1; return 0; /各位都相等則兩數(shù)相等。 void numcpy(int p,int q,int det) /復制p

15、數(shù)組到q數(shù)組從det開始的地方 for (int i=1;i=p0;i+) qi+det-1=pi; q0=p0+det-1;,void jian(int a,int b) /計算a=a-b int flag,i; flag=compare(a,b); /調用比較函數(shù)判斷大小 if (flag=0) a0=0;return; /相等 if(flag=1) /大于 for(i=1;i0,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ù)組清

16、零 numcpy(b,tmp,i); while(compare(a,tmp)=0)ci+;jian(a,tmp); /用減法來模擬 while(c00,int main() 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); return 0;,例6】回文數(shù) 【問題描述】 若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個 10進制數(shù) 56，將 56加 65（即把56從

17、右向左讀），得到 121是一個回文數(shù)。又如，對于10進制數(shù)87， STEPl： 8778= 165 STEP2： 165561= 726 STEP3： 7266271353 STEP4：1353+3531=4884 在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數(shù)4884。 寫一個程序，給定一個N（2N10或N=16）進制數(shù) M求最少經過幾步可以得到回文數(shù)。如果在30步以內（包含30步）不可能得到回文數(shù)，則輸出“Impossible” 【輸入樣例】：9 87 【輸出樣例】：6 【算法分析】 N進制運算 1、當前位規(guī)范由%10改為% n 2、進位處理由/10改為/n 3、其他運

18、算規(guī)則不變,參考程序】 #include #include using namespace std; int n,a101,b101,ans,i; void init(int a) /將數(shù)串s轉化為整數(shù)數(shù)組a string s; cinns; /讀入字符串s memset(a,0,sizeof(a); /數(shù)組a清0 a0=s.length(); /用a0計算字符串s的位數(shù) for(i=1;i=0,void jia(int a) /整數(shù)數(shù)組a與其反序數(shù)b進行n進制加法運算 for(int i=1;i0) a0+; /修正新的a的位數(shù)（a+b最多只能的一個進位） int main() init(a

19、); if(check(a)cout0endl;return 0; ans=0; /步數(shù)初始化為0 while(ans+=30) jia(a); if(check(a)coutansendl;return 0; coutImpossible; /輸出無解信息 return 0;,上機練習,1、求N！的值 【問題描述】 用高精度方法，求N！的精確值(N以一般整數(shù)輸入)。 【輸入樣例】ni.in 10 【輸出樣例】ni.out 3628800 2、求A/B高精度值 【問題描述】 計算A/B的精確值，設A，B是以一般整數(shù)輸入，計算結果精確小數(shù)后20位。 【輸入樣例】ab.in 4 3 【輸出樣例】a

20、b.out 4/3=1.33333333333333333333 【輸入樣例】ab.in 6 5 【輸出樣例】ab.out 6/5=1.2,3、求n累加和 【問題描述】 用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)。 【輸入樣例】ja.in 10 【輸出樣例】ja.out 55 4、階乘和(sum.pas) 【問題描述】 已知正整數(shù)N（N=100）,設S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*3=6。請編程實現(xiàn)：輸入正整數(shù)N,輸出計算結果S的值。 【輸入樣例】sum.in 4 【輸出樣例】sum.out 33 5、高精

21、度求積(MULTIPLY.PAS) 【問題描述】 輸入兩個高精度正整數(shù)M和N（M和N均小于100位）。 【問題求解】 求這兩個高精度數(shù)的積。 【輸入樣例】MULTIPLY.IN 36 3 【輸出樣例】MULTIPLY.OUT 108,6、天使的起誓（YUBIKILI.pas） 【問題描述】 TENSHI非常幸運的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(fā)言稿被放在N個呈圓形排列的寶盒中。這些寶盒按順時針方向被編上號碼、N-1、N。一開始天使們站在編號為N的寶盒旁。她們各自手上都有一個數(shù)字，代表她們自己的發(fā)言稿所在的盒子是從號盒子開始按順時針方向的第幾個。例如：有個盒子，那么如果TENSHI手上的數(shù)字為，那么她的發(fā)言稿所在盒子就是第個?，F(xiàn)在天使們開始按照自己手上的數(shù)字來找發(fā)言稿，先找到的就可以先發(fā)言。TENSHI一下子就找到了，于是她最先上臺宣誓：“我將帶領大家開啟NOI之門”TE