第一章高精度計算,1,利用計算機進行數值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數的位數可達幾十位甚至幾百位，雖然計算機的計算精度也算較高了，但因受到硬件的限制，往往達不到實際問題所要求的精度。我們可以利用程序設計的方法去實現這樣的高精度計算。介紹常用的幾種高精度計算的方法。高精度計算中需要處理好以下幾個問題：(1)數據的接收方法和存貯方法數據的接收和存貯：當輸入的數很長時，可采用字符串方式輸入，這樣可輸入數字很長的數，利用字符串函數和操作運算，將每一位數取出，存入數組中。另一種方法是直接用循環加數組方法輸入數據。voidinit(inta)/傳入一個數組strings;cins;/讀入字符串sa0=s.length();/用a0計算字符串s的位數for(i=1;i=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-1/10;ci+j-1%=10;(4)商和余數的求法商和余數處理：視被除數和除數的位數情況進行處理.,3,【例1】高精度加法。輸入兩個正整數，求它們的和。【分析】輸入兩個數到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C+語言中任何數據類型都有一定的表示范圍。而當兩個被加數很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數相加的算法。,如果我們用數組A、B分別存儲加數和被加數，用數組C存儲結果。則上例有A1=6，A2=5，A3=8，B1=5，B2=5，B3=2，C4=1，C3=1，C2=1，C1=1，兩數相加如圖2所示。,4,因此，算法描述如下：intc100;voidadd(inta,intb)/a,b,c都為數組，分別存儲被加數、加數、結果inti=1,x=0;/x是進位while(i=a數組長度)|(i=b數組的長度)ci=ai+bi+x;/第i位相加并加上次的進位x=ci/10;/向高位進位ci%=10;/存儲第i位的值i+;/位置下標變量,5,通常，讀入的兩個整數用可用字符串來存儲，程序設計如下：#include#include#includeusingnamespacestd;intmain()chara1100,b1100;inta100,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);/輸入加數與被加數lena=strlen(a1);lenb=strlen(b1);for(i=0;i=lena-1;i+)alena-i=a1i-48;/加數放入a數組for(i=0;i=lenb-1;i+)blenb-i=b1i-48;/加數放入b數組lenc=1;x=0;,6,while(lenc=1;i-)coutci;/輸出結果coutendl;return0;,7,【例2】高精度減法。輸入兩個正整數，求它們的差。【算法分析】類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數必須比減數大，同時需要處理借位。高精度減法的參考程序：#include#include#includeusingnamespacestd;intmain()inta256,b256,c256,lena,lenb,lenc,i;charn256,n1256,n2256;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);,8,printf(Inputminuend:);gets(n1);/輸入被減數printf(Inputsubtrahend:);gets(n2);/輸入減數if(strlen(n1)n2時，返回正整數；n1n2時，返回負整數/處理被減數和減數，交換被減數和減數strcpy(n,n1);/將n1數組的值完全賦值給n數組strcpy(n1,n2);strcpy(n2,n);cout-;/交換了減數和被減數，結果為負數lena=strlen(n1);lenb=strlen(n2);for(i=0;i=lena-1;i+)alena-i=int(n1i-0);/被減數放入a數組for(i=0;i=1;i-)coutci;/輸出結果coutendl;return0;,10,【例3】高精度乘法。輸入兩個正整數，求它們的積。【算法分析】類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加，如圖3、圖4。分析c數組下標的變化規律，可以寫出如下關系式：ci=ci+c”i+由此可見，ci跟ai*bj乘積有關，跟上次的進位有關，還跟原ci的值有關，分析下標規律，有ci+j-1=ai*bj+x+ci+j-1;x=ci+j-1/10;ci+j-1%=10;,11,高精度乘法的參考程序：#include#include#includeusingnamespacestd;intmain()chara1100,b1100;inta100,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-48;for(i=0;i=1;i-)coutci;coutb;lena=strlen(a1);for(i=0;is;/讀入字符串sa0=s.length();/用a0計算字符串s的位數for(i=1;i0;i-)coutai;coutbi)return1;if(ai=0)ci+;jian(a,tmp);/用減法來模擬while(c00,22,intmain()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);return0;,23,【例6】回文數【問題描述】若一個數（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數。例如：給定一個10進制數56，將56加65（即把56從右向左讀），得到121是一個回文數。又如，對于10進制數87，STEPl：8778=165STEP2：165561=726STEP3：7266271353STEP4：1353+3531=4884在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數4884。寫一個程序，給定一個N（2N10或N=16）進制數M求最少經過幾步可以得到回文數。如果在30步以內（包含30步）不可能得到回文數，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進制運算1、當前位規范由%10改為%n2、進位處理由/10改為/n3、其他運算規則不變,24,【參考程序】#include#includeusingnamespacestd;intn,a101,b101,ans,i;voidinit(inta)/將數串s轉化為整數數組astrings;cinns;/讀入字符串smemset(a,0,sizeof(a);/數組a清0a0=s.length();/用a0計算字符串s的位數for(i=1;i=0,25,voidjia(inta)/整數數組a與其反序數b進行n進制加法運算for(inti=1;i0)a0+;/修正新的a的位數（a+b最多只能的一個進位）intmain()init(a);if(check(a)cout0endl;return0;ans=0;/步數初始化為0while(ans+=30)jia(a);if(check(a)coutansendl;return0;coutImpossible;/輸出無解信息return0;,26,【上機練習】,1、求N！的值【問題描述】用高精度方法，求N！的精確值(N以一般整數輸入)。【輸入樣例】ni.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】計算A/B的精確值，設A，B是以一般整數輸入，計算結果精確小數后20位。【輸入樣例】ab.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例】ab.out6/5=1.2,27,3、求n累加和【問題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數輸入)。【輸入樣例】ja.in10【輸出樣例】ja.out554、階乘和(sum.pas)【問題描述】已知正整數N（N=100）,設S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*3=6。請編程實現：輸入正整數N,輸出計算結果S的值。【輸入樣例】sum.in4【輸出樣例】sum.out335、高精度求積(MULTIPLY.PAS)【問題描述】輸入兩個高精度正整數M和N（M和N均小于100位）。【問題求解】求這兩個高精度數的積。【輸入樣例】MULTIPLY.IN363【輸出樣例】MULTIPLY.OUT108,28,6、天使的起誓（YUBIKILI.pas）【問題描述】TENSHI非常幸運的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發言稿被放在N個呈圓形排列的寶盒中。這些寶盒按順時針方向被編上號碼、N-1、N。一開始天使們站在編號為N的寶盒旁。她們各自手上都有一個數字，代表她們自己的發言稿所在的盒子是從號盒子開始按順時針方向的第幾個。例如：有個盒子，那么如果TENSHI手上的數字為，那么她的發言稿所在盒子就是第個。現在天使們開始按照自己手上的數字來找發言稿，先找到的就可以先發言。TENSHI一下子就找到了，于是她最先上臺宣誓：“我將帶領大家開啟NOI之門”TENSHI宣誓結束以后，陸續有天使上臺宣誓。可是有一位天使找了好久都找不到她的發言稿，原來她手上的數字M非常大，她轉了好久都找不到她想找的寶盒。【問題求解】請幫助這位天使找到她想找的寶盒的編號。【輸入格式】從文件YUBIKILI.IN的第一、二行分別讀入正整數N和M，其中N、M滿足2N108，2M101000【輸出格式】把所求寶盒的編號輸出到文件YUBIKILI.OUT，文件只有一行（包括換行符）。,樣例一YUBIKILI.IN79,YUBIKILI.OUT2,樣例二YUBIKILI.IN11108,YUBIKILI.OUT9,29,7、Hanoi雙塔問題(Noip2007)【問題描述】給定A、B、C三根足夠長的細柱，在A柱上放有2n個中間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區分的（下圖為n=3的情形）。現要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細柱上的圓盤都要保持上小下大的順序；任務：設An為2n個圓盤完成上述任務所需的最少移動次數