高精度計(jì)算C++版ppt課件.ppt

第一章高精度計(jì)算,1,利用計(jì)算機(jī)進(jìn)行數(shù)值計(jì)算，有時(shí)會(huì)遇到這樣的問(wèn)題：有些計(jì)算要求精度高，希望計(jì)算的數(shù)的位數(shù)可達(dá)幾十位甚至幾百位，雖然計(jì)算機(jī)的計(jì)算精度也算較高了，但因受到硬件的限制，往往達(dá)不到實(shí)際問(wèn)題所要求的精度。我們可以利用程序設(shè)計(jì)的方法去實(shí)現(xiàn)這樣的高精度計(jì)算。介紹常用的幾種高精度計(jì)算的方法。高精度計(jì)算中需要處理好以下幾個(gè)問(wèn)題：(1)數(shù)據(jù)的接收方法和存貯方法數(shù)據(jù)的接收和存貯：當(dāng)輸入的數(shù)很長(zhǎng)時(shí)，可采用字符串方式輸入，這樣可輸入數(shù)字很長(zhǎng)的數(shù)，利用字符串函數(shù)和操作運(yùn)算，將每一位數(shù)取出，存入數(shù)組中。另一種方法是直接用循環(huán)加數(shù)組方法輸入數(shù)據(jù)。voidinit(inta)/傳入一個(gè)數(shù)組strings;cins;/讀入字符串sa0=s.length();/用a0計(jì)算字符串s的位數(shù)for(i=1;i=10)ci%=10;+ci+1;減法借位：if(aibi)-ai+1;ai+=10;ci=ai-bi;乘法進(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ù)情況進(jìn)行處理.,3,【例1】高精度加法。輸入兩個(gè)正整數(shù)，求它們的和。【分析】輸入兩個(gè)數(shù)到兩個(gè)變量中，然后用賦值語(yǔ)句求它們的和，輸出。但是，我們知道，在C+語(yǔ)言中任何數(shù)據(jù)類(lèi)型都有一定的表示范圍。而當(dāng)兩個(gè)被加數(shù)很大時(shí)，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學(xué)時(shí)，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫(xiě)出兩個(gè)整數(shù)相加的算法。,如果我們用數(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所示。,4,因此，算法描述如下：intc100;voidadd(inta,intb)/a,b,c都為數(shù)組，分別存儲(chǔ)被加數(shù)、加數(shù)、結(jié)果inti=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)變量,5,通常，讀入的兩個(gè)整數(shù)用可用字符串來(lái)存儲(chǔ)，程序設(shè)計(jì)如下：#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】高精度減法。輸入兩個(gè)正整數(shù)，求它們的差?！舅惴ǚ治觥款?lèi)似加法，可以用豎式求減法。在做減法運(yùn)算時(shí)，需要注意的是：被減數(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í)，返回正整數(shù)；n1n2時(shí)，返回負(fù)整數(shù)/處理被減數(shù)和減數(shù)，交換被減數(shù)和減數(shù)strcpy(n,n1);/將n1數(shù)組的值完全賦值給n數(shù)組strcpy(n1,n2);strcpy(n2,n);cout-;/交換了減數(shù)和被減數(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=1;i-)coutci;/輸出結(jié)果coutendl;return0;,10,【例3】高精度乘法。輸入兩個(gè)正整數(shù)，求它們的積?！舅惴ǚ治觥款?lèi)似加法，可以用豎式求乘法。在做乘法運(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)，ci跟ai*bj乘積有關(guān)，跟上次的進(jìn)位有關(guān)，還跟原ci的值有關(guān)，分析下標(biāo)規(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計(jì)算字符串s的位數(shù)for(i=1;i0;i-)coutai;coutbi)return1;if(ai=0)ci+;jian(a,tmp);/用減法來(lái)模擬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ù)【問(wèn)題描述】若一個(gè)數(shù)（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱(chēng)之為回文數(shù)。例如：給定一個(gè)10進(jìn)制數(shù)56，將56加65（即把56從右向左讀），得到121是一個(gè)回文數(shù)。又如，對(duì)于10進(jìn)制數(shù)87，STEPl：8778=165STEP2：165561=726STEP3：7266271353STEP4：1353+3531=4884在這里的一步是指進(jìn)行了一次N進(jìn)制的加法，上例最少用了4步得到回文數(shù)4884。寫(xiě)一個(gè)程序，給定一個(gè)N（2N10或N=16）進(jìn)制數(shù)M求最少經(jīng)過(guò)幾步可以得到回文數(shù)。如果在30步以?xún)?nèi)（包含30步）不可能得到回文數(shù)，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進(jìn)制運(yùn)算1、當(dāng)前位規(guī)范由%10改為%n2、進(jìn)位處理由/10改為/n3、其他運(yùn)算規(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計(jì)算字符串s的位數(shù)for(i=1;i=0,25,voidjia(inta)/整數(shù)數(shù)組a與其反序數(shù)b進(jìn)行n進(jìn)制加法運(yùn)算for(inti=1;i0)a0+;/修正新的a的位數(shù)（a+b最多只能的一個(gè)進(jìn)位）intmain()init(a);if(check(a)cout0endl;return0;ans=0;/步數(shù)初始化為0while(ans+=30)jia(a);if(check(a)coutansendl;return0;coutImpossible;/輸出無(wú)解信息return0;,26,【上機(jī)練習(xí)】,1、求N！的值【問(wèn)題描述】用高精度方法，求N！的精確值(N以一般整數(shù)輸入)?！据斎霕永縩i.in10【輸出樣例】ni.out36288002、求A/B高精度值【問(wèn)題描述】計(jì)算A/B的精確值，設(shè)A，B是以一般整數(shù)輸入，計(jì)算結(jié)果精確小數(shù)后20位。【輸入樣例】ab.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例】ab.out6/5=1.2,27,3、求n累加和【問(wèn)題描述】用高精度方法，求s=1+2+3+n的精確值(n以一般整數(shù)輸入)?！据斎霕永縥a.in10【輸出樣例】ja.out554、階乘和(sum.pas)【問(wèn)題描述】已知正整數(shù)N（N=100）,設(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)題描述】輸入兩個(gè)高精度正整數(shù)M和N（M和N均小于100位）。【問(wèn)題求解】求這兩個(gè)高精度數(shù)的積?！据斎霕永縈ULTIPLY.IN363【輸出樣例】MULTIPLY.OUT108,28,6、天使的起誓（YUBIKILI.pas）【問(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ù)字為，那么她的發(fā)言稿所在盒子就是第個(gè)?，F(xiàn)在天使們開(kāi)始按照自己手上的數(shù)字來(lái)找發(fā)言稿，先找到的就可以先發(fā)言。TENSHI一下子就找到了，于是她最先上臺(tái)宣誓：“我將帶領(lǐng)大家開(kāi)啟NOI之門(mén)”TENSHI宣誓結(jié)束以后，陸續(xù)有天使上臺(tái)宣誓?？墒怯幸晃惶焓拐伊撕镁枚颊也坏剿陌l(fā)言稿，原來(lái)她手上的數(shù)字M非常大，她轉(zhuǎn)了好久都找不到她想找的寶盒?！締?wèn)題求解】請(qǐng)幫助這位天使找到她想找的寶盒的編號(hào)?！据斎敫袷健繌奈募UBIKILI.IN的第一、二行分別讀入正整數(shù)N和M，其中N、M滿足2N108，2M101000【輸出格式】把所求寶盒的編號(hào)輸出到文件YUBIKILI.OUT，文件只有一行（包括換行符）。,樣例一YUBIKILI.IN79,YUBIKILI.OUT2,樣例二YUBIKILI.IN11108,YUBIKILI.OUT9,29,7、Hanoi雙塔問(wèn)題(Noip2007)【問(wèn)題描述】給定A、B、C三根足夠長(zhǎng)的細(xì)柱，在A柱上放有2n個(gè)中間有孔的圓盤(pán)，共有n個(gè)不同的尺寸，每個(gè)尺寸都有兩個(gè)相同的圓盤(pán)，注意這兩個(gè)圓盤(pán)是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤(pán)移到C柱上，在移動(dòng)過(guò)程中可放在B柱上暫存。要求：（1）每次只能移動(dòng)一個(gè)圓盤(pán)；（2）A、B、C三根細(xì)柱上的圓盤(pán)都要保持上小下大的順序；任務(wù)：設(shè)An為2n個(gè)圓盤(pán)完成上述任務(wù)所需的最少移動(dòng)次數(shù)