第六講模擬與高精度計(jì)算ACM算法與程序設(shè)計(jì)數(shù)學(xué)科學(xué)學(xué)院：汪小平wxiaoping325@163.com模擬與高精度計(jì)算第1頁現(xiàn)實(shí)中有些問題難以找到公式或規(guī)律來處理。只能按照一定步驟不停地做下去，最終才能得到答案。這么問題，用計(jì)算機(jī)來處理十分適當(dāng)，只要能讓計(jì)算機(jī)模擬人在處理問題時(shí)行為即可。這一類問題能夠稱之為“模擬題”。模擬與高精度計(jì)算第2頁摘花生

/problem?id=2950問題描述魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)覺路邊通告牌上貼著一張小小紙條：“歡迎無償品嘗我種花生！——熊字”。魯賓遜先生和多多都很開心，因?yàn)榛ㄉ撬麄冏類?。在通告牌背后，路邊真有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。模擬與高精度計(jì)算第3頁有經(jīng)驗(yàn)多多一眼就能看出，每棵花生植株下花生有多少。為了訓(xùn)練多多算術(shù)，魯賓遜先生說：“你先找出花生最多植株，去采摘它花生；然后再找出剩下植株里花生最多，去采摘它花生；依這類推，不過你一定要在我限定時(shí)間內(nèi)回到路邊?！蔽覀兗俣ǘ喽嘣诿總€(gè)單位時(shí)間內(nèi)，能夠做以下四件事情中一件：(1)從路邊跳到最靠近路邊（即第一行）某棵花生植株；(2)從一棵植株跳到前后左右與之相鄰另一棵植株；(3)采摘一棵植株下花生；(4)從最靠近路邊（即第一行）某棵花生植株跳回路邊。現(xiàn)在給定一塊花生田大小和花生分布，請(qǐng)問在限定時(shí)間內(nèi)，多多最多能夠采到多少個(gè)花生？注意可能只有部分植株下面長有花生，假設(shè)這些植株下花生個(gè)數(shù)各不相同。模擬與高精度計(jì)算第4頁比如在圖2所表示花生田里，只有位于(2,5),(3,7),(4,2),(5,4)植株下長有花生，個(gè)數(shù)分別為13,7,15,9。沿著圖示路線，多多在21個(gè)單位時(shí)間內(nèi)，最多能夠采到37個(gè)花生。

模擬與高精度計(jì)算第5頁輸入格式輸入第一行包含一個(gè)整數(shù)T，表示數(shù)據(jù)組數(shù)。

每組輸入第一行包含三個(gè)整數(shù)，M,N和K，用空格隔開；表示花生田大小為M*N（1<=M,N<=50），多多采花生限定時(shí)間為K（0<=K<=1000）個(gè)單位時(shí)間。接下來M行，每行包含N個(gè)非負(fù)整數(shù)，也用空格隔開；第i+1行第j個(gè)整數(shù)Pij（0<=Pij<=500）表示花生田里植株(i,j)下花生數(shù)目，0表示該植株下沒有花生。輸出要求輸出包含T行，每一行只包含一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多能夠采到花生個(gè)數(shù)。模擬與高精度計(jì)算第6頁樣例輸入672100000000000130000000070150000000090000000000

樣例輸出37模擬與高精度計(jì)算第7頁找規(guī)律得到一個(gè)以花生矩陣作為自變量公式來處理這個(gè)問題，是不現(xiàn)實(shí)。結(jié)果只能是做了才知道。即走進(jìn)花生地．每次要采下一株花生之前，先計(jì)算一下剩下時(shí)間夠不夠走到那株花生，采摘，并從那株花生走回到路上。假如時(shí)問夠．則走過去采摘；假如時(shí)間不夠，則采摘活動(dòng)到此結(jié)束。設(shè)二維數(shù)組aField存放花生地信息。然而，用aField[0][0]還是aField[1][1]對(duì)應(yīng)花生地左上角是值得思索一下。因?yàn)閺牡乩锏铰飞线€需要1個(gè)單位時(shí)間，題目中坐標(biāo)又都是從1開始。所以若aField[1][1]對(duì)應(yīng)花生地左上角，則從aField[i][j]點(diǎn)回到路上所需時(shí)間就是i，這么更為方便和自然，不易犯錯(cuò)。解題思緒模擬與高精度計(jì)算第8頁參考程序#include<stdio.h>#include<stdlib.h>#include<memory.h>#include<math.h>intT,M,N,K;#defineMAX_NUM55intaField[MAX_NUM][MAX_NUM];main(){scanf(“%d,&T);for(intt=0;t<T;t++){scanf(“%d%d％d”,&M,&N,&K);//花生地左上角對(duì)應(yīng)數(shù)組元素是aField[1][1]，路縱坐標(biāo)是0for(intm=1;m<=M;m++)for(intn=1;n<=N;n++)scanf(“％d”，&afield[m][n]);intnTotalPeanuts=0;//摘到花生總數(shù)intnTotalTime=O;//已經(jīng)花去時(shí)問intnCuri=0，nCurj;//當(dāng)前位置坐標(biāo)，//nCuri代表縱坐標(biāo)，開始是在路上，所以初值為0模擬與高精度計(jì)算第9頁

while(nTotalTime<K){//假如還有時(shí)間intnMax=0,nMaxi,nMaxj;//最大花生數(shù)目，//及其所處位置for(inti=1;i<=M;i++)//下面這個(gè)循環(huán)尋找下一個(gè)//最大花生數(shù)目及其位置for(intj=1;j<=N;j++)if(nMax<aFieId[i][j]){nMax=aFieId[i][j];nMaxi=i;nMaxj=j;}if(nMax==0)//地里已經(jīng)沒有花生了break;if(nCuri==0)nCurj=nMaxj;//假如當(dāng)前位置是在路上，那么//應(yīng)走到橫坐標(biāo)nMaxj處，再進(jìn)人花生地模擬與高精度計(jì)算第10頁//下一行看剩下時(shí)間是否足夠走到(nMaxi，nMaxj)處，//摘取花生，并回到路上if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri)

+abs(nMaxj-nCurj)<=K){//下一行加上走到新位置，以及摘花生時(shí)問nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj);nCuri=nMaxi;nCurj=nMaxj;//走到新位置nTotaiPeanuts+=aField[nMaxi][nMaxj];aField[nMaxi][nMaxj]=0;//摘走花生}elsebreak；}printf(“%d\n”,nTotalPeanuts);}}模擬與高精度計(jì)算第11頁常見問題這個(gè)題目應(yīng)該仔細(xì)閱讀。往往沒有看到每次只能拿剩下花生株中最大，而是希望找到一個(gè)在要求時(shí)間內(nèi)能夠拿最多花生組合，把題目變成了另外一道題。沒有讀到‘‘沒有兩株花生株花生數(shù)目相同”條件，所以把題目復(fù)雜化了。這個(gè)題目是假設(shè)猴子在取花生過程中不會(huì)回到大路上，而有些同學(xué)思索是否可能在中間回到大路上，因?yàn)轭}目沒說在大路上移動(dòng)要花時(shí)間，所以有可能中途出來再進(jìn)去摘花生更多。本題解法即使直觀．不過有一個(gè)弊端．就是每次在尋找下一個(gè)最大花生植株時(shí)，都要遍歷整個(gè)矩陣，效率不高。用什么方法才能高效率地找到下一個(gè)最大花生植株?模擬與高精度計(jì)算第12頁顯示器1、鏈接地址

/problem?id=27452、問題描述

你一個(gè)朋友買了一臺(tái)電腦。他以前只用過計(jì)算器，因?yàn)殡娔X顯示器上顯示數(shù)字樣子和計(jì)算器是不一樣，所以當(dāng)他使用電腦時(shí)候會(huì)比較郁悶。為了幫助他，你決定寫一個(gè)程序把在電腦上數(shù)字顯示得像計(jì)算器上一樣。模擬與高精度計(jì)算第13頁輸入數(shù)據(jù)輸入包含若干行，每行表示一個(gè)要顯示數(shù)。每行有兩個(gè)整數(shù)s和n(1<=s<=10,0<=n<=99999999)，這里n是要顯示數(shù)，s是要顯示數(shù)尺寸。假如某行輸入包含兩個(gè)0，表示輸入結(jié)束。這行不需要處理。輸出要求顯示方式是：用s個(gè)'-'表示一個(gè)水平線段，用s個(gè)'|'表示一個(gè)垂直線段。這種情況下，每一個(gè)數(shù)字需要占用s+2列和2s+3行。另外，在兩個(gè)數(shù)字之間要輸出一個(gè)空白列。在輸出完每一個(gè)數(shù)之后，輸出一個(gè)空白行。注意：輸出中空白地方都要用空格來填充。模擬與高精度計(jì)算第14頁

輸入樣例21234536789000輸出樣例模擬與高精度計(jì)算第15頁一個(gè)計(jì)算器上數(shù)字顯示單元，能夠看作由以下編號(hào)從1到77個(gè)筆畫組成：3、解題思緒模擬與高精度計(jì)算第16頁那么，我們能夠說，數(shù)字8覆蓋了全部筆畫，數(shù)字7覆蓋筆畫1、3和6，而數(shù)字1覆蓋筆畫3、6。注意，每個(gè)筆畫都是由s個(gè)’-‘或s個(gè)’|’組成。輸出時(shí)，先輸出第1行，即整數(shù)n中全部數(shù)字里筆畫1，然后輸出第2行到第s+1行，即全部數(shù)字筆畫2和筆畫3，接下來是第s+2行，即全部數(shù)字筆畫4，再接下來是第s+3行到2×s+2行，，就是全部數(shù)字筆畫5和筆畫6，最終第2×s+3行，是全部數(shù)字筆畫7。假如某個(gè)數(shù)字d沒有覆蓋某個(gè)筆畫m(m=1…7)，那么，輸出數(shù)字d筆畫m時(shí)候，就應(yīng)該都輸出空格；假如覆蓋了筆畫m，則輸出s個(gè)’-‘或s個(gè)’|’，這取決于筆畫m是橫還是豎。解題思緒模擬與高精度計(jì)算第17頁由上思緒，處理這道題目標(biāo)關(guān)鍵，就在于怎樣統(tǒng)計(jì)每個(gè)數(shù)字都覆蓋了哪些筆畫。實(shí)際上，假如我們統(tǒng)計(jì)是每個(gè)筆畫都被哪些數(shù)字覆蓋，則程序?qū)崿F(xiàn)起來更為輕易。一個(gè)筆畫被哪些數(shù)字所覆蓋，能夠用一個(gè)數(shù)組來統(tǒng)計(jì)，比如統(tǒng)計(jì)筆畫1覆蓋情況數(shù)組以下：charn1[11]={"--------"};其中，n1[i](i=0……9)代表筆畫1是否被數(shù)字i覆蓋。假如是，則n1[i]為'-'，假如否，則n1[i]為空格。上面數(shù)組值表達(dá)了筆畫1被數(shù)字0,2,3,5,6,7,8,9覆蓋。對(duì)于豎向筆畫2，由字符'|'組成，則統(tǒng)計(jì)其覆蓋情況數(shù)組以下：charn2[11]={"||||||"};該數(shù)組值表達(dá)了筆畫2被數(shù)字0,4,5,6,8,9覆蓋。解題思緒模擬與高精度計(jì)算第18頁4、參考程序#include<stdio.h>#include<string.h>charn1[11]={"--------"};//筆畫1被數(shù)字0,2,3,5,6,7,8,9覆蓋charn2[11]={"||||||"};//筆畫2被數(shù)字0,4,5,6,8,9覆蓋charn3[11]={"||||||||"};//筆畫3被數(shù)字0,1,2,3,4,7,8,9覆蓋charn4[11]={"-------"};//筆畫4被數(shù)字2,3,4,5,6,8,9覆蓋charn5[11]={"||||"};//筆畫5被數(shù)字0,2,6,8覆蓋charn6[11]={"|||||||||"};//筆畫6被數(shù)字0,1,3,4,5,6,7,8,9覆蓋charn7[11]={"-------"};//筆畫7被數(shù)字0,2,3,5,6,8,9覆蓋intmain(void){ints;charszNumber[20];intnDigit,nLength,i,j,k;模擬與高精度計(jì)算第19頁

while(1){scanf("%d%s",&s,szNumber);if(s==0)break;nLength=strlen(szNumber);

for(i=0;i<nLength;i++){//輸出全部數(shù)字筆畫1nDigit=szNumber[i]-'0';printf("");for(j=0;j<s;j++)//一個(gè)筆畫由s個(gè)字符組成

printf("%c",n1[nDigit]);printf("");//兩個(gè)空格

}printf("\n");4、參考程序模擬與高精度計(jì)算第20頁

for(i=0;i<s;i++){//輸出全部數(shù)字筆畫2和筆畫3for(j=0;j<nLength;j++){nDigit=szNumber[j]-'0';printf("%c",n2[nDigit]);for(k=0;k<s;k++)printf("");//筆畫2和筆畫3之間空格

printf("%c",n3[nDigit]);//有一個(gè)空格

}printf("\n");}for(i=0;i<nLength;i++){//輸出全部數(shù)字筆畫4printf("");nDigit=szNumber[i]-'0';for(j=0;j<s;j++)printf("%c",n4[nDigit]);printf("");//兩個(gè)空格

}

printf("\n");4、參考程序模擬與高精度計(jì)算第21頁4、參考程序for(i=0;i<s;i++){//輸出全部數(shù)字筆畫5和筆畫6for(j=0;j<nLength;j++){nDigit=szNumber[j]-'0';printf("%c",n5[nDigit]);for(k=0;k<s;k++)printf("");//筆畫5和筆畫6之間空格printf("%c",n6[nDigit]);//有一個(gè)空格}printf("\n");}for(i=0;i<nLength;i++){//輸出全部數(shù)字筆畫7printf("");nDigit=szNumber[i]-'0';for(j=0;j<s;j++)printf("%c",n7[nDigit]);printf("");//兩個(gè)空格}printf("\n");printf("\n");}return0;}模擬與高精度計(jì)算第22頁5、實(shí)現(xiàn)技巧一個(gè)筆畫被哪些數(shù)字所覆蓋，最直接想法是用整型數(shù)組來統(tǒng)計(jì)，比如：intn1[10]={1,0,1,1,0,1,1,1,1,1};表示筆畫1被覆蓋情況?？墒桥c其在數(shù)字i筆畫1所處位置進(jìn)行輸出時(shí)候，依據(jù)n1[i]值決定輸出空格還是'-'’，還不如直接用下面char類型數(shù)組來表示覆蓋情況：charn1[11]={"--------"};這么，在數(shù)字i筆畫1所處位置進(jìn)行輸出時(shí)候，只要輸出s個(gè)n1[i]就行了。這是一個(gè)很好思緒，它提醒我們，以后在編程時(shí)設(shè)置一些標(biāo)志時(shí)候，要考慮一下是否能夠直接用更有意義東西將0，1這么標(biāo)志代替。模擬與高精度計(jì)算第23頁模擬類作業(yè)題CDOJ：1040猴子選大王、1078約瑟夫斯問題、1073UESTC冠軍杯模擬與高精度計(jì)算第24頁什么是高精度計(jì)算？C/C++中int類型能表示范圍是-231--231–1。unsigned類型能表示范圍是0--232–1，即0--4294967295。所以，int和unsigned類型變量，都不能保留超出10位整數(shù)。(另外，longlong類型也不能保留超出20位整數(shù)，因?yàn)?64=18,446,744,073,709,551,616)

有時(shí)需要參加運(yùn)算數(shù)值，可能會(huì)遠(yuǎn)遠(yuǎn)不止10、20位，比如，可能需要保留小數(shù)點(diǎn)后面100位（比如求π值），那么，即便使用能表示很大數(shù)值范圍double變量，不過因?yàn)閐ouble變量只有64位，所以還是不可能到達(dá)準(zhǔn)確到小數(shù)點(diǎn)后面100位這么精度。longlong變量精度也不足以表示一個(gè)100位整數(shù)。普通我們稱這種基本數(shù)據(jù)類型無法表示整數(shù)為大整數(shù)。怎樣表示和存放大整數(shù)呢？基本思想就是：用數(shù)組存放和表示大整數(shù)。一個(gè)數(shù)組元素，存放大整數(shù)中一位。那么，怎樣處理類似大整數(shù)這么高精度計(jì)算問題呢？模擬與高精度計(jì)算第25頁高精度數(shù)實(shí)際上就是一個(gè)整型數(shù)組，依據(jù)題目中用數(shù)據(jù)位數(shù)設(shè)定數(shù)組大小。為了方便通常將高精度數(shù)創(chuàng)建為一個(gè)新類型，如：inta[250];a[0]將存放高精度數(shù)位數(shù)，而從a[1]到a[a[0]]分別從低位到高位存放高精度數(shù)每一位數(shù)（這么每當(dāng)一位超出9時(shí)，會(huì)向前一進(jìn)位高精度數(shù)，為十進(jìn)制高精度數(shù)）。未使用部分均為0。比如將123456789012存入a中為數(shù)組下標(biāo)012345678910111213…存放數(shù)據(jù)1221098765432100模擬與高精度計(jì)算第26頁當(dāng)a[i]上數(shù)據(jù)大于等于10時(shí)候，就要向高位進(jìn)位了。因?yàn)樵摂?shù)組中下標(biāo)越大，位數(shù)越高，故對(duì)a[i]位進(jìn)行進(jìn)位操作為：a[i+1]=a[i]/10;a[i]%=10;假如a[a[0]]位也大于等于10，在進(jìn)位同時(shí)就要考慮a[0]值改變了。處理方式是先預(yù)計(jì)a[0]能改變最大值，再依次減小，直到抵達(dá)準(zhǔn)確位數(shù)。l=a[0]+MAX;while(a[l]==0&&l>1)l--;a[0]=l;模擬與高精度計(jì)算第27頁當(dāng)a[i]上數(shù)據(jù)小于0時(shí)候，就要由高位退位了。因?yàn)樵摂?shù)組中下標(biāo)越大，位數(shù)越高，故當(dāng)a[i]位小于0時(shí)，a[i+1]位退位操作（以十進(jìn)制為例）為：a[i+1]--;a[i]+=10;假如a[a[0]]位等于0，在退位同時(shí)就要考慮a[0]值改變了。此時(shí)要減小a[0]，直到抵達(dá)準(zhǔn)確位數(shù)。while(a[a[0]]==0&&a[0]>1)a[0]--;模擬與高精度計(jì)算第28頁高精度數(shù)加整型數(shù)算法：將整型加到a[1]后，再不停進(jìn)位，直到a[i]小于10為止。不過假如a[1]+x就已經(jīng)溢出整型范圍話，就需要a[1]+x%10，a[2]+x/10后再進(jìn)位。memcpy(tmp,a,sizeof(tmp));//復(fù)制a到tmp中intl=1;tmp[1]+=x;while(tmp[l]>9){tmp[l+1]+=tmp[l]/10;tmp[l]%=10;l++;//inc(i)}if(l>tmp[0])tmp[0]=l;memcpy(b,tmp,sizeof(b));模擬與高精度計(jì)算第29頁高精度數(shù)減整型數(shù)，若高精度數(shù)小于整型，把高精度轉(zhuǎn)化為整型直接減。這只討論高精度數(shù)大于整型。將高精度數(shù)對(duì)應(yīng)位同x對(duì)應(yīng)位相減，再進(jìn)行退位。memcpy(tmp,a,sizeof(tmp));intl=1;while(x){tmp[l]-=x%10,x/=10,l++;}for(inti=1;i<=tmp[0];i++)if(tmp[i]<0){tmp[i]+=10;tmp[i+1]--;}while(tmp[0]==0&&tmp[0]>1)tmp[0]--;memcpy(b,tmp,sizeof(b));模擬與高精度計(jì)算第30頁斐波那契數(shù)列準(zhǔn)確計(jì)算問題描述：試準(zhǔn)確求出斐波那契數(shù)列第n項(xiàng)。斐波那契數(shù)列定義：給出n<=61時(shí)數(shù)，以下：1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、17711、28657、46368、75025、121393、196418、317811、514229、832040、1346269、2178309、3524578、5702887、9227465、14930352、24157817、39088169、63245986、102334155、165580141、267914296、433494437、701408733、1134903170、1836311903、2971215073、4807526976、7778742049、12586269025、20365011074、32951280099、53316291173、86267571272、139583862445、225851433717、365435296162、591286729879、956722026041、1548008755920、2504730781961、4052739537881模擬與高精度計(jì)算第31頁斐波那契數(shù)列準(zhǔn)確計(jì)算來看一個(gè)加法過程：1548008755920+25047307819614052739537881為了作多位準(zhǔn)確計(jì)算，設(shè)置a、b、c三個(gè)數(shù)組。a[0]、b[0]存相鄰兩項(xiàng)個(gè)位數(shù)字，a[1]、b[1]存放兩項(xiàng)十位數(shù)字，其余類推。1、算法分析模擬與高精度計(jì)算第32頁斐波那契數(shù)列準(zhǔn)確計(jì)算同一位求和:c[i]=a[i]+b[i]+h，其中h為前一位相加進(jìn)位數(shù)。這里得到數(shù)c[i]可能超出一位，求出其進(jìn)位數(shù)h=c[i]/l0作為下一位相加進(jìn)位數(shù)，并讓c[i]=c[i]%10。從i=0至m求和全部完成后，即得到一個(gè)新項(xiàng)，把b數(shù)組賦給a數(shù)組，c數(shù)組賦給b數(shù)組，為繼續(xù)求下一項(xiàng)作準(zhǔn)備。當(dāng)己求出第n項(xiàng)，去掉c數(shù)組高位0后從高位至低位依次打印各位即為求得數(shù)列第n項(xiàng)。模擬與高精度計(jì)算第33頁高精度數(shù)加高精度數(shù)對(duì)應(yīng)位相加，最終統(tǒng)一進(jìn)位memset(tmp,0,sizeof(tmp));intl=max(a[0],b[0]);for(inti=1;i<=l;i++)tmp[i]=a[i]+b[i];l++;for(inti=1;i<=l;i++)if(tmp[i]>9){tmp[i+1]++;tmp[i]-=10;}while(tmp[l]==0&&l>1)l--;tmp[0]=l;memcpy(c,tmp,sizeof(c));模擬與高精度計(jì)算第34頁斐波那契數(shù)列準(zhǔn)確計(jì)算#include<stdio.h>#include<string.h>#defineN1000inta[N],b[N],c[N];intmain(void){inth,i,j,n,k;while(scanf("%d",&n)==1){memset(a,0,sizeof(a));memset(b,0,sizeof(a));memset(c,0,sizeof(a));a[0]=b[0]=1;//賦初值k=1;//開始時(shí)是1位數(shù)，用作循環(huán)上界for(i=2;i<=n;i++)//一個(gè)一個(gè)運(yùn)算{h=0;//開始時(shí)進(jìn)位數(shù)為0for(j=0;j<k;j++){c[j]=a[j]+b[j]+h;h=c[j]/10;c[j]%=10;}模擬與高精度計(jì)算第35頁斐波那契數(shù)列準(zhǔn)確計(jì)算if(h>0)//最終一次單獨(dú)處理{c[j]=h;k++;//位數(shù)增加}for(j=0;j<k;j++)//交換，為下一次計(jì)算作準(zhǔn)備{a[j]=b[j];b[j]=c[j];}}for(j=k-1;j>=0;j--)//輸出printf("%d",b[j]);printf("\n");}return0;}模擬與高精度計(jì)算第36頁大整數(shù)乘法

/ShowProblem.aspx?ProblemID=1092Description任給兩個(gè)長度不超出100位大整數(shù)，求兩個(gè)數(shù)相乘準(zhǔn)確結(jié)果。Input本題有多組輸入數(shù)據(jù)。第一行是輸入數(shù)據(jù)組數(shù)T，每組數(shù)據(jù)有兩行，分別是兩個(gè)非負(fù)大整數(shù)，當(dāng)數(shù)不為0時(shí)，不會(huì)出現(xiàn)首位為0情形。1<=T<=20。Output對(duì)應(yīng)每組數(shù)據(jù)，應(yīng)輸出一行，表示兩數(shù)相乘結(jié)果，不能有多出前導(dǎo)0。最終一組數(shù)據(jù)輸出后應(yīng)有一個(gè)空行。

模擬與高精度計(jì)算第37頁SampleInput1

12345678900

98765432100SampleOutput1219326311126352690000

模擬與高精度計(jì)算第38頁高精度數(shù)普通采取字符串方式，也能夠采取字符方式（以回車符作為結(jié)束標(biāo)志）。下面為字符串式讀入（十進(jìn)制）：

strings;intl;memset(a,0,sizeof(a));gets(s);l=strlen(s);for(i=l;i>=1;i--)//把數(shù)字倒過來，使得高位在下標(biāo)在位置a[i]=s[l-i]-'0';模擬與高精度計(jì)算第39頁

在程序中，為了更加好保留大整數(shù)，用了一個(gè)結(jié)構(gòu)體：

typedefstruct{intnumber[LEN];intlen;}digit;

用結(jié)構(gòu)體a,b表示兩個(gè)乘數(shù)，用c表示積。計(jì)算過程基本上和小學(xué)生列豎式做乘法相同。為編程方便，個(gè)數(shù)存放在數(shù)組最低位，而不是下標(biāo)高位置。在程序中，能夠不急于處理進(jìn)位，而將進(jìn)位問題留待最終統(tǒng)一處理。現(xiàn)以835×49為例來說明程序計(jì)算過程。解題思緒模擬與高精度計(jì)算第40頁先算835×9。5×9得到45個(gè)1，3×9得到27個(gè)10，8×9得到72個(gè)100。因?yàn)椴患庇谔幚磉M(jìn)位，所以835×9算完后，結(jié)果以下：接下來算4×5。此處4×5結(jié)果代表20個(gè)10，所以要c[1]+=20，變?yōu)椋涸傧聛硭?×3。此處4×3結(jié)果代表12個(gè)100，所以要c[2]+=12，變?yōu)椋耗M與高精度計(jì)算第41頁最終算4×8。此處4×8結(jié)果代表32個(gè)1000，所以要c[3]+=32，變?yōu)椋撼朔ㄟ^程完成。接下來從c[0]開始向高位逐位處理進(jìn)位問題。c[0]留下5，把4加到c[1]上，c[1]變?yōu)?1后，應(yīng)留下1，把5加到c[2]上……最終使得c里每個(gè)元素都是1位數(shù)，結(jié)果就算出來了：規(guī)律：一個(gè)數(shù)第i位和另一個(gè)數(shù)第j位相乘所得數(shù)，一定是要累加到結(jié)果第i+j位上。這里i,j都是從右往左，從0開始數(shù)。模擬與高精度計(jì)算第42頁4、參考程序#include<stdio.h>#include<string.h>#defineLEN210typedefstruct//統(tǒng)計(jì)數(shù)長度，降低循環(huán){intnumber[LEN];intlen;}digit;voidmultiply(digit*a,digit*b,digit*c);intmain(void){chars[LEN];inti,k,n,T;digita,b,c;scanf("%d",&T);//讀入數(shù)據(jù)個(gè)數(shù)getchar();//吸收回車符for(n=0;n<T;n++){gets(s);a.len=strlen(s);for(i=0;i<a.len;i++)//把數(shù)字倒過來，使得高位在下標(biāo)在位置a.number[i]=s[a.len-i-1]-'0';模擬與高精度計(jì)算第43頁4、參考程序gets(s);b.len=strlen(s);for(i=0;i<b.len;i++)//把數(shù)字倒過來，使得高位在下標(biāo)在位置b.number[i]=s[b.len-i-1]-'0';multiply(&a,&b,&c);for(i=c.len-1;i>=0;i--)printf("%d",c.number[i]);printf("\n");}return0;}//a,b是乘數(shù)，c是積voidmultiply(digit*a,digit*b,digit*c){inti,j,t;if((a->len==1&&a->number[0]==0)||(b->len==1&&b->number[0]==0))//其中一個(gè)數(shù)為0{c->len=1;c->number[0]=0;return;}模擬與高精度計(jì)算第44頁4、參考程序c->len=a->len+b->len;//先乘，后進(jìn)位memset(c->number,0,c->len*sizeof(int));//清零for(i=0;i<b->len;i++)//逐位作乘法{for(j=0;j<a->len;j++)c->number[i+j]+=a->number[j]*b->number[i];}for(i=0;i<c->len-1;i++)//統(tǒng)一進(jìn)位{if(c->number[i]>=10){c->number[i+1]+=c->number[i]/10;c->number[i]%=10;}}//積最大長度為兩數(shù)長度之和，最小為之和減1if(c->number[i]==0)c->len--;}模擬與高精度計(jì)算第45頁大整數(shù)除法

1、鏈接地址

/problem?id=27372、問題描述求兩個(gè)大正整數(shù)相除商輸入數(shù)據(jù)第1行是測(cè)試數(shù)據(jù)組數(shù)n，每組測(cè)試數(shù)據(jù)占2行，第1行是被除數(shù)，第2行是除數(shù)。每組測(cè)試數(shù)據(jù)之間有一個(gè)空行，每行數(shù)據(jù)不超出100個(gè)字符

輸出要求n行，每組測(cè)試數(shù)據(jù)有一行輸出是對(duì)應(yīng)整數(shù)商模擬與高精度計(jì)算第46頁輸入樣例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451輸出樣例010000000000000000000000000000005409656775097850895687056798068970934546546575676768678435435345模擬與高精度計(jì)算第47頁基本思想是重復(fù)做減法，看看從被除數(shù)里最多能減去多少個(gè)除數(shù)，商就是多少。一個(gè)一個(gè)減顯然太慢，怎樣減得更加快一些呢？以7546除以23為例來看一下：開始商為0。先減去23100倍，就是2300，發(fā)覺夠減3次，余下646。于是商值就增加300。然后用646減去230，發(fā)覺夠減2次，余下186，于是商值增加20。最終用186減去23，夠減8次，所以最終商就是328。所以本題關(guān)鍵是要寫一個(gè)大整數(shù)減法函數(shù)，然后重復(fù)調(diào)用該函數(shù)進(jìn)行減法操作。計(jì)算除數(shù)10倍、100倍時(shí)候，不用做乘法，直接在除數(shù)后面補(bǔ)0即可。3、解題思緒模擬與高精度計(jì)算第48頁4、參考程序#include<stdio.h>#include<string.h>#defineMAX_LEN200charszLine1[MAX_LEN+10];charszLine2[MAX_LEN+10];intan1[MAX_LEN+10];//被除數(shù),an1[0]對(duì)應(yīng)于個(gè)位intan2[MAX_LEN+10];//除數(shù),an2[0]對(duì)應(yīng)于個(gè)位intaResult[MAX_LEN+10];//存放商，aResult[0]對(duì)應(yīng)于個(gè)位//長度為nLen1大整數(shù)p1減去長度為nLen2大整數(shù)p2//結(jié)果放在p1里，返回值代表結(jié)果長度//如不夠減返回-1，恰好減完返回0intSubstract(int*p1,int*p2,intnLen1,intnLen2){inti;if(nLen1<nLen2)return-1;模擬與高精度計(jì)算第49頁4、參考程序//下面判斷p1是否比p2大，假如不是，返回-1if(nLen1==nLen2){for(i=nLen1-1;i>=0;i--){if(p1[i]>p2[i])break;//p1>p2elseif(p1[i]<p2[i])return-1;//p1<p2}}for(i=0;i<nLen1;i++){//要求調(diào)用本函數(shù)確保當(dāng)i>=nLen2時(shí)，p2[i]＝0p1[i]-=p2[i];if(p1[i]<0){p1[i]+=10;p1[i+1]--;}}for(i=nLen1-1;i>=0;i--)if(p1[i])//找到最高位第一個(gè)不為0returni+1;return0;//全部為0，說明二者相等}模擬與高精度計(jì)算第50頁4、參考程序intmain(){intt,n;scanf("%d",&n);for(t=0;t<n;t++){scanf("%s",szLine1);scanf("%s",szLine2);inti,j;intnLen1=strlen(szLine1);memset(an1,0,sizeof(an1));memset(an2,0,sizeof(an2));memset(aResult,0,sizeof(aResult));for(j=0,i=nLen1-1;i>=0;i--)an1[j++]=szLine1[i]-'0';intnLen2=strlen(szLine2);for(j=0,i=nLen2-1;i>=0;i--)an2[j++]=szLine2[i]-'0';if(nLen1<nLen2){printf("0\n");continue;}模擬與高精度計(jì)算第51頁intnTimes=nLen1-nLen2;if(nTimes>0){for(i=nLen1-1;i>=nTimes;i--)an2[i]=an2[i-nTimes];//朝高位移動(dòng)for(;i>=0;i--)//低位補(bǔ)0an2[i]=0;nLen2=nLen1;}for(j=0;j<=nTimes;j++){intnTmp;//一直減到不夠減為止//先減去若干個(gè)an2×(10nTimes次方)，//不夠減了，再減去若干個(gè)an2×(10nTimes-1次方)，......while((nTmp=Substract(an1,an2+j,nLen1,nLen2-j))>=0){nLen1=nTmp;aResult[nTimes-j]++;//每成功減一次，則將商對(duì)應(yīng)位加1}}模擬與高精度計(jì)算第52頁參考程序//下面輸出結(jié)果，先跳過高位0for(i=MAX_LEN;(i>=0)&&(aResult[i]==0);i--);if(i>=0)for(;i>=0;i--)printf("%d",aResult[i]);elseprintf("0");printf("\n");}return0;}模擬與高精度計(jì)算第53頁麥森數(shù)1、鏈接地址

/problem?id=27062、問題描述

形如2^P-1素?cái)?shù)稱為麥森數(shù)，這時(shí)P一定也是個(gè)素?cái)?shù)。但反過來不一定，即假如P是個(gè)素?cái)?shù)。2^P-1不一定也是素?cái)?shù)。到1998年底，人們已找到了37個(gè)麥森數(shù)。最大一個(gè)是P=3021377，它有909526位。麥森數(shù)有許多主要應(yīng)用，它與完全數(shù)親密相關(guān)。你任務(wù)：輸入P(1000<P<3100000),計(jì)算2p-1位數(shù)和最終500位數(shù)字（用十進(jìn)制高精度數(shù)表示）模擬與高精度計(jì)算第54頁輸入數(shù)據(jù)只包含一個(gè)整數(shù)P(1000<P<3100000)輸出要求第1行：十進(jìn)制高精度數(shù)2^p-1位數(shù)。第2-11行：十進(jìn)制高精度數(shù)2^p-1最終500位數(shù)字。（每行輸出50位，共輸出10行，不足500位時(shí)高位補(bǔ)0）無須驗(yàn)證2^p-1與P是否為素?cái)?shù)。輸入樣例1279模擬與高精度計(jì)算第55頁輸出樣例38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087模擬與高精度計(jì)算第56頁第一個(gè)問題，輸出2^p-1有多少位。因?yàn)?^p個(gè)位數(shù)只可能是2,4,6,8所以2^p-1和2^p位數(shù)相同。使用C/C++標(biāo)準(zhǔn)庫中在math.h里申明，求以10為底對(duì)數(shù)函數(shù)doublelog10(doublex)函數(shù)，就能輕松求得2^p-1位數(shù)。2p值需要用一個(gè)高效率方法來算。顯然，對(duì)于任何p>0，考慮p二進(jìn)制形式，則不難得到：這里，ai要么是1，要么是0。3、解題思緒模擬與高精度計(jì)算第57頁因而：計(jì)算2p方法就是：先將結(jié)果值設(shè)為1，計(jì)算21。假如a0值為1，則結(jié)果乘以21；計(jì)算22，假如a1為1，則結(jié)果乘以22；計(jì)算24，假如a2為1，則結(jié)果乘以24；……總之，第i步(i從0到n，an是1)就計(jì)算22^i，假如ai為1，則結(jié)果就乘以22^i。每次由22^i×22^i就能算出22^(i+1)。因?yàn)閜可能很大，所以上面乘法都應(yīng)該使用高精度計(jì)算。因?yàn)轭}目只要求輸出500位，所以這些乘法都是只須算出末尾500即可。解題思緒模擬與高精度計(jì)算第58頁在前面高精度計(jì)算中，我們用數(shù)組來存放大整數(shù)，數(shù)組一個(gè)元素對(duì)應(yīng)于十進(jìn)制大整數(shù)一位。本題假如也這么做，就會(huì)超時(shí)。為了加緊計(jì)算速度，能夠用一個(gè)數(shù)組元素對(duì)應(yīng)于大整數(shù)4位，即將大整數(shù)表示為10000進(jìn)制，而數(shù)組中每一個(gè)元素就存放10000進(jìn)制數(shù)1位。比如，用int型數(shù)組a來存放整數(shù)6373384，那么只需兩個(gè)數(shù)組元素就能夠了，a[0]=3384,a[1]=637。因?yàn)橹灰蠼Y(jié)果最終500位數(shù)字，所以我們不需要計(jì)算完整結(jié)果，只需算出最終500位即可。因?yàn)橛妹總€(gè)數(shù)組元素存放十進(jìn)制大整數(shù)4位，所以本題中數(shù)組最多只需要125個(gè)元素。解題思緒模擬與高精度計(jì)算第59頁4、參考程序#include<stdio.h>#include<memory.h>#defineLEN125//每數(shù)組元素存放4位，數(shù)組最多需要125個(gè)元素#include<math.h>//計(jì)算高精度乘法a*b,結(jié)果末500位放在a中voidMultiply(int*a,int*b){inti,j;intnCarry;//存放進(jìn)位intnTmp;intc[LEN];//存放結(jié)果末500位memset(c,0,sizeof(int)*LEN);for(i=0;i<LEN;i++){nCarry=0;for(j=0;j<LEN-i;j++){nTmp=c[i+j]+a[j]*b[i]+nCarry;c[i+j]=nTmp%10000;nCarry=