第八周 模擬問(wèn)題

1、第八講模擬問(wèn)題ACM算法與程序設(shè)計(jì)現(xiàn)實(shí)中的有些問(wèn)題難以找到公式或規(guī)律來(lái)解決。只能按照一定步驟不停地做下去，最后才能得到答案。這樣的問(wèn)題，用計(jì)算機(jī)來(lái)解決十分合適，只要能讓計(jì)算機(jī)模擬人在解決問(wèn)題時(shí)的行為即可。這一類的問(wèn)題可以稱之為“模擬題”。2約瑟夫問(wèn)題 問(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)。 http:/problem?id=27463Input每行是用空格分開(kāi)的兩個(gè)整數(shù)，第一個(gè)是 n, 第二個(gè)是 m

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

3、組元素，相當(dāng)于人的手指；劃掉一個(gè)數(shù)的操作，就用將一個(gè)數(shù)組元素置0的方法來(lái)實(shí)現(xiàn)。要跳過(guò)已經(jīng)被劃掉的數(shù)，那么就要跳過(guò)為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的元素開(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)更方便。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) /跳過(guò)已經(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常見(jiàn)問(wèn)題程序完全模擬了人工操作的過(guò)程，但因?yàn)橐磸?fù)跳過(guò)為0的數(shù)組元素，因此算法的效率不是很高。采用單鏈表進(jìn)行模擬來(lái)解決本題。就能省去跳過(guò)已出圈的猴子這個(gè)操作，大大提高了效率。在數(shù)組里循環(huán)計(jì)數(shù)的時(shí)候，一定要小心計(jì)算其開(kāi)始的下標(biāo)和終止的下標(biāo)。比如循環(huán)是從0到n-1，而不是從0到n?；赝艘粋€(gè)位置，易被忽略或?qū)戝e(cuò)。比如只寫(xiě)了語(yǔ)句nPtr-，忘了處理nPtr變成小于0的情況

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

7、可以做下列四件事情中的一件： 1) 從路邊跳到最靠近路邊（即第一行）的某棵花生植株； 2) 從一棵植株跳到前后左右與之相鄰的另一棵植株； 3) 采摘一棵植株下的花生； 4) 從最靠近路邊（即第一行）的某棵花生植株跳回路邊。 現(xiàn)在給定一塊花生田的大小和花生的分布，請(qǐng)問(wèn)在限定時(shí)間內(nèi)，多多最多可以采到多少個(gè)花生？注意可能只有部分植株下面長(zhǎng)有花生，假設(shè)這些植株下的花生個(gè)數(shù)各不相同。 12例如在圖2所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下長(zhǎng)有花生，個(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，用空格隔開(kāi)；表示花生田的大小為M * N（1 = M, N = 50），多多采花生的限定時(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)有花生。 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è)以花生矩陣作為自變量的公式來(lái)解決這個(gè)問(wèn)題，是不現(xiàn)實(shí)的。結(jié)果只能是做了才知道。即走進(jìn)花生地每次要采下一株花生之前，先計(jì)算一下剩下的時(shí)間夠不夠走到那株花生，采摘，并從那株花生走回到路上。如果時(shí)問(wèn)夠則走過(guò)去采摘；如果時(shí)間不夠，則采摘活動(dòng)到此結(jié)束。設(shè)二維數(shù)組aField存放花生地的信息。然而，用aField00還是aField11對(duì)應(yīng)花生地的左上角是值得思考一下的。因?yàn)閺牡乩锏铰飞线€需要1個(gè)單位時(shí)間，題目中的坐標(biāo)又都是從1開(kāi)始。所

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

11、 歷的年份，m 對(duì)13 取模后得到0 到12 的值，這個(gè)值要加1 才能用于表示Tzolkin歷的日期，同時(shí)m 對(duì)20 取模后得到019 的數(shù)值，分別表示取20 個(gè)字符串中的一個(gè)。如果我們用字符串?dāng)?shù)組來(lái)存儲(chǔ)這20 個(gè)字符串，則019的取值正好對(duì)應(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); /花生地的左上角對(duì)應(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í)問(wèn) int nCuri=0，nCurj; /當(dāng)前位置坐標(biāo)， /nCuri代表縱坐標(biāo)，開(kāi)始是在路上，所以初值為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)沒(méi)有花生了 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í)問(wèn) nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; /走到新的位置 nTotaiPeanuts+=aFieldnMaxinMaxj; aFieldnMaxinMaxj=0; /摘走花生 else break； printf(“%dn”, nTotalPeanuts); 20常見(jiàn)問(wèn)題這個(gè)題目應(yīng)該仔細(xì)閱讀。往往沒(méi)有看到每次只能拿剩下花生株中最大的，而是希望找到一種在規(guī)定時(shí)間內(nèi)能夠拿最多花生的組合，把題目變成了另外一道題。沒(méi)有讀到?jīng)]有

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

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

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

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

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

20、 被數(shù)字0,1,3,4,5,6,7,8,9 覆蓋char n711=- - - -;/筆畫(huà)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ù)字的筆畫(huà)1 nDigit = szNumberi - 0; printf

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

22、n); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫(huà)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ù)字的筆畫(huà)5 和筆畫(huà)6 for (j = 0 ; j nLength ; j+) nDigit = szNumberj - 0; printf(%c, n5nDigit); for (k = 0 ; k s ; k+) pr

23、intf( ); /筆畫(huà)5 和筆畫(huà)6 之間的空格 printf(%c , n6nDigit);/有一個(gè)空格 printf(n); for (i = 0 ; i nLength ; i+) /輸出所有數(shù)字的筆畫(huà)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è)筆畫(huà)被哪些數(shù)字所覆蓋，最直接的想法是用整型數(shù)組來(lái)記錄，比如：int n110 = 1, 0, 1, 1, 0, 1

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

25、忘了輸出空格。應(yīng)把所有的空白用空格符填充。例如：若要輸出4 的話就是這樣：（。表示空格）問(wèn)題三：兩組數(shù)據(jù)之間要加一個(gè)空行。34排列1、鏈接地址 2、問(wèn)題描述大家知道，給出正整數(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問(wèn)題描述輸入數(shù)據(jù)第一行是一個(gè)正整數(shù)m，表示測(cè)試數(shù)據(jù)的個(gè)數(shù)，下面是m 組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)第一行是2 個(gè)正整數(shù)n( 1 = n 1024 )和k(1=k=64)，第二行有n 個(gè)正整數(shù)，是1，2 n的一個(gè)排列。輸出要求對(duì)于每組輸入數(shù)據(jù)，輸出一行，n 個(gè)數(shù)，中間用空格隔開(kāi)，表示輸入排列的下k 個(gè)排列。36問(wèn)題描述輸入樣例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)也算不出來(lái)，算出來(lái)也沒(méi)有地方存放。那么，有沒(méi)有公式或規(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 開(kāi)始，往左邊找，直到找到某個(gè)aj，滿足aj-1 aj（對(duì)上例, 這個(gè)aj 就是 7，aj-1 就是4）。(2) 在 aj 、aj+1 an 中找到最小的比aj-1 大的數(shù)，將這個(gè)數(shù)和 aj-1 互換位置（對(duì)上例, 這個(gè)數(shù)就是5，和4 換完位置后的排列是 “2 1 5 7 6 4 3”）。(3) 將從位置j 到位置n 的所有數(shù)（共n-j+1 個(gè)）從小到大重新排序，排好序后，新的排列就是所要求的排列。（對(duì)上例，就是將“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