第八周 模擬問題

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

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

3、組元素，相當于人的手指；劃掉一個數的操作，就用將一個數組元素置0的方法來實現(xiàn)。要跳過已經被劃掉的數，那么就要跳過為0的數組元素。需要注意的是，當nPtr指向aLoop中最后一個元素(下標n-1)時，再數下一個，則nPtr要指回到數組的第一個元素(下標0)，這樣aLoop才像一個圈。6實現(xiàn)技巧n個元素的數組，從下標0的元素開始存放猴子編號，則循環(huán)報數的時候，下一個猴子的下標就是“(當前猴子下標+1)n”。這種寫法比用分支語句來決定下個猴子的下標是多少更快捷而且寫起來更方便。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; /記錄本輪數到的猴子數目 whi1e(nCountedm) /一直要數出m個猴子 while(aLoopnPtr=0) /跳過已經出圈的猴子 nPtr=(nPtr+1)%n;/到下一個位置 nCounted+; /數到一只猴子 nPtr=(nPtr+1)%n

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

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

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

8、Input輸入的第一行包括一個整數T，表示數據組數。 每組輸入的第一行包括三個整數，M, N和K，用空格隔開；表示花生田的大小為M * N（1 = M, N = 50），多多采花生的限定時間為K（0 = K = 1000）個單位時間。接下來的M行，每行包括N個非負整數，也用空格隔開；第i + 1行的第j個整數Pij（0 = Pij = 500）表示花生田里植株(i, j)下花生的數目，0表示該植株下沒有花生。 Output輸出包括T行，每一行只包含一個整數，即在限定時間內，多多最多可以采到花生的個數。 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ī)律得到一個以花生矩陣作為自變量的公式來解決這個問題，是不現(xiàn)實的。結果只能是做了才知道。即走進花生地每次要采下一株花生之前，先計算一下剩下的時間夠不夠走到那株花生，采摘，并從那株花生走回到路上。如果時問夠則走過去采摘；如果時間不夠，則采摘活動到此結束。設二維數組aField存放花生地的信息。然而，用aField00還是aField11對應花生地的左上角是值得思考一下的。因為從地里到路上還需要1個單位時間，題目中的坐標又都是從1開始。所

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

11、 歷的年份，m 對13 取模后得到0 到12 的值，這個值要加1 才能用于表示Tzolkin歷的日期，同時m 對20 取模后得到019 的數值，分別表示取20 個字符串中的一個。如果我們用字符串數組來存儲這20 個字符串，則019的取值正好對應需要的字符串的數組下標。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); /花生地的左上角對應的數組元素是aField11，路的縱坐標是0 for(int m=1; m=M; m+) for(int n=1; n=N; n+) scanf(“d”，&afieldmn); int nTotalPeanuts=0; /摘到的花生總數 int nTotalTime=O; /已經花去的時問 int nCuri=0，nCurj; /當前位置坐標， /nCuri代表縱坐標，開始是在路上，所以初值為018 while(nTotalTimeK) /如果還有時間 int nMax=0, nMaxi, nMaxj /最大的花生數目，及其所處的位置 for(int

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

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

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

16、題描述輸入數據輸入包括若干行，每行表示一個要顯示的數。每行有兩個整數s 和n (1 = s = 10, 0 =n= 99999999)，這里n 是要顯示的數，s 是要顯示的數的尺寸。如果某行輸入包括兩個0，表示輸入結束。這行不需要處理。輸出要求顯示的方式是：用s 個-表示一個水平線段，用s 個|表示一個垂直線段。這種情況下，每一個數字需要占用s+2 列和2s+3 行。另外，在兩個數字之間要輸出一個空白的列。在輸出完每一個數之后，輸出一個空白的行。注意：輸出中空白的地方都要用空格來填充。23問題描述輸入樣例2 123453 678900 024問題描述輸出樣例25一個計算器上的數字顯示單元，可以

17、看作由以下編號從1 到7 的7 個筆畫組成： 3、解題思路26 那么，我們可以說，數字8 覆蓋了所有的筆畫，數字7 覆蓋筆畫1、3 和6，而數字1覆蓋筆畫3、6。注意，每個筆畫都是由s 個-或s 個|組成。 輸出時，先輸出第1 行，即整數n 中所有數字里的筆畫1，然后輸出第2 行到第s+1 行，即所有數字的筆畫2 和筆畫3，接下來是第s+2 行，即所有數字的筆畫4，再接下來是第s+3行到2s+2 行，就是所有數字的筆畫 5 和筆畫6，最后的第2s+3 行，是所有數字的筆畫7。如果某個數字d 沒有覆蓋某個筆畫m (m = 17)，那么，輸出數字d 的筆畫m 的時候，就應該都輸出空格；如果覆蓋了筆

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

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

20、 被數字0,1,3,4,5,6,7,8,9 覆蓋char n711=- - - -;/筆畫7 被數字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+) /輸出所有數字的筆畫1 nDigit = szNumberi - 0; printf

21、( ); for (j = 0 ; j s ; j+) /一個筆畫由s 個字符組成 printf(%c, n1nDigit); printf( );/兩個空格 printf(n);304、參考程序 for (i = 0 ; i s ; i+) /輸出所有數字的筆畫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);/有一個空格 printf(

22、n); for (i = 0 ; i nLength ; i+) /輸出所有數字的筆畫4 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n4nDigit); printf( );/兩個空格 printf(n);314、參考程序 for (i = 0 ; i s ; i+) /輸出所有數字的筆畫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);/有一個空格 printf(n); for (i = 0 ; i nLength ; i+) /輸出所有數字的筆畫7 printf( ); nDigit = szNumberi - 0; for (j = 0 ; j s ; j+) printf(%c, n7nDigit); printf( );/兩個空格 printf(n); printf(n); return 0;325、實現(xiàn)技巧一個筆畫被哪些數字所覆蓋，最直接的想法是用整型數組來記錄，比如：int n110 = 1, 0, 1, 1, 0, 1

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

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

26、1。35問題描述輸入數據第一行是一個正整數m，表示測試數據的個數，下面是m 組測試數據，每組測試數據第一行是2 個正整數n( 1 = n 1024 )和k(1=k=64)，第二行有n 個正整數，是1，2 n的一個排列。輸出要求對于每組輸入數據，輸出一行，n 個數，中間用空格隔開，表示輸入排列的下k 個排列。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! 個排列，

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

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