信息學(xué)競(jìng)賽習(xí)題解答5模擬

1、算法與程序?qū)嵺`習(xí) 題 解 答5模擬現(xiàn)實(shí)中的有些問(wèn)題，難以找到公式或規(guī)律來(lái)解決，只能按照一定步驟，不停地做下去，最后才能得到答案。這樣的問(wèn)題，用計(jì)算機(jī)來(lái)解決十分合適，只要能讓計(jì)算機(jī)模擬人在解決此問(wèn)題的行為即可。這一類(lèi)的問(wèn)題可以稱(chēng)之為“模擬題”。比如下面經(jīng)典的約瑟夫問(wèn)題：CS51：約瑟夫問(wèn)題（來(lái)源： 2746，程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐（李文新）例6.1 P141）問(wèn)題描述：約瑟夫問(wèn)題：有只猴子，按順時(shí)針?lè)较驀梢蝗x大王（編號(hào)從到），從第號(hào)開(kāi)始報(bào)數(shù)，一直數(shù)到，數(shù)到的猴子退出圈外，剩下的猴子再接著從1 開(kāi)始報(bào)數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時(shí)，這個(gè)猴子就是猴王，編程求輸入，后，輸出最后猴王的編號(hào)。輸

2、入：每行是用空格分開(kāi)的兩個(gè)整數(shù)，第一個(gè)是 n，第二個(gè)是m ( 0 m, n 300) 。最后一行是：0 0輸出：對(duì)于每行輸入數(shù)據(jù)（最后一行除外)，輸出數(shù)據(jù)也是一行，即最后猴王的編號(hào)。樣例輸入：6 212 48 30 0樣例輸出：517解題思路：初一看，很可能想把這道題目當(dāng)作數(shù)學(xué)題來(lái)做，即認(rèn)為結(jié)果也許會(huì)是以n和m為自變量的某個(gè)函數(shù)f(n,m)，只要發(fā)現(xiàn)這個(gè)函數(shù)，問(wèn)題就迎刃而解。實(shí)際上，這樣的函數(shù)很難找，甚至也許根本就不存在。用人工解決的辦法就是將n個(gè)數(shù)寫(xiě)在紙上排成一圈，然后從1開(kāi)始數(shù)，每數(shù)到第m個(gè)就劃掉一個(gè)數(shù)，一遍遍做下去，直到剩下最后一個(gè)。有了計(jì)算機(jī)，這項(xiàng)工作做起來(lái)就會(huì)快多了，我們只要編寫(xiě)一個(gè)

3、程序，模擬人工操作的過(guò)程就可以了。用數(shù)組anLoop來(lái)存放n個(gè)數(shù)，相當(dāng)于n個(gè)數(shù)排成的圈；用整型變量 nPtr指向當(dāng)前數(shù)到的數(shù)組元素，相當(dāng)于人的手指；劃掉一個(gè)數(shù)的操作，就用將一個(gè)數(shù)組元素置0的方法來(lái)實(shí)現(xiàn)。人工數(shù)的時(shí)候，要跳過(guò)已經(jīng)被劃掉的數(shù)，那么程序執(zhí)行的時(shí)候，就要跳過(guò)為0的數(shù)組元素。需要注意的是，當(dāng)nPtr指向anLoop中最后一個(gè)元素（下標(biāo)n-1）時(shí)，再數(shù)下一個(gè)，則nPtr要指回到數(shù)組的頭一個(gè)元素（下標(biāo)0），這樣anLoop才象一個(gè)圈。參考程序：#include #include #define MAX_NUM 300int aLoopMAX_NUM+1;int main()int n,m,i

4、;while(1)scanf(%d%d,&n,&m);if(n=0) break;for(i=0;in;i+)aLoopi=i+1;int nPtr=0; /存儲(chǔ)位置信息for(i=0;in;i+) /每次循環(huán)將1只猴子趕出圈子int nCount=0; /記錄本輪數(shù)到的猴子數(shù)目while(nCountm) /一直要數(shù)出m個(gè)猴子while(aLoopnPtr=0) /跳過(guò)已經(jīng)出圈的猴子nPtr=(nPtr+1)%n; /到下一個(gè)位置，如果到最后就跳到第1個(gè)nCount+;nPtr=(nPtr+1)%n;nPtr-; /找到要出圈的猴子，位置要回退一個(gè)if(nPtr0)nPtr=n-1;if(i

5、=n-1) /最后一個(gè)出圈的猴子printf(%dn,aLoopnPtr);aLoopnPtr=0;return 0;注意事項(xiàng)：上面的程序完全模擬了人工操作的過(guò)程，但因?yàn)橐磸?fù)跳過(guò)為0 的數(shù)組元素，因此算法的效率不是很高。后文的“鏈表”一章，采用單鏈表進(jìn)行模擬來(lái)解決本題，就能省去跳過(guò)已出圈的猴子這個(gè)操作，大大提高了效率。n 個(gè)元素的數(shù)組，從下標(biāo)0 的元素開(kāi)始存放猴子編號(hào)，則循環(huán)報(bào)數(shù)的時(shí)候，下一個(gè)猴子的下標(biāo)就是“(當(dāng)前猴子下標(biāo)+ 1 )% n”。這種寫(xiě)法比用分支語(yǔ)句來(lái)決定下個(gè)猴子的下標(biāo)是多少，更快捷而且寫(xiě)起來(lái)更方便。對(duì)于本題，雖然很難直接找出結(jié)果函數(shù) f(n, m)，但是如果仔細(xì)研究，找出局部的

6、一些規(guī)律，比如，每次找下一個(gè)要出圈的猴子時(shí)，直接根據(jù)本次的起點(diǎn)位置就用公式算出下一個(gè)要出圈的猴子的位置，那么寫(xiě)出的程序就可以省去數(shù)m只猴子這個(gè)操作，大大提高效率，甚至不需要用數(shù)組來(lái)存放 n 個(gè)數(shù)。請(qǐng)寫(xiě)出這個(gè)高效而節(jié)省空間的程序。問(wèn)題一：在數(shù)組里循環(huán)計(jì)數(shù)的時(shí)候，一定要小心計(jì)算其開(kāi)始的下標(biāo)和終止的下標(biāo)。比如，語(yǔ)句15，循環(huán)是從0到n-1，而不是從0 到n。問(wèn)題二：nPtr-到nPtr=n-1回退一個(gè)位置，易被忽略或?qū)戝e(cuò)。比如只寫(xiě)了語(yǔ)句nPtr-，忘了處理nPtr變成小于0的情況。CS52：醉酒的獄卒（The Drunk Jailer）（來(lái)源：POJ 1218 ZOJ 1350，程序設(shè)計(jì)方法及在線實(shí)

7、踐指導(dǎo)（王衍等） P169）問(wèn)題描述：某個(gè)監(jiān)獄有一排、共n間牢房，一間挨一間。每間牢房關(guān)著一名囚犯，每間牢房的門(mén)剛開(kāi)始時(shí)都是關(guān)著的。有一天晚上，獄卒厭煩了看守工作，決定玩一個(gè)游戲。游戲的第1輪，他喝了一杯酒，然后沿著監(jiān)獄，把所有的牢房的門(mén)挨個(gè)挨個(gè)打開(kāi)；第2輪，他又喝了一杯酒，然后沿著監(jiān)獄，把編號(hào)為偶數(shù)的牢房的門(mén)關(guān)上；第3輪，他又喝了一杯酒，然后沿著監(jiān)獄，對(duì)編號(hào)為3的倍數(shù)的牢房，如果牢房的門(mén)開(kāi)著，則關(guān)上，否則打開(kāi)；，獄卒重復(fù)游戲n輪。游戲結(jié)束后，他喝下最后一杯酒，醉倒了。這時(shí)，囚犯才意識(shí)到他們牢房的門(mén)可能是開(kāi)著的，而且獄卒醉倒了，所以他們?cè)姜z了。給定牢房的數(shù)目，求越獄囚犯的人數(shù)。輸入：輸入文件的

8、第1行為一個(gè)正整數(shù)，表示測(cè)試數(shù)據(jù)的個(gè)數(shù)。每個(gè)測(cè)試數(shù)據(jù)占一行，為一個(gè)整數(shù)n，5=n=100，表示牢房的數(shù)目。輸出：對(duì)每個(gè)測(cè)試數(shù)據(jù)所表示的牢房數(shù)目n，輸出越獄的囚犯人數(shù)。樣例輸入：25100樣例輸出：210解題分析：n輪游戲后，哪些牢房的門(mén)是開(kāi)著的，并無(wú)規(guī)律可循。但這個(gè)游戲的規(guī)則和過(guò)程很簡(jiǎn)單：游戲有n輪，第j輪游戲是將編號(hào)為j的倍數(shù)的牢房狀態(tài)變反，原來(lái)是開(kāi)著的，則關(guān)上，原來(lái)是關(guān)著的，則打開(kāi)，j=1,2,3,n。這些規(guī)則和過(guò)程用程序能較容易地實(shí)行，所以適合采用“模擬”的思路來(lái)求解。具體實(shí)現(xiàn)時(shí)可定義一個(gè)一維數(shù)組，每個(gè)元素表示對(duì)應(yīng)牢房的狀態(tài)，初始為1，表示牢房門(mén)是關(guān)著的，然后模擬游戲的每一輪：第j輪時(shí)，

9、改變牢房編號(hào)為j的倍數(shù)的牢房狀態(tài)，為0則改為1，為1則改為0。n輪游戲后，統(tǒng)計(jì)狀態(tài)為0的牢房數(shù)即可。參考程序：#include #include int main()int nCases,n;int prision101; /n個(gè)牢房，n最多100個(gè),1表示鎖著，0表示開(kāi)著int i,j;scanf(%d,&nCases);for(i=0;inCases;i+)scanf(%d,&n);for(j=1;j=n;j+)prisionj=1;for(j=1;j=n;j+)int tmp=j;while(tmp=n)prisiontmp=(prisiontmp=1)?0:1;tmp+=j;int n

10、um=0;for(j=1;j=n;j+)if(!prisionj) num+;printf(%dn,num);return 0;CS53：花生問(wèn)題（同CS93）（來(lái)源： 2950，程序設(shè)計(jì)導(dǎo)引及在線實(shí)踐（李文新）例4.3 P107）問(wèn)題描述：魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費(fèi)品嘗我種的花生！熊字”。魯賓遜先生和多多都很開(kāi)心，因?yàn)榛ㄉ撬麄兊淖類(lèi)?ài)。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖5-1）。有經(jīng)驗(yàn)的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生

11、說(shuō)：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類(lèi)推，不過(guò)你一定要在我限定的時(shí)間內(nèi)回到路邊?！蔽覀兗俣ǘ喽嘣诿總€(gè)單位時(shí)間內(nèi)，可以做下列四件事情中的一件：1) 從路邊跳到最靠近路邊（即第一行）的某棵花生植株；2) 從一棵植株跳到前后左右與之相鄰的另一棵植株；3) 采摘一棵植株下的花生；4) 從最靠近路邊（即第一行）的某棵花生植株跳回路邊。圖 5-1 花生地圖 5-2 摘花生過(guò)程現(xiàn)在給定一塊花生田的大小和花生的分布，請(qǐng)問(wèn)在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有部分植株下面長(zhǎng)有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。例如在圖5-2所示

12、的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4) 的植株下長(zhǎng)有花生，個(gè)數(shù)分別為13、7、15、9。沿著圖示的路線，多多在21個(gè)單位時(shí)間內(nèi)，最多可以采到37個(gè)花生。輸入：輸入的第一行包括三個(gè)整數(shù)，M, N 和K，用空格隔開(kāi)；表示花生田的大小為M *N（1 = M, N = 20），多多采花生的限定時(shí)間為K（0 = K = 1000 ）個(gè)單位時(shí)間。接下來(lái)的M 行，每行包括N 個(gè)非負(fù)整數(shù)，也用空格隔開(kāi)；第i + 1 行的第j 個(gè)整數(shù)Pij（0 = Pij = 500） 表示花生田里植株(i, j)下花生的數(shù)目，0 表示該植株下沒(méi)有花生。輸出：輸出包括一行，這一行只包含

13、一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多可以采到花生的個(gè)數(shù)。樣例輸入：6 7 210 0 0 0 0 0 00 0 0 0 13 0 00 0 0 0 0 0 70 15 0 0 0 0 00 0 0 9 0 0 00 0 0 0 0 0 0樣例輸出：37解題思路：試圖找規(guī)律，得到一個(gè)以花生矩陣作為自變量的公式來(lái)解決這個(gè)問(wèn)題，是不現(xiàn)實(shí)的。結(jié)果只能是做了才知道。即走進(jìn)花生地，每次要采下一株花生之前，先計(jì)算一下，剩下的時(shí)間，夠不夠走到那株花生，采摘，并從那株花生走回到路上。如果時(shí)間夠，則走過(guò)去采摘；如果時(shí)間不夠，則采摘活動(dòng)到此結(jié)束。參考程序：#include #include #include #inc

14、lude int T,M,N,K;#define MAX_NUM 55int aFieldMAX_NUMMAX_NUM;int main()int i,j,t,m,n;scanf(%d,&T);for(t=0;tT;t+)scanf(%d%d%d,&M,&N,&K);for(m=1;m=M;m+)for(n=1;n=N;n+)scanf(%d,&aFieldmn);int nTotalPeanuts=0; /摘得的花生總數(shù)int nTotalTime=0; /已經(jīng)花去的總時(shí)間int nCuri=0,nCurj; /當(dāng)前位置坐標(biāo)while(nTotalTimeK)int nMax=0,nMaxi

15、,nMaxj; /最大的花生數(shù)目，及其所處的位置/尋找下一個(gè)最大花生數(shù)目及其位置for(i=1;i=M;i+)for(j=1;j=N;j+)if(nMaxaFieldij)nMax=aFieldij;nMaxi=i;nMaxj=j;if(nMax=0) /地里沒(méi)有花生了break;if(nCuri=0)nCurj=nMaxj; /如果當(dāng)前位置在路上，那么應(yīng)走到橫坐標(biāo)nMaxj處，再進(jìn)入花生地/下面檢查剩余的時(shí)間夠不夠走到nMaxi,nMaxj處，摘取花生，并回到路上if(nTotalTime+nMaxi+1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj)=K)nTotalT

16、ime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj);nCuri=nMaxi;nCurj=nMaxj;nTotalPeanuts+=aFieldnMaxinMaxj;aFieldnMaxinMaxj=0; /摘走花生賦值為0elsebreak;printf(%dn,nTotalPeanuts);return 0;實(shí)現(xiàn)技巧：用二維數(shù)組存放花生地的信息是很自然的想法。然而，用aField00還是aField11 對(duì)應(yīng)花生地的左上角，是值得思考一下的。因?yàn)閺牡乩锏铰飞线€需要1 個(gè)單位時(shí)間，題目中的坐標(biāo)又都是從1 開(kāi)始，所以若aField11 對(duì)應(yīng)花生地的左上角，則從aFi

17、eldij 點(diǎn)，回到路上所需時(shí)間就是i，這樣更為方便和自然，不易出錯(cuò)。并不是C/C+ 的數(shù)組下標(biāo)從0 開(kāi)始，我們使用數(shù)組的時(shí)候，就要從下標(biāo)為0 的元素開(kāi)始用。常見(jiàn)問(wèn)題：?jiǎn)栴}一：讀題時(shí)應(yīng)該仔細(xì)讀。有的同學(xué)沒(méi)有看到每次只能拿剩下花生株中最大的，而是希望找到一種在規(guī)定時(shí)間內(nèi)能夠拿最多花生的組合，把題目變成了另外一道題。問(wèn)題二：有的同學(xué)沒(méi)有讀到“沒(méi)有兩株花生株的花生數(shù)目相同”的條件，因此把題目復(fù)雜化了。問(wèn)題三：這個(gè)題目是假設(shè)猴子在取花生的過(guò)程中不會(huì)回到大路上的，有些同學(xué)在思考是否可能在中間回到大路上，因?yàn)轭}目沒(méi)說(shuō)在大路上移動(dòng)要花時(shí)間，所以有可能中途出來(lái)再進(jìn)去摘的花生更多。CS54：分糖果的游戲（Can

18、dy Sharing Game）（來(lái)源：POJ 1666 ZOJ 1814，程序設(shè)計(jì)方法及在線實(shí)踐指導(dǎo)（王衍等） P186）問(wèn)題描述：N個(gè)學(xué)生圍成一圈坐著，面向老師（老師位于中心）。每個(gè)學(xué)生手頭上剛開(kāi)始都有偶數(shù)塊糖果。每輪游戲：老師一吹哨子，每個(gè)學(xué)生將他的糖果的一半分給他右邊相鄰的學(xué)生；N個(gè)學(xué)生分糖果完畢后，如果某個(gè)學(xué)生手頭上的糖果數(shù)為奇數(shù)，則由老師再給一塊糖果湊成偶數(shù)塊。當(dāng)所有學(xué)生的糖果數(shù)一樣時(shí)，則游戲結(jié)束。要求編寫(xiě)程序，輸出游戲進(jìn)行的輪數(shù)，以及最終每個(gè)學(xué)生手頭糖果的塊數(shù)。輸入：輸入文件描述了多次游戲（即輸入文件中包含多個(gè)測(cè)試數(shù)據(jù)）。每次游戲的數(shù)據(jù)第一行是一個(gè)整數(shù)N，表示學(xué)生的人數(shù)，接下來(lái)是

19、N個(gè)偶數(shù)，代表初始時(shí)N個(gè)學(xué)生手上的糖果數(shù)目（逆時(shí)針排列）。輸入文件最后一行為0，表示輸入結(jié)束。輸出：對(duì)每次游戲，輸出游戲進(jìn)行的輪數(shù)，以及游戲結(jié)束后每個(gè)學(xué)生手上的糖果數(shù)。樣例輸入：6362222211222018161412108642424680樣例輸出：15 1417 224 8注意：游戲會(huì)在有限次內(nèi)結(jié)束，因?yàn)椋ㄔO(shè)每輪游戲過(guò)后N個(gè)學(xué)生擁有糖果的最大數(shù)目為max，最小數(shù)目為min）：（1）max不會(huì)增加；（2）min不會(huì)減少；（3）且任何一個(gè)糖果數(shù)多于min的學(xué)生，他的糖果數(shù)不會(huì)減少到min；（4）如果max和min不等，則至少有一個(gè)學(xué)生，他的糖果數(shù)會(huì)增加，這個(gè)學(xué)生就是糖果數(shù)最少的學(xué)生。解題分

20、析：對(duì)于給定的學(xué)生人數(shù)N，以及初始時(shí)N個(gè)學(xué)生的糖果數(shù)，最終需要進(jìn)行游戲的輪數(shù)以及最終每個(gè)學(xué)生的糖果數(shù)是沒(méi)有規(guī)律可循的，只能進(jìn)行模擬。模擬游戲的每一輪，直到N個(gè)學(xué)生的糖果數(shù)一樣為止。以樣例輸入中的第1個(gè)測(cè)試數(shù)據(jù)為例解釋游戲的過(guò)程，如圖5.9所示，圖（a）中圓圈里的數(shù)字表示初始時(shí)6個(gè)學(xué)生的糖果數(shù)，旁邊的數(shù)字表示學(xué)生的序號(hào)（從0開(kāi)始，按逆時(shí)針順序排列）。圖（b）表示第1輪游戲，每個(gè)人將手上糖果數(shù)的一半分給右邊的學(xué)生（虛線箭頭所示）；如果某個(gè)學(xué)生手頭上的糖果數(shù)位奇數(shù)，則由老師再給一塊糖果湊成偶數(shù)塊，如圖（c）所示；第1輪游戲過(guò)后，每人手上的糖果數(shù)如圖（d）所示。具體實(shí)現(xiàn)時(shí)，可以用一整型數(shù)組candys存儲(chǔ)N個(gè)學(xué)生（序號(hào)為0N-1，如圖5.9（a）所示）的糖果數(shù)。在模擬每一輪游戲時(shí)，要先用臨時(shí)變量（設(shè)為half0）保存第N-1個(gè)學(xué)生糖果數(shù)的一半，然后將第i個(gè)學(xué)生的糖果數(shù)candysi更新為：candysi/2+candysi-1/2；最后一個(gè)學(xué)生，即第0個(gè)學(xué)生的糖果數(shù)更新為：candys0/2+half0。在判斷N個(gè)學(xué)生的糖果數(shù)是否一致時(shí)，注意只要有前后兩個(gè)學(xué)生的糖果數(shù)不一致的情況，就可以判斷這N個(gè)學(xué)生的糖果數(shù)不一致；另外第N-1個(gè)學(xué)生右邊相鄰的學(xué)生是第0個(gè)學(xué)生，所以要取模，即要判斷candysi與candys(i+1)%N是否相等。