ACM暑期培訓(xùn)(共29張)

1、高精度運(yùn)算理學(xué)院計(jì)算機(jī)系理學(xué)院計(jì)算機(jī)系 姚娟姚娟計(jì)算機(jī)能做的和不能做的 計(jì)算機(jī)的限制：精度、范圍計(jì)算機(jī)的限制：精度、范圍(int： -231 231-1, 即即 -2 147 483 648 2 147 483 647) 計(jì)算機(jī)：突破了人的運(yùn)算速度極限計(jì)算機(jī)：突破了人的運(yùn)算速度極限 對(duì)運(yùn)算的數(shù)據(jù)進(jìn)行了對(duì)運(yùn)算的數(shù)據(jù)進(jìn)行了“合理”的假設(shè)的假設(shè) 要解決假設(shè)之外的事情，它們的數(shù)量不多、但常要解決假設(shè)之外的事情，它們的數(shù)量不多、但常常極其重大。比如中國(guó)的糧食安全問(wèn)題：常極其重大。比如中國(guó)的糧食安全問(wèn)題： 13億人口、人均需要多少億人口、人均需要多少 多少耕地、畝產(chǎn)多少、上年余積多少多少耕地、畝產(chǎn)多少、上

2、年余積多少 大整數(shù)加法1、鏈接地址 /problem?id=15032、問(wèn)題描述 求不多于100個(gè)不超過(guò)100 位的非負(fù)整數(shù)的之和。輸入數(shù)據(jù) 有n行（nlen2?len1:len2;for(i=len1;ilen+1;i+) an1i=0;/缺位前導(dǎo)補(bǔ)缺位前導(dǎo)補(bǔ)0for(i=len2;ilen+1;i+) an2i=0;for(i=0;i1) /去掉前導(dǎo)數(shù)字去掉前導(dǎo)數(shù)字0，確定數(shù)組當(dāng)前長(zhǎng)度，確定數(shù)組當(dāng)前長(zhǎng)度len-;for(k=0;k=10)ak+1=ak+1+ak/10;/對(duì)數(shù)值超過(guò)對(duì)數(shù)值超過(guò)9的位進(jìn)行歸整處理的位進(jìn)行歸整處理ak=ak%10;if(ak!=0) l

3、en=k+1;/確定數(shù)組的最終長(zhǎng)度確定數(shù)組的最終長(zhǎng)度return len;POJ1503 參考程序int main()char szLineMAXLEN+10;int an1MAXLEN+10,an2MAXLEN+10;int k=0,i,j=0;int len1,len2;an10=0;len1=1;while(1)cinszLine;if(szLine0=0) break;len2=strlen(szLine);for(i=len2-1,j=0;i=0; i-)an2j+ = szLinei - 0;addition(an1,an2,len1,len2);for(i=len1-1;i=0;

4、i-)coutan1i;return 0;大整數(shù)乘法1、鏈接地址 /problem?id=23892、問(wèn)題描述 求兩個(gè)不超過(guò)200 位的非負(fù)整數(shù)的積。輸入數(shù)據(jù)有兩行，每行是一個(gè)不超過(guò)200 位的非負(fù)整數(shù)，沒(méi)有多余的前導(dǎo)0。輸出要求一行，即相乘后的結(jié)果。結(jié)果里不能有多余的前導(dǎo)0，即如果結(jié)果是342，那么就不能輸出為0342。輸入樣例1234567890098765432100輸出樣例1219326311126352690000 大整數(shù)乘法(POJ2389) 解題思路 在程序中，用在程序中，用unsigned an1200和和unsigned an2200分別存放兩個(gè)乘數(shù)

5、，用分別存放兩個(gè)乘數(shù)，用aResult400來(lái)來(lái)存放積。計(jì)算的中間結(jié)果也都存在存放積。計(jì)算的中間結(jié)果也都存在aResult中。中。aResult長(zhǎng)度取長(zhǎng)度取400是因?yàn)閮蓚€(gè)是因?yàn)閮蓚€(gè)200 位的數(shù)相乘，位的數(shù)相乘，積最多會(huì)有積最多會(huì)有400 位。位。an10, an20, aResult0都表示個(gè)位。都表示個(gè)位。 計(jì)算的過(guò)程基本上和小學(xué)生列豎式做乘法相同。計(jì)算的過(guò)程基本上和小學(xué)生列豎式做乘法相同。為編程方便，并不急于處理進(jìn)位，而將進(jìn)位問(wèn)題為編程方便，并不急于處理進(jìn)位，而將進(jìn)位問(wèn)題留待最后統(tǒng)一處理。留待最后統(tǒng)一處理。 現(xiàn)以現(xiàn)以 83549 為例來(lái)說(shuō)明程序的計(jì)算過(guò)程。為例來(lái)說(shuō)明程序的計(jì)算過(guò)程。先算

6、先算8359。59 得到得到45 個(gè)個(gè)1，39 得到得到27 個(gè)個(gè)10，89 得得到到72 個(gè)個(gè)100。由于不急于處理進(jìn)位，所以。由于不急于處理進(jìn)位，所以8359 算完后，結(jié)算完后，結(jié)果如下：果如下：大整數(shù)乘法(POJ2389) 解題思路接下來(lái)算接下來(lái)算45。此處。此處45 的結(jié)果代表的結(jié)果代表20 個(gè)個(gè)10，因此要，因此要 c1+=20，變?yōu)椋?，變?yōu)椋涸傧聛?lái)算再下來(lái)算43。此處。此處43 的結(jié)果代表的結(jié)果代表12 個(gè)個(gè)100，因此要，因此要 c2+= 12，變?yōu)椋?，變?yōu)椋捍笳麛?shù)乘法(POJ2389) 解題思路最后算最后算 48。此處。此處48 的結(jié)果代表的結(jié)果代表 32 個(gè)個(gè)1000，因此要

7、，因此要 c3+= 32，變?yōu)椋?，變?yōu)椋撼朔ㄟ^(guò)程完畢。接下來(lái)從乘法過(guò)程完畢。接下來(lái)從 c0開(kāi)始向高位逐位處理進(jìn)位問(wèn)題。開(kāi)始向高位逐位處理進(jìn)位問(wèn)題。c0留下留下5，把，把4 加到加到c1上，上，c1變?yōu)樽優(yōu)?1 后，應(yīng)留下后，應(yīng)留下1，把，把5 加到加到c2上上最終使得最終使得c 里的每個(gè)元素都是里的每個(gè)元素都是1 位數(shù)，結(jié)果就位數(shù)，結(jié)果就算出來(lái)了：算出來(lái)了：規(guī)律：一個(gè)數(shù)的第規(guī)律：一個(gè)數(shù)的第i 位和另一個(gè)數(shù)的第位和另一個(gè)數(shù)的第j 位相乘所得的數(shù)，一位相乘所得的數(shù)，一定是要累加到結(jié)果的第定是要累加到結(jié)果的第i+j 位上。這里位上。這里i, j 都是從右往左，從都是從右往左，從0 開(kāi)始數(shù)。開(kāi)始數(shù)。P

8、OJ2389 參考程序#include#includeusing namespace std;const int MAXLEN=200+10;int aMAXLEN,bMAXLEN;int c2*MAXLEN;string st1,st2;int i,j,k;/字符串字符串s轉(zhuǎn)換為整型數(shù)組轉(zhuǎn)換為整型數(shù)組tvoid tran(string s,int *t)int m,l;l=s.length();for(m=0;ml;m+)tm=sl-1-m-0;POJ2389 參考程序/乘法：輸入用字符串表示的長(zhǎng)整數(shù)乘法：輸入用字符串表示的長(zhǎng)整數(shù)m1、m2/返回一個(gè)表示兩個(gè)數(shù)乘積長(zhǎng)度的指針，及表示乘積的一個(gè)

9、整型數(shù)組返回一個(gè)表示兩個(gè)數(shù)乘積長(zhǎng)度的指針，及表示乘積的一個(gè)整型數(shù)組cvoid mul(int *m1,int *m2,int *len)int i,j;for(i=0;iMAXLEN;i+)/用第二個(gè)數(shù)乘以第一個(gè)數(shù)用第二個(gè)數(shù)乘以第一個(gè)數(shù),每次一位每次一位 for(j=0;jMAXLEN;j+)ci+j=ci+j+ai*bj;/先乘起來(lái)先乘起來(lái),后面統(tǒng)一進(jìn)位后面統(tǒng)一進(jìn)位for(i=0;i=10)ci+1=ci+1+ci/10;ci=ci%10;i=2*MAXLEN-1;while(ci=0 & i0) i=i-1;/跳過(guò)高位的跳過(guò)高位的0*len=i;POJ2389 參考程序int main()

10、int len;while(cinst1st2)for(i=0;iMAXLEN;i+)ai=0; bi=0;tran(st1,a);tran(st2,b);for(i=0;i=0;j-)coutcj;coutendl;return 0;大整數(shù)除法1、鏈接地址 http:/ 2、問(wèn)題描述 求兩個(gè)大的正整數(shù)相除的商輸入數(shù)據(jù) 第1 行是測(cè)試數(shù)據(jù)的組數(shù)n，每組測(cè)試數(shù)據(jù)占2 行，第1 行是被除數(shù)，第2 行是除數(shù)。每組測(cè)試數(shù)據(jù)之間有一個(gè)空行，每行數(shù)據(jù)不超過(guò)100 個(gè)字符輸出要求 n 行，每組測(cè)試數(shù)據(jù)有一行輸出是相應(yīng)的整數(shù)商問(wèn)題描述問(wèn)題描述輸入樣例324053373129633733590092604577

11、420574392304964939303555957976607910827396462987192585318701752584429931160870372907079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451輸出樣例01000000000000000000000000000000540965677509785089568705679

12、8068970934546546575676768678435435345 基本的思想是反復(fù)做減法，看看從被除數(shù)里最多能減去多少個(gè)除數(shù)，商就是多少。一個(gè)一個(gè)減顯然太慢，如何減得更快一些呢？以7546 除以23 為例來(lái)看一下：開(kāi)始商為0。先減去23 的100 倍，就是2300，發(fā)現(xiàn)夠減3 次，余下646。于是商的值就增加300。然后用646 減去230，發(fā)現(xiàn)夠減2 次，余下186，于是商的值增加20。最后用186 減去23，夠減8 次，因此最終商就是328。 所以本題的核心是要寫一個(gè)大整數(shù)的減法函數(shù)，然后反復(fù)調(diào)用該函數(shù)進(jìn)行減法操作。 計(jì)算除數(shù)的10 倍、100 倍的時(shí)候，不用做乘法，直接在除數(shù)后

13、面補(bǔ)0 即可。解題思路解題思路參考程序參考程序n#include n#include n#define MAX_LEN 200nchar szLine1MAX_LEN + 10;nchar szLine2MAX_LEN + 10;nint an1MAX_LEN + 10; /被除數(shù)被除數(shù), an10對(duì)應(yīng)于個(gè)位對(duì)應(yīng)于個(gè)位nint an2MAX_LEN + 10; /除數(shù)除數(shù), an20對(duì)應(yīng)于個(gè)位對(duì)應(yīng)于個(gè)位nint aResultMAX_LEN + 10; /存放商，存放商，aResult0對(duì)應(yīng)于個(gè)位對(duì)應(yīng)于個(gè)位n/長(zhǎng)度為長(zhǎng)度為 nLen1 的大整數(shù)的大整數(shù)p1 減去長(zhǎng)度為減去長(zhǎng)度為nLen2 的大

14、整數(shù)的大整數(shù)p2n/結(jié)果放在結(jié)果放在p1 里，返回值代表結(jié)果的長(zhǎng)度里，返回值代表結(jié)果的長(zhǎng)度n/如不夠減返回如不夠減返回-1，正好減完返回，正好減完返回 0nint Substract( int * p1, int * p2, int nLen1, int nLen2)nn int i;n if( nLen1 = 0; i - ) n n if( p1i p2i ) break; /p1p2n else if( p1i p2i ) return -1; /p1p2n n n for( i = 0; i =nLen2 時(shí)，時(shí)，p2i 0n p1i -= p2i; n if( p1i = 0 ; i

15、- )n if( p1i )/找到最高位第一個(gè)不為找到最高位第一個(gè)不為0n return i + 1;n return 0;/全部為全部為0，說(shuō)明兩者相等，說(shuō)明兩者相等n參考程序參考程序nint main()nn int t, n;n cinn;n for( t = 0; t szLine1;n cin szLine2;n int i, j;n int nLen1 = strlen( szLine1);n memset( an1, 0, sizeof(an1);n memset( an2, 0, sizeof(an2);n memset( aResult, 0, sizeof(aResult)

16、;n for( j = 0, i = nLen1 - 1;i = 0 ; i -)n an1j+ = szLine1i - 0;n int nLen2 = strlen(szLine2);n for( j = 0, i = nLen2 - 1;i = 0 ; i -)n an2j+ = szLine2i - 0;n if( nLen1 nLen2 ) n n cout 0)n n for( i = nLen1 -1; i = nTimes; i - ) n an2i = an2i-nTimes;/朝高位移動(dòng)朝高位移動(dòng)n for( ; i = 0; i-)/低位補(bǔ)低位補(bǔ)0n an2i = 0;n

17、 nLen2 = nLen1;n n for( j = 0 ; j = 0) n n nLen1 = nTmp;n aResultnTimes-j+; /每成功減一次，則將商的相應(yīng)位加每成功減一次，則將商的相應(yīng)位加1n n 參考程序參考程序n /下面輸出結(jié)果，先跳過(guò)高位下面輸出結(jié)果，先跳過(guò)高位0n for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - );n if( i = 0)n for( ; i=0; i-)n cout aResulti;n elsen cout0;n coutendl;n n return 0;n課堂練習(xí)-八進(jìn)制小數(shù) 鏈接：鏈

18、接：/problem?id=1131描述描述 八進(jìn)制小數(shù)可以用十進(jìn)制小數(shù)精確的表示。比如，八進(jìn)制里面的八進(jìn)制小數(shù)可以用十進(jìn)制小數(shù)精確的表示。比如，八進(jìn)制里面的0.75等等于十進(jìn)制里面的于十進(jìn)制里面的0.963125 (7/8 + 5/64)。所有小數(shù)點(diǎn)后位數(shù)為。所有小數(shù)點(diǎn)后位數(shù)為n的八進(jìn)制的八進(jìn)制小數(shù)都可以表示成小數(shù)點(diǎn)后位數(shù)不多于小數(shù)都可以表示成小數(shù)點(diǎn)后位數(shù)不多于3n的十進(jìn)制小數(shù)。的十進(jìn)制小數(shù)。你的任務(wù)是寫一個(gè)程序，把你的任務(wù)是寫一個(gè)程序，把(0, 1)中的八進(jìn)制小數(shù)轉(zhuǎn)化成十進(jìn)制小數(shù)。中的八進(jìn)制小數(shù)轉(zhuǎn)化成十進(jìn)制小數(shù)。 輸入輸入 輸入包括若干八進(jìn)制小數(shù)，每個(gè)小數(shù)占用一行。每個(gè)小數(shù)的形式是輸入包括若干八進(jìn)制小數(shù)，每個(gè)小數(shù)占用一行。每個(gè)小數(shù)的形式是0.d1d2d3 . dk，這里，這里di是八進(jìn)制數(shù)是八進(jìn)制數(shù)0.7，而且已知，而且已知0 k octal) . 暑期練習(xí)暑期練習(xí) POJ 1001 難度一般難度一般 英文鏈接英文鏈接 中文鏈接中文鏈接 POJ 2413 英文鏈接英文鏈接題意是給出兩個(gè)長(zhǎng)整數(shù)