第六課程設(shè)計(jì)大賽問(wèn)題與答案.doc

一、雞兔同籠問(wèn)題描述一個(gè)籠子里面關(guān)了雞和兔子（雞有2只腳，兔子有4只腳，沒(méi)有例外）。已經(jīng)知道了籠子里面腳的總數(shù)a，問(wèn)籠子里面至少有多少只動(dòng)物，至多有多少只動(dòng)物輸入數(shù)據(jù)第1行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)正整數(shù)a (a 32768)。輸出要求n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出是兩個(gè)正整數(shù)，第一個(gè)是最少的動(dòng)物數(shù)，第二個(gè)是最多的動(dòng)物數(shù)，兩個(gè)正整數(shù)用空格分開。如果沒(méi)有滿足要求的情況出現(xiàn)，則輸出2個(gè)0。 輸入樣例2320輸出樣例0 05 10解題思路這個(gè)問(wèn)題可以描述成任給一個(gè)整數(shù)N，如果N是奇數(shù)，輸出0 0，否則如果N是4的倍數(shù)，輸出N / 4 N / 2，如果N不是4的倍數(shù)，輸出N/4+1 N/2。這是一個(gè)一般的計(jì)算題，只要實(shí)現(xiàn)相應(yīng)的判斷和輸出代碼就可以了。題目中說(shuō)明了輸入整數(shù)在一個(gè)比較小的范圍內(nèi)，所以只需要考慮整數(shù)運(yùn)算就可以了。參考程序1. #include 2. void main( )3. 4. int nCases, i, nFeet; /nCases 表示輸入測(cè)試數(shù)據(jù)的組數(shù)，nFeet表示輸入的腳數(shù)。5. scanf(%d, &nCases);6. for(i = 0; i nCases; i+)7. scanf(%d, &nFeet);8. if(nFeet %2 != 0) / 如果有奇數(shù)只腳，則輸入不正確，9. / 因?yàn)椴徽?只還是4只，都是偶數(shù)10. printf(0 0n);11. else if (nFeet%4 != 0) /若要?jiǎng)游飻?shù)目最少，使動(dòng)物盡量有4只腳12. /若要?jiǎng)游飻?shù)目最多，使動(dòng)物盡量有2只腳13. printf(%d %dn, nFeet / 4 + 1, nFeet / 2);14. else printf(%d %dn, nFeet / 4, nFeet / 2);15. 16. 二、判斷閏年 問(wèn)題描述判斷某年是否是閏年。公歷紀(jì)年法中，能被4整除的大多是閏年，但能被100整除而不能被400整除的年份不是閏年，如1900年是平年，2000年是閏年。輸入數(shù)據(jù)一行，僅含一個(gè)整數(shù)a(0 a 3000)。輸出要求一行，如果公元a年是閏年輸出Y，否則輸出N。輸入樣例2006輸出樣例N解題思路這個(gè)題目主要考察閏年的定義，使用基本的邏輯判斷語(yǔ)句就可以了?？紤]到輸入的范圍在0到3000之間，所以判斷閏年時(shí)不必考慮能被3200整除的年份不是閏年的判定條件。程序應(yīng)該包括三個(gè)基本的步驟：正確讀入要判定的年份a；判定a是否為閏年；給出正確的輸出。其中，判斷輸入年份是否為閏年根據(jù)個(gè)人的思考習(xí)慣可以有不同的判定順序。參考解法一 分段排除：如果a % 4 ! = 0，則a不是閏年；否則如果a % 100 = 0 & a % 400 != 0，則a不是閏年；否則a是閏年。參考解法二 列出所有閏年的可能條件，滿足條件則為閏年，否則判為非閏年：如果 (a % 400 = 0 | (a % 4 = 0 & a % 100 != 0), 則a是閏年；否則 a不是閏年。參考程序一：1. #include 2. void main()3. 4. int a; /記錄待判定的年份5. scanf(%d, &a);6. if(a % 4 != 0) 7. printf(Nn);8. else if(a % 100 = 0 & a % 400 != 0)9. printf(Nn);10. else 11. printf(Yn);12. 參考程序二：1. #include 2. void main()3. int a;4. scanf(%d, &a);5. if(a % 4 = 0 & a % 100 != 0) | a % 400 = 0) 6. printf(Yn);7. else8. printf(Nn);9. 三、細(xì)菌繁殖 問(wèn)題描述一種細(xì)菌的繁殖速度是每天成倍增長(zhǎng)。例如：第一天有10個(gè)，第二天就變成20個(gè)，第三天變成40個(gè)，第四天變成80個(gè)，?，F(xiàn)在給出第一天的日期和細(xì)菌數(shù)目，要你寫程序求出到某一天的時(shí)候，細(xì)菌的數(shù)目。輸入數(shù)據(jù)第一行有一個(gè)整數(shù)n，表示測(cè)試數(shù)據(jù)的數(shù)目。其后n行每行有5個(gè)整數(shù)，整數(shù)之間用一個(gè)空格隔開。第一個(gè)數(shù)表示第一天的月份，第二個(gè)數(shù)表示第一天的日期，第三個(gè)數(shù)表示第一天細(xì)菌的數(shù)目，第四個(gè)數(shù)表示要求的那一天的月份，第五個(gè)數(shù)表示要求的那一天的日期。已知第一天和要求的一天在同一年并且該年不是閏年，要求的一天一定在第一天之后。數(shù)據(jù)保證要求的一天的細(xì)菌數(shù)目在整數(shù)范圍內(nèi)。輸出要求對(duì)于每一組測(cè)試數(shù)據(jù)，輸出一行，該行包含一個(gè)整數(shù)，為要求的一天的細(xì)菌數(shù)。輸入樣例21 1 1 1 22 28 10 3 2輸出樣例240解題思路這題實(shí)際上是求給定的兩天之間間隔的天數(shù)n，第一天的細(xì)菌數(shù)乘以2的n次方就是題目的答案。每個(gè)月的天數(shù)因?yàn)椴缓芤?guī)則，如果在程序中用規(guī)則描述會(huì)比較麻煩，所以可以使用一個(gè)數(shù)組將每個(gè)月的天數(shù)存起來(lái)。整個(gè)計(jì)算過(guò)程可以描述如下：讀入測(cè)試樣例數(shù)n；做n次：1. 讀入兩個(gè)日期及第一天的細(xì)菌數(shù)； 2. 將兩個(gè)日期轉(zhuǎn)換為當(dāng)年的第幾天； 3得到兩個(gè)天數(shù)的差，即它們中間間隔的天數(shù)m； 4用第一天的細(xì)菌數(shù)乘以2的m次方等到x; 5. 輸出x;參考程序參考程序一： / 作者 c0610002080131. #include 2. void main( )3. 4. int days12 = 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31;5. int n;6. int i;7. int sum;8. int k;9. long nNum;10. scanf(%d, &n);11. for(i = 0; i n; i +)12. int month_1, day_1, month_2, day_2, num; /起止日期的月份和日期。13. scanf(%d%d%d%d%d, &month_1, &day_1, &num,&month_2, &day_2);14. sum = 0;15. for(k = month_1; k month_2; k +)16. sum += daysk - 1;17. 18. sum -= day_1;19. sum += day_2;20.21. nNum = num;22. for(k = 0; k sum; k +)23. nNum *= 2;24. 25. printf(%dn, nNum);26. 27. 28.參考程序二： / 作者c0601005483021. #include 2. int month=0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31;3. void main()4. 5. int times;6. scanf(%d, ×);7. int mon1, date1, mon2, date2, num1;8. while(times -)9. scanf(%d%d%d%d%d, &mon1, &date1, &num1, &mon2, &date2);10. int days = date2 - date1;11. for(int i = mon1; i mon2; i+)12. days += monthi;13. 14. long num = num1;15. for(int j = 0; j days; j+)16. num *= 2;17. 18. printf( %dn, num );19. 20. 四、八皇后問(wèn)題 問(wèn)題描述會(huì)下國(guó)際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個(gè)皇后放在棋盤上（有8 * 8個(gè)方格），使它們誰(shuí)也不能被吃掉！這就是著名的八皇后問(wèn)題。 對(duì)于某個(gè)滿足要求的8皇后的擺放方法，定義一個(gè)皇后串a(chǎn)與之對(duì)應(yīng)，即a=b1b2.b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問(wèn)題一共有92組解（即92個(gè)不同的皇后串）。給出一個(gè)數(shù)b，要求輸出第b個(gè)串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時(shí)比y小。 輸入數(shù)據(jù)第1行是測(cè)試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測(cè)試數(shù)據(jù)占1行，包括一個(gè)正整數(shù)b(1 = b = 92)輸出要求n行，每行輸出對(duì)應(yīng)一個(gè)輸入。輸出應(yīng)是一個(gè)正整數(shù)，是對(duì)應(yīng)于b的皇后串輸入樣例2192輸出樣例1586372484136275解題思路一因?yàn)橐蟪?2種不同擺放方法中的任意一種，所以我們不妨把92種不同的擺放方法一次性求出來(lái)，存放在一個(gè)數(shù)組里。為求解這道題我們需要有一個(gè)矩陣仿真棋盤，每次試放一個(gè)棋子時(shí)只能放在尚未被控制的格子上，一旦放置了一個(gè)新棋子，就在它所能控制的所有位置上設(shè)置標(biāo)記，如此下去把八個(gè)棋子放好。當(dāng)完成一種擺放時(shí)，就要嘗試下一種。若要按照字典序?qū)⒖尚械臄[放方法記錄下來(lái)，就要按照一定的順序進(jìn)行嘗試。也就是將第一個(gè)棋子按照從小到大的順序嘗試；對(duì)于第一個(gè)棋子的每一個(gè)位置，將第二個(gè)棋子從可行的位置從小到大的順序嘗試；在第一第二個(gè)棋子固定的情況下，將第三個(gè)棋子從可行的位置從小到大的順序嘗試；依次類推。首先，我們有一個(gè)8*8的矩陣仿真棋盤標(biāo)識(shí)當(dāng)前已經(jīng)擺放好的棋子所控制的區(qū)域。用一個(gè)有92行每行8個(gè)元素的二維數(shù)組記錄可行的擺放方法。用一個(gè)遞歸程序來(lái)實(shí)現(xiàn)嘗試擺放的過(guò)程?；舅枷胧羌僭O(shè)我們將第一個(gè)棋子擺好，并設(shè)置了它所控制的區(qū)域，則這個(gè)問(wèn)題變成了一個(gè)7皇后問(wèn)題，用與8皇后同樣的方法可以獲得問(wèn)題的解。那我們就把重心放在如何擺放一個(gè)皇后棋子上，擺放的基本步驟是：從第1到第8個(gè)位置，順序地嘗試將棋子放置在每一個(gè)未被控制的位置上，設(shè)置該棋子所控制的格子，將問(wèn)題變?yōu)楦∫?guī)模的問(wèn)題向下遞歸，需要注意的是每次嘗試一個(gè)新的未被控制的位置前，要將上一次嘗試的位置所控制的格子復(fù)原。參考程序一1. #include 2. #include 3.4. int queenPlaces928; /存放92種皇后棋子的擺放方法5. int count = 0;6. int board88; /仿真棋盤7. void putQueen(int ithQueen); /遞歸函數(shù)，每次擺好一個(gè)棋子8.9. void main()10. 11. int n, i, j; 12. for(i = 0; i 8; i+) / 初始化13. for(j = 0; j 8; j+)14. boardij = -1;15. for(j = 0; j 92; j+)16. queenPlacesji = 0;17. 18. putQueen(0); /從第0個(gè)棋子開始擺放，運(yùn)行的結(jié)果是將queenPlaces生成好19. scanf(%d, &n);20. for(i = 0; i n; i+)21. int ith;22. scanf(%d, &ith);23. for(j = 0; j 8; j+)24. printf(%d, queenPlacesith - 1j);25. printf(n);26. 27. 28. void putQueen(int ithQueen)29. int i, k, r;30. if(ithQueen = 8)31. count +;32. return;33. 34. for(i = 0; i 8; i+)35. if(boardiithQueen = -1)36. /擺放皇后37. boardiithQueen = ithQueen;38. /將其后所有的擺放方法的第ith個(gè)皇后都放在i+1的位置上39. /在i增加以后，后面的第ith個(gè)皇后擺放方法后覆蓋此時(shí)的設(shè)置40. for(k = count; k 92; k+)41. queenPlaceskithQueen = i + 1;42. /設(shè)置控制范圍43. for(k = 0; k 8; k+)44. for(r = 0; r 8; r+)45. if(boardkr = -1 & 46. (k = i | r = ithQueen | abs(k - i) = abs(r - ithQueen) 47. boardkr = ithQueen;48. /向下級(jí)遞歸49. putQueen(ithQueen + 1);50. /回溯，撤銷控制范圍51. for(k = 0; k 8; k+)52. for(r = 0; r 8; r+)53. if(boardkr = ithQueen) boardkr = -1;54. 55. 56. 解題思路二上面的方法用一個(gè)二維數(shù)組來(lái)記錄棋盤被已經(jīng)放置的棋子的控制情況，每次有新的棋子放置時(shí)用了枚舉法來(lái)判斷它控制的范圍。還可以用三個(gè)一維數(shù)組來(lái)分別記錄每一列，每個(gè)45度的斜線和每個(gè)135度的斜線上是否已經(jīng)被已放置的棋子控制，這樣每次有新的棋子放置時(shí)，不必再搜索它的控制范圍，可以直接通過(guò)三個(gè)一維數(shù)組判斷它是否與已經(jīng)放置的棋子沖突，在不沖突的情況下，也可以通過(guò)分別設(shè)置三個(gè)一維數(shù)組的相應(yīng)的值，來(lái)記錄新棋子的控制范圍。參考程序二1. #include 2. int record929, mark9, count = 0; /record記錄全部解，mark記錄當(dāng)前解；3. bool range9, line117, line217; /分別記錄列方向，45度，135度方向上被控制的情況4. void tryToPut(int ); /求全部解的過(guò)程5. void main()6. 7. int i, testtimes, num;8. scanf(%d, &testtimes);9. 10. for(i = 0; i =8; i+)11. rangei = true;12. for(i = 0; i 17; i +)13. line1i = line2i = true;14.15. tryToPut(1);16.17. while(testtimes -)18. scanf(%d, &num);19. for(i = 1; i 8) /如果最后一個(gè)皇后被放置完畢，將當(dāng)前解復(fù)制到全部解中27. for(int k = 1; k 9; k +) 28. recordcountk = markk;29. count +;30. 31. for(int j=1; j=8; j+) 逐一嘗試將當(dāng)前皇后放置在不同列上32. if(rangej & line1 i + j & line2i - j + 9) /如果與前面的不沖突，33. /則把當(dāng)前皇后放置在當(dāng)前位置34. marki = j;35. rangej = line1i + j = line2i - j + 9 = false;36. tryToPut(i + 1);37. rangej = line1i + j = line2i - j + 9 = true;38. 39. 40. 解題思路三這個(gè)題目也可以不用仿真棋盤來(lái)模擬已放置棋子的控制區(qū)域，而只用一個(gè)有8個(gè)元素的數(shù)組記錄已經(jīng)擺放的棋子擺在什么位置，當(dāng)要放置一個(gè)新的棋子時(shí)，只需要判斷它與已經(jīng)放置的棋子之間是否沖突就行了。參考程序三1. #include 2. int ans928, n, b, i, j, num, hang8;3. void queen(int i)4. int j, k;5. if(i = 8) /一組新的解產(chǎn)生了6. for(j = 0; j 8; j+) ansnumj = hangj + 1;7. num+;8. return;9. 10. for (j=0; j8; j+) /將當(dāng)前皇后i逐一嘗試放置在不同的列11. for(k=0; ki; k+) /逐一判定i與前面的皇后是否沖突12. if( hangk = j | (k - i) = (hangk - j) | (i - k) = (hangk - j ) break;13. if (k = i) /放置i，嘗試第i+1個(gè)皇后14. hangi = j;15. queen(i + 1);16. 17. 18. 19. void main( )20. num=0;21. queen(0);22. scanf(“%d”, &n);23. for(i = 0; i n; i+)24. scanf(“%d”, &b);25. for(j = 0; j 8; j+) printf(“%d”, ansb - 1j);26. printf(“n”);27. 28. 1.五、# include # include # include using namespace std;int main(int argc,char* argv) ifstream cin (aaa.txt); string s,t; int n; cinn; for (int i=0;is; int c=0; t=s0; int temp=0; for(int j=0;js.size();j+) if(sj=t0) temp+; if(j=s.size()-1) if(temp=1)coutt0; else couttempt0; else if(temp=1)coutt0; else couttempt0; t0=sj; temp=1; if(j=s.size()-1) if(temp=1)coutt0; else couttempt0; coutendl;s=; return 0;六、A New Stone GameDescriptionAlice and Bob decide to play a new stone game.At the beginning of the game they pick n(1=n=10) piles of stones in a line. Alice and Bob move the stones in turn. At each step of the game,the player choose a pile,remove at least one stones,then freely move stones from this pile to any other pile that still has stones. For example:n=4 and the piles have (3,1,4,2) stones.If the player chose the first pile and remove one.Then it can reach the follow states. 2 1 4 2 1 2 4 2（move one stone to Pile 2） 1 1 5 2（move one stone to Pile 3） 1 1 4 3（move one stone to Pile 4） 0 2 5 2（move one stone to Pile 2 and another one to Pile 3） 0 2 4 3（move one stone to Pile 2 and another one to Pile 4） 0 1 5 3（move one stone to Pile 3 and another one to Pile 4） 0 3 4 2（move two stones to Pile 2） 0 1 6 2（move two stones to Pile 3） 0 1 4 4（move two stones to Pile 4） Alice always moves first. Suppose that both Alice and Bob do their best in the game. You are to write a program to determine who will finally win the game. Input The input contains several test cases. The first line of each test case contains an integer number n, denoting the number of piles. The following n integers describe the number of stones in each pile at the beginning of the game, you may assume the number of stones in each pile will not exceed 100. The last test case is followed by one zero. Output For each test case, if Alice win the game,output 1,otherwise output 0. Sample Input 32 1 321 10Sample Output 10#include #include #include #define MAXN 11long hMAXN;long n;bool Init()long k;cinn;for (k=0;khk;return n!=0;bool GirlWin()long k;if (n%2=1) return true;std:sort(h,h+n);for (k=0;kn;k+=2)if (hk!=hk+1) return true;return false;int main()while (Init()if (GirlWin() cout1endl;else cout0endl;return 0;七、Look and Say來(lái)源（/onlinejudge/showProblem.do?problemCode=2886）The look and say sequence is defined as follows. Start with any string of digits as the first element in the sequence. Each subsequent element is defined from the previous one by verbally describing the previous element. For example, the string 122344111 can be described as one 1, two 2s, one 3, two 4s, three 1s. Therefore, the element that comes after 122344111 in the sequence is 1122132431. Similarly, the string 101 comes after 1111111111. Notice that it is generally not possible to uniquely identify the previous element of a particular element. For example, a string of 112213243 1s also yields 1122132431 as the next element. InputThe input consists of a number of cases. The first line gives the number of cases to follow. Each case consists of a line of up to 1000 digits. OutputFor each test case, print the string that follows the given string. Sample Input3122344111111111111112345Sample Output11221324311011112131415答案# include # include # include using namespace std;int main(int argc,char* argv) ifstream cin (aaa.txt); string s,t; int n; cinn; for (int i=0;is; int c=0; t=s0; int temp=0; for(int j=0;js.size();j+) if(sj=t0) temp+; if(j=s.size()-1) printf(%d%c,temp,t0); else printf(%d%c,temp,t0); t0=sj; temp=1; if(j=s.size()-1) printf(%d%c,temp,t0); coutendl; return 0;八、Image Transformation來(lái)源（/onlinejudge/showProblem.do?problemCode=2857）The image stored on a computer can be represented as a matrix of pixels. In the RGB (Red-Green-Blue) color system, a pixel can be described as a triplex integer numbers. That is, the color of a pixel is in the format r g b where r, g and b are integers ranging from 0 to 255(inclusive) which represent the Red, Green and Blue level of that pixel. Sometimes however, we may need a gray picture instead of a colorful one. One of the simplest way to transform a RGB picture into gray: for each pixel, we set the Red, Green and Blue level to a same value which is usually the average of the Red, Green and Blue level of that pixel (that is (r + g + b)/3, here we assume that the sum of r, g and b is always dividable b