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

一、雞兔同籠問題描述一個籠子里面關(guān)了雞和兔子（雞有2只腳，兔子有4只腳，沒有例外）。已經(jīng)知道了籠子里面腳的總數(shù)a，問籠子里面至少有多少只動物，至多有多少只動物輸入數(shù)據(jù)第1行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據(jù)占1行，包括一個正整數(shù)a (a 32768)。輸出要求n行，每行輸出對應(yīng)一個輸入。輸出是兩個正整數(shù)，第一個是最少的動物數(shù)，第二個是最多的動物數(shù)，兩個正整數(shù)用空格分開。如果沒有滿足要求的情況出現(xiàn)，則輸出2個0。 輸入樣例2320輸出樣例0 05 10解題思路這個問題可以描述成任給一個整數(shù)N，如果N是奇數(shù)，輸出0 0，否則如果N是4的倍數(shù)，輸出N / 4 N / 2，如果N不是4的倍數(shù)，輸出N/4+1 N/2。這是一個一般的計算題，只要實現(xiàn)相應(yīng)的判斷和輸出代碼就可以了。題目中說明了輸入整數(shù)在一個比較小的范圍內(nèi)，所以只需要考慮整數(shù)運算就可以了。參考程序1. #include 2. void main( )3. 4. int nCases, i, nFeet; /nCases 表示輸入測試數(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. / 因為不論2只還是4只，都是偶數(shù)10. printf(0 0n);11. else if (nFeet%4 != 0) /若要動物數(shù)目最少，使動物盡量有4只腳12. /若要動物數(shù)目最多，使動物盡量有2只腳13. printf(%d %dn, nFeet / 4 + 1, nFeet / 2);14. else printf(%d %dn, nFeet / 4, nFeet / 2);15. 16. 二、判斷閏年 問題描述判斷某年是否是閏年。公歷紀年法中，能被4整除的大多是閏年，但能被100整除而不能被400整除的年份不是閏年，如1900年是平年，2000年是閏年。輸入數(shù)據(jù)一行，僅含一個整數(shù)a(0 a 3000)。輸出要求一行，如果公元a年是閏年輸出Y，否則輸出N。輸入樣例2006輸出樣例N解題思路這個題目主要考察閏年的定義，使用基本的邏輯判斷語句就可以了?？紤]到輸入的范圍在0到3000之間，所以判斷閏年時不必考慮能被3200整除的年份不是閏年的判定條件。程序應(yīng)該包括三個基本的步驟：正確讀入要判定的年份a；判定a是否為閏年；給出正確的輸出。其中，判斷輸入年份是否為閏年根據(jù)個人的思考習(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. 三、細菌繁殖 問題描述一種細菌的繁殖速度是每天成倍增長。例如：第一天有10個，第二天就變成20個，第三天變成40個，第四天變成80個，?，F(xiàn)在給出第一天的日期和細菌數(shù)目，要你寫程序求出到某一天的時候，細菌的數(shù)目。輸入數(shù)據(jù)第一行有一個整數(shù)n，表示測試數(shù)據(jù)的數(shù)目。其后n行每行有5個整數(shù)，整數(shù)之間用一個空格隔開。第一個數(shù)表示第一天的月份，第二個數(shù)表示第一天的日期，第三個數(shù)表示第一天細菌的數(shù)目，第四個數(shù)表示要求的那一天的月份，第五個數(shù)表示要求的那一天的日期。已知第一天和要求的一天在同一年并且該年不是閏年，要求的一天一定在第一天之后。數(shù)據(jù)保證要求的一天的細菌數(shù)目在整數(shù)范圍內(nèi)。輸出要求對于每一組測試數(shù)據(jù)，輸出一行，該行包含一個整數(shù)，為要求的一天的細菌數(shù)。輸入樣例21 1 1 1 22 28 10 3 2輸出樣例240解題思路這題實際上是求給定的兩天之間間隔的天數(shù)n，第一天的細菌數(shù)乘以2的n次方就是題目的答案。每個月的天數(shù)因為不很規(guī)則，如果在程序中用規(guī)則描述會比較麻煩，所以可以使用一個數(shù)組將每個月的天數(shù)存起來。整個計算過程可以描述如下：讀入測試樣例數(shù)n；做n次：1. 讀入兩個日期及第一天的細菌數(shù)； 2. 將兩個日期轉(zhuǎn)換為當(dāng)年的第幾天； 3得到兩個天數(shù)的差，即它們中間間隔的天數(shù)m； 4用第一天的細菌數(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. 四、八皇后問題 問題描述會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。 對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a(chǎn)與之對應(yīng)，即a=b1b2.b8，其中bi為相應(yīng)擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個不同的皇后串）。給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當(dāng)且僅當(dāng)將x視為整數(shù)時比y小。 輸入數(shù)據(jù)第1行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據(jù)占1行，包括一個正整數(shù)b(1 = b = 92)輸出要求n行，每行輸出對應(yīng)一個輸入。輸出應(yīng)是一個正整數(shù)，是對應(yīng)于b的皇后串輸入樣例2192輸出樣例1586372484136275解題思路一因為要求出92種不同擺放方法中的任意一種，所以我們不妨把92種不同的擺放方法一次性求出來，存放在一個數(shù)組里。為求解這道題我們需要有一個矩陣仿真棋盤，每次試放一個棋子時只能放在尚未被控制的格子上，一旦放置了一個新棋子，就在它所能控制的所有位置上設(shè)置標記，如此下去把八個棋子放好。當(dāng)完成一種擺放時，就要嘗試下一種。若要按照字典序?qū)⒖尚械臄[放方法記錄下來，就要按照一定的順序進行嘗試。也就是將第一個棋子按照從小到大的順序嘗試；對于第一個棋子的每一個位置，將第二個棋子從可行的位置從小到大的順序嘗試；在第一第二個棋子固定的情況下，將第三個棋子從可行的位置從小到大的順序嘗試；依次類推。首先，我們有一個8*8的矩陣仿真棋盤標識當(dāng)前已經(jīng)擺放好的棋子所控制的區(qū)域。用一個有92行每行8個元素的二維數(shù)組記錄可行的擺放方法。用一個遞歸程序來實現(xiàn)嘗試擺放的過程?；舅枷胧羌僭O(shè)我們將第一個棋子擺好，并設(shè)置了它所控制的區(qū)域，則這個問題變成了一個7皇后問題，用與8皇后同樣的方法可以獲得問題的解。那我們就把重心放在如何擺放一個皇后棋子上，擺放的基本步驟是：從第1到第8個位置，順序地嘗試將棋子放置在每一個未被控制的位置上，設(shè)置該棋子所控制的格子，將問題變?yōu)楦∫?guī)模的問題向下遞歸，需要注意的是每次嘗試一個新的未被控制的位置前，要將上一次嘗試的位置所控制的格子復(fù)原。參考程序一1. #include 2. #include 3.4. int queenPlaces928; /存放92種皇后棋子的擺放方法5. int count = 0;6. int board88; /仿真棋盤7. void putQueen(int ithQueen); /遞歸函數(shù)，每次擺好一個棋子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個棋子開始擺放，運行的結(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個皇后都放在i+1的位置上39. /在i增加以后，后面的第ith個皇后擺放方法后覆蓋此時的設(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. /向下級遞歸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. 解題思路二上面的方法用一個二維數(shù)組來記錄棋盤被已經(jīng)放置的棋子的控制情況，每次有新的棋子放置時用了枚舉法來判斷它控制的范圍。還可以用三個一維數(shù)組來分別記錄每一列，每個45度的斜線和每個135度的斜線上是否已經(jīng)被已放置的棋子控制，這樣每次有新的棋子放置時，不必再搜索它的控制范圍，可以直接通過三個一維數(shù)組判斷它是否與已經(jīng)放置的棋子沖突，在不沖突的情況下，也可以通過分別設(shè)置三個一維數(shù)組的相應(yīng)的值，來記錄新棋子的控制范圍。參考程序二1. #include 2. int record929, mark9, count = 0; /record記錄全部解，mark記錄當(dāng)前解；3. bool range9, line117, line217; /分別記錄列方向，45度，135度方向上被控制的情況4. void tryToPut(int ); /求全部解的過程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) /如果最后一個皇后被放置完畢，將當(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. 解題思路三這個題目也可以不用仿真棋盤來模擬已放置棋子的控制區(qū)域，而只用一個有8個元素的數(shù)組記錄已經(jīng)擺放的棋子擺在什么位置，當(dāng)要放置一個新的棋子時，只需要判斷它與已經(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個皇后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來源（/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來源（/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