第六课程设计大赛问题与答案.doc

一、鸡兔同笼问题描述一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物输入数据第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (a 32768)。输出要求n行，每行输出对应一个输入。输出是两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用空格分开。如果没有满足要求的情况出现，则输出2个0。 输入样例2320输出样例0 05 10解题思路这个问题可以描述成任给一个整数N，如果N是奇数，输出0 0，否则如果N是4的倍数，输出N / 4 N / 2，如果N不是4的倍数，输出N/4+1 N/2。这是一个一般的计算题，只要实现相应的判断和输出代码就可以了。题目中说明了输入整数在一个比较小的范围内，所以只需要考虑整数运算就可以了。参考程序1. #include 2. void main( )3. 4. int nCases, i, nFeet; /nCases 表示输入测试数据的组数，nFeet表示输入的脚数。5. scanf(%d, &nCases);6. for(i = 0; i nCases; i+)7. scanf(%d, &nFeet);8. if(nFeet %2 != 0) / 如果有奇数只脚，则输入不正确，9. / 因为不论2只还是4只，都是偶数10. printf(0 0n);11. else if (nFeet%4 != 0) /若要动物数目最少，使动物尽量有4只脚12. /若要动物数目最多，使动物尽量有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年是闰年。输入数据一行，仅含一个整数a(0 a 3000)。输出要求一行，如果公元a年是闰年输出Y，否则输出N。输入样例2006输出样例N解题思路这个题目主要考察闰年的定义，使用基本的逻辑判断语句就可以了。考虑到输入的范围在0到3000之间，所以判断闰年时不必考虑能被3200整除的年份不是闰年的判定条件。程序应该包括三个基本的步骤：正确读入要判定的年份a；判定a是否为闰年；给出正确的输出。其中，判断输入年份是否为闰年根据个人的思考习惯可以有不同的判定顺序。参考解法一 分段排除：如果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个，。现在给出第一天的日期和细菌数目，要你写程序求出到某一天的时候，细菌的数目。输入数据第一行有一个整数n，表示测试数据的数目。其后n行每行有5个整数，整数之间用一个空格隔开。第一个数表示第一天的月份，第二个数表示第一天的日期，第三个数表示第一天细菌的数目，第四个数表示要求的那一天的月份，第五个数表示要求的那一天的日期。已知第一天和要求的一天在同一年并且该年不是闰年，要求的一天一定在第一天之后。数据保证要求的一天的细菌数目在整数范围内。输出要求对于每一组测试数据，输出一行，该行包含一个整数，为要求的一天的细菌数。输入样例21 1 1 1 22 28 10 3 2输出样例240解题思路这题实际上是求给定的两天之间间隔的天数n，第一天的细菌数乘以2的n次方就是题目的答案。每个月的天数因为不很规则，如果在程序中用规则描述会比较麻烦，所以可以使用一个数组将每个月的天数存起来。整个计算过程可以描述如下：读入测试样例数n；做n次：1. 读入两个日期及第一天的细菌数； 2. 将两个日期转换为当年的第几天； 3得到两个天数的差，即它们中间间隔的天数m； 4用第一天的细菌数乘以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. 四、八皇后问题 问题描述会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。 对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2.b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。 输入数据第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1 = b = 92)输出要求n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串输入样例2192输出样例1586372484136275解题思路一因为要求出92种不同摆放方法中的任意一种，所以我们不妨把92种不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子，就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。当完成一种摆放时，就要尝试下一种。若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试；对于第一个棋子的每一个位置，将第二个棋子从可行的位置从小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。首先，我们有一个8*8的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有92行每行8个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7皇后问题，用与8皇后同样的方法可以获得问题的解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1到第8个位置，顺序地尝试将棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。参考程序一1. #include 2. #include 3.4. int queenPlaces928; /存放92种皇后棋子的摆放方法5. int count = 0;6. int board88; /仿真棋盘7. void putQueen(int ithQueen); /递归函数，每次摆好一个棋子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个棋子开始摆放，运行的结果是将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个皇后摆放方法后覆盖此时的设置40. for(k = count; k 92; k+)41. queenPlaceskithQueen = i + 1;42. /设置控制范围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. 解题思路二上面的方法用一个二维数组来记录棋盘被已经放置的棋子的控制情况，每次有新的棋子放置时用了枚举法来判断它控制的范围。还可以用三个一维数组来分别记录每一列，每个45度的斜线和每个135度的斜线上是否已经被已放置的棋子控制，这样每次有新的棋子放置时，不必再搜索它的控制范围，可以直接通过三个一维数组判断它是否与已经放置的棋子冲突，在不冲突的情况下，也可以通过分别设置三个一维数组的相应的值，来记录新棋子的控制范围。参考程序二1. #include 2. int record929, mark9, count = 0; /record记录全部解，mark记录当前解；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) /如果最后一个皇后被放置完毕，将当前解复制到全部解中27. for(int k = 1; k 9; k +) 28. recordcountk = markk;29. count +;30. 31. for(int j=1; j=8; j+) 逐一尝试将当前皇后放置在不同列上32. if(rangej & line1 i + j & line2i - j + 9) /如果与前面的不冲突，33. /则把当前皇后放置在当前位置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. 解题思路三这个题目也可以不用仿真棋盘来模拟已放置棋子的控制区域，而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置，当要放置一个新的棋子时，只需要判断它与已经放置的棋子之间是否冲突就行了。参考程序三1. #include 2. int ans928, n, b, i, j, num, hang8;3. void queen(int i)4. int j, k;5. if(i = 8) /一组新的解产生了6. for(j = 0; j 8; j+) ansnumj = hangj + 1;7. num+;8. return;9. 10. for (j=0; j8; j+) /将当前皇后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