ACM程序設(shè)計(jì)競(jìng)賽例題1

1、ACM程序設(shè)計(jì)競(jìng)賽例題1ACM程序設(shè)計(jì)競(jìng)賽例題1ACM程序設(shè)計(jì)競(jìng)賽例題1ACM程序設(shè)計(jì)競(jìng)賽例題1編制僅供參考審核批準(zhǔn)生效日期地址： 電話：傳真: 郵編:備戰(zhàn)ACM資料習(xí)題10-1背包問題在0 / 1背包問題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高。 程序如下：#include void readdata();void search(int);void checkmax();void printresult();int c=35, n=1

2、0; );printf(n);printf(n);6素?cái)?shù)環(huán)問題把從1到20這20個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)。分析：用回溯算法，考察所有可能的排列。程序如下：#include #include void search(int);void init(); 表示空格；X表示墻。程序如下：#include #include void search(int,int);int canplace(int,int);void readdata(); Floodfill給一個(gè)2020的迷宮和一個(gè)起點(diǎn)坐標(biāo)，用廣度優(yōu)先搜索填充所有的可到達(dá)的格子。提示：參考第2題。2.電子老鼠闖迷宮如下圖1212

3、方格圖，找出一條自入口（2，9）到出口（11，8）的最短路本題給出完整的程序和一組測(cè)試數(shù)據(jù)。狀態(tài)：老鼠所在的行、列。程序如下：#includevoid readdata(); aij=0; .注：測(cè)試數(shù)據(jù)可在運(yùn)行時(shí)粘貼上去（點(diǎn)擊窗口最左上角按鈕，在菜單中選則“編輯”/“粘貼”即可）。想一想：此程序都存在哪些問題，如果openlen太小程序會(huì)不會(huì)出錯(cuò)，加入代碼使程序能自動(dòng)報(bào)出此類錯(cuò)誤。3.跳馬給一個(gè)200200的棋盤，問國(guó)際象棋的馬從給定的起點(diǎn)到給定的終點(diǎn)最少需要幾步。Sample Input 0 0 1 1 Sample output 4狀態(tài)：馬所在的行、列。程序如下：#includevoid

4、 readdata(); 獨(dú)輪車獨(dú)輪車的輪子上有5種顏色，每走一格顏色變化一次，獨(dú)輪車只能往前推，也可以在原地旋轉(zhuǎn)，每走一格，需要一個(gè)單位的時(shí)間，每轉(zhuǎn)90度需要一個(gè)單位的時(shí)間，轉(zhuǎn)180度需要兩個(gè)單位的時(shí)間。現(xiàn)給定一個(gè)2020的迷宮、一個(gè)起點(diǎn)、一個(gè)終點(diǎn)和到達(dá)終點(diǎn)的顏色，問獨(dú)輪車最少需要多少時(shí)間到達(dá)。狀態(tài)：獨(dú)輪車所在的行、列、當(dāng)前顏色、方向。另外為了方便在結(jié)點(diǎn)中加上到達(dá)該點(diǎn)的最小步數(shù)。程序如下：#includestruct colornodeint row; 表示空格aij=0; .XXXX.X.X 1 1 1 4 8 11最長(zhǎng)公共子序列一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確

5、切地說，若給定序列X=，則另一序列Z=是X的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列 ，使得對(duì)于所有j=1,2,k有答如下：a) 最長(zhǎng)公共子序列的結(jié)構(gòu)若用窮舉搜索法，耗時(shí)太長(zhǎng)，算法需要指數(shù)時(shí)間。易證最長(zhǎng)公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和Y=的一個(gè)最長(zhǎng)公共子序列Z=，則：i.若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長(zhǎng)公共子序列； ii.若xmyn且zkxm ，則Z是Xm-1和Y的最長(zhǎng)公共子序列； iii.若xmyn且zkyn ，則Z是X和Yn-1的最長(zhǎng)公共子序列。 其中Xm-1=，Yn-1=，Zk-1=。最長(zhǎng)公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。b) 子問題的遞歸結(jié)構(gòu)

6、由最長(zhǎng)公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=和Y=的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時(shí)，找出Xm-1和Yn-1的最長(zhǎng)公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個(gè)最長(zhǎng)公共子序列。當(dāng)xmyn時(shí)，必須解兩個(gè)子問題，即找出Xm-1和Y的一個(gè)最長(zhǎng)公共子序列及X和Yn-1的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X和Y的一個(gè)最長(zhǎng)公共子序列。由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問題具有子問題重疊性質(zhì)。例如，在計(jì)算X和Y的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出X和Yn-1及Xm-1和Y的最長(zhǎng)公共子序列。而這兩個(gè)子問題都包含一個(gè)公共子問題，即計(jì)算Xm-1和Yn-1的最長(zhǎng)

7、公共子序列。我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用ci,j記錄序列Xi和Yj的最長(zhǎng)公共子序列的長(zhǎng)度。其中Xi=，Yj=。當(dāng)i=0或j=0時(shí)，空序列是Xi和Yj的最長(zhǎng)公共子序列，故ci,j=0。建立遞歸關(guān)系如下：c) 計(jì)算最優(yōu)值由于在所考慮的子問題空間中，總共只有(m*n)個(gè)不同的子問題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。計(jì)算最長(zhǎng)公共子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=和Y=作為輸入。輸出兩個(gè)數(shù)組c0.m ,0.n和b1.m ,1.n。其中ci,j存儲(chǔ)Xi與Yj的最長(zhǎng)公共子序列的長(zhǎng)度，bi,j記錄指示ci,j的值是由哪一個(gè)子問題的解達(dá)到的，這在

8、構(gòu)造最長(zhǎng)公共子序列時(shí)要用到。最后，X和Y的最長(zhǎng)公共子序列的長(zhǎng)度記錄于cm,n中。程序如下：#include#includeint lcs_length(char x, char y);int main()char x100,y100;int len;while(1)scanf(%s%s,x,y);if(x0=0) 搬桌子問題某教學(xué)大樓一層有n個(gè)教室，從左到右依次編號(hào)為1、2、n?，F(xiàn)在要把一些課桌從某些教室搬到另外一些教室，每張桌子都是從編號(hào)較小的教室搬到編號(hào)較大的教室，每一趟，都是從左到右走，搬完一張課桌后，可以繼續(xù)從當(dāng)前位置或往右走搬另一張桌子。輸入數(shù)據(jù)：先輸入n、m，然后緊接著m行輸入這m

9、張要搬課桌的起始教室和目標(biāo)教室。輸出數(shù)據(jù)：最少需要跑幾趟。Sample Input10 51 33 94 66 107 8Sample Output3分析：貪心算法，把課桌按起點(diǎn)從小到大排序，每次都是搬離當(dāng)前位置最近的課桌。程序如下：#includeint main()structint start;int end;a100;int i,j;int n,m,min,num,temp,used100=0;scanf(%d%d,&m,&n);for(i=0;i=temp)temp=ai.end;usedi=1;num+;min+;printf(%d,min);1、平面分割方法：設(shè)有n條封閉曲線畫在

10、平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，問這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。#include int f(int n) if(n=1) return 2;else return f(n-1)+2*(n-1);void main()int n;while(1)cinn;coutf(n)endl;2、LELE的RPG難題：有排成一行的個(gè)方格，用紅(Red)、粉(Pink)、綠(Green)三色涂每個(gè)格子，每格涂一色，要求任何相鄰的方格不能同色，且首尾兩格也不同色編程全部的滿足要求的涂法.#includeint f(int n)if(n=1) return 3;

11、else if(n=2) return 6;else return f(n-1)+f(n-2)*2;void main()int n;while(1)cinn;coutf(n)endl;最少錢幣數(shù)：【問題描述】這是一個(gè)古老而又經(jīng)典的問題。用給定的幾種錢幣湊成某個(gè)錢數(shù)，一般而言有多種方式。例如：給定了6種錢幣面值為2、5、10、20、50、100，用來湊 15元，可以用5個(gè)2元、1個(gè)5元，或者3個(gè)5元，或者1個(gè)5元、1個(gè)10元，等等。顯然，最少需要2個(gè)錢幣才能湊成15元。你的任務(wù)就是，給定若干個(gè)互不相同的錢幣面值，編程計(jì)算，最少需要多少個(gè)錢幣才能湊成某個(gè)給出的錢數(shù)。【要求】【數(shù)據(jù)輸入】輸入可以有

12、多個(gè)測(cè)試用例。每個(gè)測(cè)試用例的第一行是待湊的錢數(shù)值M（1 = M = 2000，整數(shù)），接著的一行中，第一個(gè)整數(shù)K（1 = K = 10）表示幣種個(gè)數(shù)，隨后是K個(gè)互不相同的錢幣面值Ki(1 = Ki = 1000)。輸入M=0時(shí)結(jié)束?！緮?shù)據(jù)輸出】每個(gè)測(cè)試用例輸出一行，即湊成錢數(shù)值M最少需要的錢幣個(gè)數(shù)。如果湊錢失敗，輸出“Impossible”。你可以假設(shè)，每種待湊錢幣的數(shù)量是無限多的?！緲永斎搿?56 2 5 10 20 50 10011 20【樣例輸出】2Impossible/* 2010年5月19日 */#include#includeusing namespace std;int m10

13、00;int M;int p;int check() .70，71，72，73.）【要求】【數(shù)據(jù)輸入】一個(gè)整數(shù)N。(N不大于30000)【數(shù)據(jù)輸出】從小到大排列的不大于N的與7有關(guān)的數(shù)字，每行一個(gè)?！緲永斎搿?0【樣例輸出】71417#includeusingnamespacestd;boolHasSeven(inti)intflag(0);while(i)if(i%10=7)flag+;i/=10;if(flag)return1;elsereturn0;intmain()intN;coutN;for(inti=1;i!=N;i+)if(i%7=0|HasSeven(i)coutiendl;

14、連續(xù)郵資問題【問題描述】G國(guó)發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對(duì)于給定的n和m的值，給出郵票面值的最佳設(shè)計(jì)，使得可在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。例如，當(dāng)n=5和m=4時(shí)，面值為(1,3,11,15,32)的5種郵票可以貼出郵資的最大連續(xù)郵資區(qū)間是1到70。編程任務(wù): 對(duì)于給定的正整數(shù)m和n，計(jì)算出郵票面值的最佳設(shè)計(jì)。 【要求】【數(shù)據(jù)輸入】輸入數(shù)據(jù)每一行給出2個(gè)正整數(shù)m和n的值（1=n，m=9），最后以0 0 表示文件結(jié)束。 【數(shù)據(jù)輸出】對(duì)于輸以假定(ai, aj) = 1.輸出包含一個(gè)正整數(shù)，即為Andy家至少養(yǎng)豬的數(shù)

15、目?！緲永斎搿?3 15 17 2【樣例輸出】16#includeusing namespace std; class Stampfriend int MaxStamp(int ,int ,int );private: int Bound(int i); void Backtrack(int i,int r); int n;第1行n,然后n行3個(gè)整數(shù)坐標(biāo)【數(shù)據(jù)輸出】每組一行,代表最小權(quán)和【樣例輸入】30 0 01 1 01 -1 0【樣例輸出】#include#include#include#include#defineMAX_POINT50/*n=50*/#defineSquare(x)(

16、x)*(x)#defineN_DIMENSION3/*定義維數(shù)*/typedefintCoordinateN_DIMENSION;/*定義坐標(biāo)*/CoordinatepointMAX_POINT;/*初始坐標(biāo)*/CoordinatepathMAX_POINT;/*坐標(biāo)路徑*/intflagMAX_POINT;/*路徑標(biāo)記*/intpointNum;/*坐標(biāo)點(diǎn)數(shù)*/doublesumDistance;/*路徑距離*/doubleminDistance=LONG_MAX;/*最小路徑*/voidReadSampleInput()FILE*fpSampleInput=NULL;inti,j;fpSa

17、mpleInput=fopen(,rb);if(NULL=fpSampleInput)printf(Error:Opensampleinputfilefailed!n);exit(-1);fscanf(fpSampleInput,%d,&pointNum);for(i=0;ipointNum;i+) for(j=0;jN_DIMENSION;j+)fscanf(fpSampleInput,%d,&pointij);fclose(fpSampleInput);voidCopyCoordinate(Coordinatea,Coordinateb)inti;for(i=0;iN_DIMENSION;

18、i+)ai=bi;doubleCalPointDistance(Coordinatea,Coordinateb)inti;intdistance=0;for(i=0;iN_DIMENSION;i+)distance+=Square(ai-bi);returnsqrt(distance);/*核心函數(shù)：使用回溯算法遍歷所有可能的路徑*/voidCalMinDistance(intpointCnt)inti=0;doubledistance=;if(pointCnt=pointNum)/*已經(jīng)訪問完每一點(diǎn)*/if(sumDistanceminDistance)minDistance=sumDist

19、ance;return;if(0=pointCnt)/*從第一點(diǎn)開始訪問*/CopyCoordinate(path0,point0);pointCnt+=1;for(i=1;iminDistance)flagi=0;sumDistance-=distance;return;CalMinDistance(pointCnt+1);/*繼續(xù)計(jì)算下一點(diǎn)*/flagi=0;/*回溯*/sumDistance-=distance;voidWriteSampleInput(doublenumber)FILE*fpSampleOutput=NULL;fpSampleOutput=fopen(,wb);if(N

20、ULL=fpSampleOutput)printf(Error:Opensampleoutputfilefailed!n);exit(-1);fprintf(fpSampleOutput,%.1lf,number);fclose(fpSampleOutput);intmain()ReadSampleInput();CalMinDistance(0);WriteSampleInput(minDistance);return0; 對(duì)于1背包問題，如果該題一般化，那就是沒有沒有那個(gè)大米袋數(shù)，每種為1袋，對(duì)于這個(gè)問題可以得到以下結(jié)論設(shè)numj為用 j元金額買下 前i種大米的最大質(zhì)量，則題目要就的就是nummn；下面分3種情況討論當(dāng) i，j，一個(gè)為0時(shí)，很明顯，num0 = 0, num0j = 0如果 j= p，這個(gè)時(shí)候，可以買 第i種大米，當(dāng)然買不買第i種大米還取決