高精度計算C++版ppt課件.ppt

第一章高精度計算,1,利用計算機進行數(shù)值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數(shù)的位數(shù)可達幾十位甚至幾百位，雖然計算機的計算精度也算較高了，但因受到硬件的限制，往往達不到實際問題所要求的精度。我們可以利用程序設(shè)計的方法去實現(xiàn)這樣的高精度計算。介紹常用的幾種高精度計算的方法。高精度計算中需要處理好以下幾個問題：(1)數(shù)據(jù)的接收方法和存貯方法數(shù)據(jù)的接收和存貯：當輸入的數(shù)很長時，可采用字符串方式輸入，這樣可輸入數(shù)字很長的數(shù)，利用字符串函數(shù)和操作運算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。voidinit(inta)/傳入一個數(shù)組strings;cins;/讀入字符串sa0=s.length();/用a0計算字符串s的位數(shù)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)商和余數(shù)的求法商和余數(shù)處理：視被除數(shù)和除數(shù)的位數(shù)情況進行處理.,3,【例1】高精度加法。輸入兩個正整數(shù)，求它們的和?！痉治觥枯斎雰蓚€數(shù)到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C+語言中任何數(shù)據(jù)類型都有一定的表示范圍。而當兩個被加數(shù)很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數(shù)相加的算法。,如果我們用數(shù)組A、B分別存儲加數(shù)和被加數(shù)，用數(shù)組C存儲結(jié)果。則上例有A1=6，A2=5，A3=8，B1=5，B2=5，B3=2，C4=1，C3=1，C2=1，C1=1，兩數(shù)相加如圖2所示。,4,因此，算法描述如下：intc100;voidadd(inta,intb)/a,b,c都為數(shù)組，分別存儲被加數(shù)、加數(shù)、結(jié)果inti=1,x=0;/x是進位while(i=a數(shù)組長度)|(i=b數(shù)組的長度)ci=ai+bi+x;/第i位相加并加上次的進位x=ci/10;/向高位進位ci%=10;/存儲第i位的值i+;/位置下標變量,5,通常，讀入的兩個整數(shù)用可用字符串來存儲，程序設(shè)計如下：#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);/輸入加數(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;,6,while(lenc=1;i-)coutci;/輸出結(jié)果coutendl;return0;,7,【例2】高精度減法。輸入兩個正整數(shù)，求它們的差。【算法分析】類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數(shù)必須比減數(shù)大，同時需要處理借位。高精度減法的參考程序：#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);/輸入被減數(shù)printf(Inputsubtrahend:);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ù)，結(jié)果為負數(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=1;i-)coutci;/輸出結(jié)果coutendl;return0;,10,【例3】高精度乘法。輸入兩個正整數(shù)，求它們的積。【算法分析】類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加，如圖3、圖4。分析c數(shù)組下標的變化規(guī)律，可以寫出如下關(guān)系式：ci=ci+c”i+由此可見，ci跟ai*bj乘積有關(guān)，跟上次的進位有關(guān)，還跟原ci的值有關(guān)，分析下標規(guī)律，有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的位數(shù)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】回文數(shù)【問題描述】若一個數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數(shù)。例如：給定一個10進制數(shù)56，將56加65（即把56從右向左讀），得到121是一個回文數(shù)。又如，對于10進制數(shù)87，STEPl：8778=165STEP2：165561=726STEP3：7266271353STEP4：1353+3531=4884在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數(shù)4884。寫一個程序，給定一個N（2N10或N=16）進制數(shù)M求最少經(jīng)過幾步可以得到回文數(shù)。如果在30步以內(nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進制運算1、當前位規(guī)范由%10改為%n2、進位處理由/10改為/n3、其他運算規(guī)則不變,24,【參考程序】#include#includeusingnamespacestd;intn,a101,b101,ans,i;voidinit(inta)/將數(shù)串s轉(zhuǎn)化為整數(shù)數(shù)組astrings;cinns;/讀入字符串smemset(a,0,sizeof(a);/數(shù)組a清0a0=s.length();/用a0計算字符串s的位數(shù)for(i=1;i=0,25,voidjia(inta)/整數(shù)數(shù)組a與其反序數(shù)b進行n進制加法運算for(inti=1;i0)a0+;/修正新的a的位數(shù)（a+b最多只能的一個進位）intmain()init(a);if(check(a)cout0endl;return0;ans=0;/步數(shù)初始化為0while(ans+=30)jia(a);if(check(a)coutansendl;return0;coutImpossible;/輸出無解信息return0;,26,【上機練習(xí)】,1、求N！的值【問題描述】用高精度方法，求N！的精確值(N以一般整數(shù)輸入)?！据斎霕永縩i.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】計算A/B的精確值，設(shè)A，B是以一般整數(shù)輸入，計算結(jié)果精確小數(shù)后20位?！据斎霕永縜b.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例】ab.out6/5=1.2,27,3、求n累加和【問題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)?！据斎霕永縥a.in10【輸出樣例】ja.out554、階乘和(sum.pas)【問題描述】已知正整數(shù)N（N=100）,設(shè)S=1!+2!+3!+.N!。其中!表示階乘,即N!=1*2*3*(N-1)*N，如:3!=1*2*3=6。請編程實現(xiàn)：輸入正整數(shù)N,輸出計算結(jié)果S的值?！据斎霕永縮um.in4【輸出樣例】sum.out335、高精度求積(MULTIPLY.PAS)【問題描述】輸入兩個高精度正整數(shù)M和N（M和N均小于100位）?！締栴}求解】求這兩個高精度數(shù)的積?！据斎霕永縈ULTIPLY.IN363【輸出樣例】MULTIPLY.OUT108,28,6、天使的起誓（YUBIKILI.pas）【問題描述】TENSHI非常幸運的被選為掌管智慧之匙的天使。在正式任職之前，她必須和其他新當選的天使一樣，要宣誓。宣誓儀式是每位天使各自表述自己的使命，她們的發(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)了好久都找不到她想找的寶盒。【問題求解】請幫助這位天使找到她想找的寶盒的編號。【輸入格式】從文件YUBIKILI.IN的第一、二行分別讀入正整數(shù)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個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細柱上的圓盤都要保持上小下大的順序；任務(wù)：設(shè)An為2n個圓盤完成上述任務(wù)所需的最少移動次數(shù)