第八周 模擬問題

1、第八講模擬問題ACM算法與程序設(shè)計(jì)現(xiàn)實(shí)中的有些問題難以找到公式或規(guī)律來解決。只能按照一定步驟不停地做下去，最后才能得到答案。這樣的問題，用計(jì)算機(jī)來解決十分合適，只要能讓計(jì)算機(jī)模擬人在解決問題時(shí)的行為即可。這一類的問題可以稱之為“模擬題”。2約瑟夫問題 問題描述約瑟夫問題：有只猴子，按順時(shí)針方向圍成一圈選大王（編號從到），從第號開始報(bào)數(shù)，一直數(shù)到，數(shù)到的猴子退出圈外，剩下的猴子再接著從1開始報(bào)數(shù)。就這樣，直到圈內(nèi)只剩下一只猴子時(shí)，這個(gè)猴子就是猴王，編程求輸入，后，輸出最后猴王的編號。 http:/problem?id=27463Input每行是用空格分開的兩個(gè)整數(shù)，第一個(gè)是 n, 第二個(gè)是 m

2、( 0 m,n =300)。最后一行是：0 0Output對于每行輸入數(shù)據(jù)（最后一行除外)，輸出數(shù)據(jù)也是一行，即最后猴王的編號 4Sample Input6 2 12 4 8 3 0 0 Sample Output5 1 7 5解題思路很可能想把這道題目當(dāng)作數(shù)學(xué)題來做，即認(rèn)為結(jié)果也許會(huì)是以一和m為自變量的某個(gè)函數(shù)f(n,m)，只要發(fā)現(xiàn)這個(gè)函數(shù)，問題就迎刃而解。用人工解決的辦法就是將一個(gè)數(shù)寫在紙上排成一圈，然后從1開始數(shù)。每數(shù)到第m個(gè)就劃掉一個(gè)數(shù)，一遍遍做下去，直到剩下最后一個(gè)。編寫一個(gè)程序模擬人工操作的過程。用數(shù)組aLoop來存放n個(gè)數(shù)，相當(dāng)于n個(gè)數(shù)排成的圈；用整型變量nPtr指向當(dāng)前數(shù)到的數(shù)

3、組元素，相當(dāng)于人的手指；劃掉一個(gè)數(shù)的操作，就用將一個(gè)數(shù)組元素置0的方法來實(shí)現(xiàn)。要跳過已經(jīng)被劃掉的數(shù)，那么就要跳過為0的數(shù)組元素。需要注意的是，當(dāng)nPtr指向aLoop中最后一個(gè)元素(下標(biāo)n-1)時(shí)，再數(shù)下一個(gè)，則nPtr要指回到數(shù)組的第一個(gè)元素(下標(biāo)0)，這樣aLoop才像一個(gè)圈。6實(shí)現(xiàn)技巧n個(gè)元素的數(shù)組，從下標(biāo)0的元素開始存放猴子編號，則循環(huán)報(bào)數(shù)的時(shí)候，下一個(gè)猴子的下標(biāo)就是“(當(dāng)前猴子下標(biāo)+1)n”。這種寫法比用分支語句來決定下個(gè)猴子的下標(biāo)是多少更快捷而且寫起來更方便。7參考程序一：#include#include#define MAX_NUN 300int aLoopMAX_NUM+10;

4、main() int n, m, I; while(1) scanf(“%d%d, &n,&m); if(n = 0) break; for(i=0; in; i+) aLoopi=i+1; int nPtr=0;8 for (i=0; in; i+) /每次循環(huán)將1只猴子趕出圈子，最后被 /趕出的就是猴王 int nCounted=0; /記錄本輪數(shù)到的猴子數(shù)目 whi1e(nCountedm) /一直要數(shù)出m個(gè)猴子 while(aLoopnPtr=0) /跳過已經(jīng)出圈的猴子 nPtr=(nPtr+1)%n;/到下一個(gè)位置 nCounted+; /數(shù)到一只猴子 nPtr=(nPtr+1)%n

5、; /指到下一個(gè)位置 nPtr-; /要回退一個(gè)位置 if (nPtr0) nPtr=n-1; if (i=n1) /最后一只出圈的猴子 printf(“%dn”, aLoopnPtr); aLoopnPtr = 0; /猴子出圈 9常見問題程序完全模擬了人工操作的過程，但因?yàn)橐磸?fù)跳過為0的數(shù)組元素，因此算法的效率不是很高。采用單鏈表進(jìn)行模擬來解決本題。就能省去跳過已出圈的猴子這個(gè)操作，大大提高了效率。在數(shù)組里循環(huán)計(jì)數(shù)的時(shí)候，一定要小心計(jì)算其開始的下標(biāo)和終止的下標(biāo)。比如循環(huán)是從0到n-1，而不是從0到n?；赝艘粋€(gè)位置，易被忽略或?qū)戝e(cuò)。比如只寫了語句nPtr-，忘了處理nPtr變成小于0的情況

6、。10摘花生問題描述魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個(gè)正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費(fèi)品嘗我種的花生！熊字”。 魯賓遜先生和多多都很開心，因?yàn)榛ㄉ撬麄兊淖類邸Ｔ诟媸九票澈?，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。http:/problem?id=295011有經(jīng)驗(yàn)的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時(shí)間內(nèi)回到路邊?！?我們假定多多在每個(gè)單位時(shí)間內(nèi)，

7、可以做下列四件事情中的一件： 1) 從路邊跳到最靠近路邊（即第一行）的某棵花生植株； 2) 從一棵植株跳到前后左右與之相鄰的另一棵植株； 3) 采摘一棵植株下的花生； 4) 從最靠近路邊（即第一行）的某棵花生植株跳回路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布，請問在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有部分植株下面長有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。 12例如在圖2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下長有花生，個(gè)數(shù)分別為13, 7, 15, 9。沿著圖示的路線，多多在21個(gè)單位時(shí)間內(nèi)，最多可以采到37個(gè)花生。 13

8、Input輸入的第一行包括一個(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表示該植株下沒有花生。 Output輸出包括T行，每一行只包含一個(gè)整數(shù)，即在限定時(shí)間內(nèi)，多多最多可以采到花生的個(gè)數(shù)。 14Sample Input6 7 21 0 0 0 0 0 0 0 0 0 0 0 13

9、0 0 0 0 0 0 0 0 7 0 15 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 Sample Output 37 15找規(guī)律得到一個(gè)以花生矩陣作為自變量的公式來解決這個(gè)問題，是不現(xiàn)實(shí)的。結(jié)果只能是做了才知道。即走進(jìn)花生地每次要采下一株花生之前，先計(jì)算一下剩下的時(shí)間夠不夠走到那株花生，采摘，并從那株花生走回到路上。如果時(shí)問夠則走過去采摘；如果時(shí)間不夠，則采摘活動(dòng)到此結(jié)束。設(shè)二維數(shù)組aField存放花生地的信息。然而，用aField00還是aField11對應(yīng)花生地的左上角是值得思考一下的。因?yàn)閺牡乩锏铰飞线€需要1個(gè)單位時(shí)間，題目中的坐標(biāo)又都是從1開始。所

10、以若aField11對應(yīng)花生地的左上角，則從aFieldij點(diǎn)回到路上所需時(shí)間就是i，這樣更為方便和自然，不易出錯(cuò)。并不是CC+的數(shù)組下標(biāo)從0開始使用數(shù)組的時(shí)候就要從下標(biāo)為0的元素開始用。3、解題思路16 總的思路是首先計(jì)算出給出的Haab 歷表示的日期是世界開始后的第幾天（假設(shè)是k），然后用k 除以260 得到Tzolkin 歷的年份，再用k 對260 取模得到m，用m 分別對13 和20取模得到d 和s，d 和Tzolkin 歷中第s 個(gè)字符串的組合就是要求的日期。 這里需要注意的是如果我們把世界的第1 天用0 表示，第260 天用259 表示，則正好用這個(gè)數(shù)字除以260得到Tzolkin

11、 歷的年份，m 對13 取模后得到0 到12 的值，這個(gè)值要加1 才能用于表示Tzolkin歷的日期，同時(shí)m 對20 取模后得到019 的數(shù)值，分別表示取20 個(gè)字符串中的一個(gè)。如果我們用字符串?dāng)?shù)組來存儲(chǔ)這20 個(gè)字符串，則019的取值正好對應(yīng)需要的字符串的數(shù)組下標(biāo)。3、解題思路174、參考程序#include #include#include#includeint T, M, N, K;#define MAX_NUM 55int aFieldMAX_NUM MAX_NUM;main() scanf(“%d, &T); for(int t=0; tT; t+) scanf(“%d%dd”, &

12、M, &N, &K); /花生地的左上角對應(yīng)的數(shù)組元素是aField11，路的縱坐標(biāo)是0 for(int m=1; m=M; m+) for(int n=1; n=N; n+) scanf(“d”，&afieldmn); int nTotalPeanuts=0; /摘到的花生總數(shù) int nTotalTime=O; /已經(jīng)花去的時(shí)問 int nCuri=0，nCurj; /當(dāng)前位置坐標(biāo)， /nCuri代表縱坐標(biāo)，開始是在路上，所以初值為018 while(nTotalTimeK) /如果還有時(shí)間 int nMax=0, nMaxi, nMaxj /最大的花生數(shù)目，及其所處的位置 for(int

13、 i=1; i=M; i+) /下面這個(gè)循環(huán)尋找下一個(gè)最大花生數(shù)目及其位置 for(int j=1; j=N; j+) if(nMaxaFieIdij) nMax=aFieIdij; nMaxi=i; nMaxj=j; if(nMax = = 0) /地里已經(jīng)沒有花生了 break; if(nCuri = = 0) nCurj=nMaxj; /如果當(dāng)前位置是在路上，那么 /應(yīng)走到橫坐標(biāo)nMaxj處，再進(jìn)人花生地19/ 下一行看剩余時(shí)間是否足夠走到(nMaxi，nMaxj)處，摘取花/生，并回到路上 if(nTotaITime+nMaxi+1+abs(nMaxi-nCuri)+ abs(nMax

14、j-nCurj) =K) / T一行加上走到新位置，以及摘花生的時(shí)問 nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置 nTotaiPeanuts+=aFieldnMaxinMaxj; aFieldnMaxinMaxj=0; /摘走花生 else break； printf(“%dn”, nTotalPeanuts); 20常見問題這個(gè)題目應(yīng)該仔細(xì)閱讀。往往沒有看到每次只能拿剩下花生株中最大的，而是希望找到一種在規(guī)定時(shí)間內(nèi)能夠拿最多花生的組合，把題目變成了另外一道題。沒有讀到?jīng)]有

15、兩株花生株的花生數(shù)目相同”的條件，因此把題目復(fù)雜化了。這個(gè)題目是假設(shè)猴子在取花生的過程中不會(huì)回到大路上，而有些同學(xué)思考是否可能在中間回到大路上，因?yàn)轭}目沒說在大路上移動(dòng)要花時(shí)間，所以有可能中途出來再進(jìn)去摘的花生更多。本題的解法雖然直觀但是有一個(gè)弊端就是每次在尋找下一個(gè)最大花生植株時(shí)，都要遍歷整個(gè)矩陣，效率不高。用什么辦法才能高效率地找到下一個(gè)最大花生植株?21顯示器1、鏈接地址 2、問題描述 你的一個(gè)朋友買了一臺(tái)電腦。他以前只用過計(jì)算器，因?yàn)殡娔X的顯示器上顯示的數(shù)字的樣子和計(jì)算器是不一樣，所以當(dāng)他使用電腦的時(shí)候會(huì)比較郁悶。為了幫助他，你決定寫一個(gè)程序把在電腦上的數(shù)字顯示得像計(jì)算器上一樣。22問

16、題描述輸入數(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è)空白的行。注意：輸出中空白的地方都要用空格來填充。23問題描述輸入樣例2 123453 678900 024問題描述輸出樣例25一個(gè)計(jì)算器上的數(shù)字顯示單元，可以

17、看作由以下編號從1 到7 的7 個(gè)筆畫組成： 3、解題思路26 那么，我們可以說，數(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行到2s+2 行，就是所有數(shù)字的筆畫 5 和筆畫6，最后的第2s+3 行，是所有數(shù)字的筆畫7。如果某個(gè)數(shù)字d 沒有覆蓋某個(gè)筆畫m (m = 17)，那么，輸出數(shù)字d 的筆畫m 的時(shí)候，就應(yīng)該都輸出空格；如果覆蓋了筆

18、畫m，則輸出s 個(gè)-或s 個(gè)|，這取決于筆畫m 是橫的還是豎的。3、解題思路27由上思路，解決這道題目的關(guān)鍵，就在于如何記錄每個(gè)數(shù)字都覆蓋了哪些筆畫。實(shí)際上，如果我們記錄的是每個(gè)筆畫都被哪些數(shù)字覆蓋，則程序?qū)崿F(xiàn)起來更為容易。一個(gè)筆畫被哪些數(shù)字所覆蓋，可以用一個(gè)數(shù)組來記錄，比如記錄筆畫1 覆蓋情況的數(shù)組如下：char n111 = - - -;其中，n1i(i = 09) 代表筆畫1 是否被數(shù)字i 覆蓋。如果是，則n1i 為-，如果否，則n1i為空格。上面的數(shù)組的值體現(xiàn)了筆畫1 被數(shù)字0, 2, 3, 5, 6, 7, 8, 9 覆蓋。對于豎向的筆畫2，由字符 | 組成，則記錄其覆蓋情況的數(shù)組如

19、下：char n211 = | | |;該數(shù)組的值體現(xiàn)了筆畫2 被數(shù)字0, 4, 5, 6, 8, 9 覆蓋。3、解題思路284、參考程序#include #include char n111=- - -;/筆畫1 被數(shù)字0,2,3,5,6,7,8,9 覆蓋char n211=| | |;/筆畫2 被數(shù)字0,4,5,6,8,9 覆蓋char n311=| |;/筆畫3 被數(shù)字0,1,2,3,4,7,8,9 覆蓋char n411= - -;/筆畫4 被數(shù)字2,3,4,5,6,8,9 覆蓋char n511=| | | | ;/筆畫5 被數(shù)字0,2,6,8覆蓋char n611=| |;/筆畫6

20、 被數(shù)字0,1,3,4,5,6,7,8,9 覆蓋char n711=- - - -;/筆畫7 被數(shù)字0,2,3,5,6,8,9 覆蓋int main(void) int s; char szNumber20; int nDigit , nLength, i , j , k;294、參考程序 while(1) scanf( %d%s, &s, szNumber); if (s = 0) break; nLength = strlen(szNumber); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫1 nDigit = szNumberi - 0; printf

21、( ); for (j = 0 ; j s ; j+) /一個(gè)筆畫由s 個(gè)字符組成 printf(%c, n1nDigit); printf( );/兩個(gè)空格 printf(n);304、參考程序 for (i = 0 ; i s ; i+) /輸出所有數(shù)字的筆畫2 和筆畫3 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n2nDigit); for (k = 0 ; k s ; k+) printf( ); /筆畫2 和筆畫3 之間的空格 printf(%c , n3nDigit);/有一個(gè)空格 printf(

22、n); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/兩個(gè)空格 printf(n);314、參考程序 for (i = 0 ; i s ; i+) /輸出所有數(shù)字的筆畫5 和筆畫6 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n5nDigit); for (k = 0 ; k s ; k+) pr

23、intf( ); /筆畫5 和筆畫6 之間的空格 printf(%c , n6nDigit);/有一個(gè)空格 printf(n); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫7 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n7nDigit); printf( );/兩個(gè)空格 printf(n); printf(n); return 0;325、實(shí)現(xiàn)技巧一個(gè)筆畫被哪些數(shù)字所覆蓋，最直接的想法是用整型數(shù)組來記錄，比如：int n110 = 1, 0, 1, 1, 0, 1

24、, 1, 1, 1, 1 ;表示筆畫1 的被覆蓋情況。可是與其在數(shù)字i 的筆畫1 所處的位置進(jìn)行輸出的時(shí)候，根據(jù)n1i的值決定輸出空格還是- ，還不如直接用下面的char 類型數(shù)組來表示覆蓋情況：char n111 = - - -;這樣，在數(shù)字i 的筆畫1 所處的位置進(jìn)行輸出的時(shí)候，只要輸出s 個(gè)n1i就行了。這是一個(gè)很好的思路，它提醒我們，以后在編程時(shí)設(shè)置一些標(biāo)志的時(shí)候，要考慮一下是否可以直接用更有意義的東西將0，1 這樣的標(biāo)志代替。335、實(shí)現(xiàn)中常見的問題問題一：沒有注意到輸出是按行，即先輸出所有數(shù)字的第一畫，再輸出第二畫。于是想一個(gè)數(shù)字一個(gè)數(shù)字地從左到右輸出，編了一陣才發(fā)現(xiàn)不對。問題二：

25、忘了輸出空格。應(yīng)把所有的空白用空格符填充。例如：若要輸出4 的話就是這樣：（。表示空格）問題三：兩組數(shù)據(jù)之間要加一個(gè)空行。34排列1、鏈接地址 2、問題描述大家知道，給出正整數(shù)n，則1 到n 這n 個(gè)數(shù)可以構(gòu)成n！種排列，把這些排列按照從小到大的順序（字典順序）列出，如n=3 時(shí)，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六個(gè)排列。給出某個(gè)排列，求出這個(gè)排列的下k 個(gè)排列，如果遇到最后一個(gè)排列，則下1 排列為第1 個(gè)排列，即排列1 2 3n。比如：n = 3，k=2 給出排列2 3 1，則它的下1 個(gè)排列為3 1 2，下2 個(gè)排列為3 2 1，因此答案為3 2

26、1。35問題描述輸入數(shù)據(jù)第一行是一個(gè)正整數(shù)m，表示測試數(shù)據(jù)的個(gè)數(shù)，下面是m 組測試數(shù)據(jù)，每組測試數(shù)據(jù)第一行是2 個(gè)正整數(shù)n( 1 = n 1024 )和k(1=k=64)，第二行有n 個(gè)正整數(shù)，是1，2 n的一個(gè)排列。輸出要求對于每組輸入數(shù)據(jù)，輸出一行，n 個(gè)數(shù)，中間用空格隔開，表示輸入排列的下k 個(gè)排列。36問題描述輸入樣例33 12 3 13 13 2 110 21 2 3 4 5 6 7 8 9 10輸出樣例3 1 21 2 31 2 3 4 5 6 7 9 8 1037 這道題目，最直觀的想法是求出1 到n 的所有排列，然后將全部排列排序且慢，n最大可以是1024，1024! 個(gè)排列，

27、幾乎永遠(yuǎn)也算不出來，算出來也沒有地方存放。那么，有沒有公式或規(guī)律，能夠很快由一個(gè)排列推算出下k 個(gè)排列呢？實(shí)際上尋找規(guī)律或公式都是徒勞的，只能老老實(shí)實(shí)由給定排列算出下一個(gè)排列，再算出下一個(gè)排列一直算到第k的排列。鑒于k 的值很小，最多只有64，因此這種算法應(yīng)該是可行的。 如何由給定排列求下一個(gè)排列？不妨自己動(dòng)手做一下。比如： “2 1 4 7 6 3 5”的下一個(gè)排列是什么？容易，顯然是“2 1 4 7 6 5 3”，那么，再下一個(gè)排列是什么？有點(diǎn)難了，是“2 1 5 3 4 6 7”。3、解題思路383、解題思路以從“2 1 4 7 6 5 3”求出下一個(gè)排列 “2 1 5 3 4 6 7”

28、作為例子，可以總結(jié)出求給定排列的下一個(gè)排列的步驟：假設(shè)給定排列中的n 個(gè)數(shù)從左到右是a1, a2, a3an 。(1) 從an 開始，往左邊找，直到找到某個(gè)aj，滿足aj-1 aj（對上例, 這個(gè)aj 就是 7，aj-1 就是4）。(2) 在 aj 、aj+1 an 中找到最小的比aj-1 大的數(shù)，將這個(gè)數(shù)和 aj-1 互換位置（對上例, 這個(gè)數(shù)就是5，和4 換完位置后的排列是 “2 1 5 7 6 4 3”）。(3) 將從位置j 到位置n 的所有數(shù)（共n-j+1 個(gè)）從小到大重新排序，排好序后，新的排列就是所要求的排列。（對上例，就是將“7 6 4 3”排序，排好后的新排列就是“2 1 5 3 4 6 7”）。當(dāng)然，按照題目要求，如果a1, a2, a3an 已經(jīng)是降序，那么它的下一個(gè)排序就是an, an-1,an-2a1。394、參考程序#include #include #define MAX_NUM 1024int anMAX_NUM + 10;/用以排序的比較函數(shù)int MyCompare