北京理工大学2013级C程序设计非信息类答案part2.doc

北京理工大学2013级C程序设计非信息类答案part 249. 【小学递归】杀鸡用牛刀要用递归啊！成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55背景： 哈哈！我们终于学了递归了，现在大家一定感到非常有意思吧，那个典型的“汉诺塔”问题，一个非常短的程序居然可以完成如此复杂的工作，真是神奇啊！来吧，让我们也动手编写一个递归程序，当然，我们要编写的不可能太复杂。功能：求整数 n 到 m 区间的累加和，其中n=m;i-)returni+sum(m,i-1); 3. #include 4. intmain()intm,n,s=0;scanf(%d%d,&m,&n);s=sum(m,n); 5. printf(Thesumfrom%dto%dis%d.n,m,n,s);return0;50. 【中学】求最大公约数递归成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55请使用递归算法计算正整数n和m的最大公约数GCD(n,m)。 = m 当 m=n 且 n mod m =0GCD(N,M) = GCD(m,n) 当nm时 = GCD(m, n mod m) 其他输入： n和m 输出： n和m的最大公约数测试输入期待的输出时间限制内存限制额外进程测试用例 11. 24481. 241秒64M0测试用例 21. 13151. 11秒64M01. #include 2. intf(intx,inty) 3. ints,t;t=x%y; 4. if(t=0)s=y;elses=f(y,t); 5. returns; 6. intmain() 7. intm,n;scanf(%d%d,&m,&n); 8. printf(%dn,f(m,n);return0;51. 【数列递归】求序列之和递归成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55请使用递归算法求序列1 + 1/2 - 1/3 + 1/4-1/5 .的前n项之和。输入：n 输出：序列的前n项和（精确到小数点之后第6位）测试输入期待的输出时间限制内存限制额外进程测试用例 11. 11. 11秒64M0测试用例 21. 21. 1.5000001秒64M0测试用例 31. 31. 1.1666671秒64M01. #include 2. floatsum(intn) 3. floats;if(n=1)s=1.0; 4. elseif(n%2=0)s=sum(n-1)+1.0/n; 5. elses=sum(n-1)-1.0/n;returns; 6. intmain() 7. intn;floats;scanf(%d,&n); 8. if(n=1)printf(1n); 9. elses=sum(n);printf(%.6fn,s);52. 【大学】函数递归*成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55编写一个函数，使用递归算法求满足下述定义的整数序列的第n项。1当 n = 0 且 n 4 且n为偶数 时f(n-2) + f(n-4)当 n 4 且n为奇数 时-1其他函数原型如下：int findf(int n);参数说明：n 项数；返回值是第n项值。例如输入：10，输出：8预设代码前置代码1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/2. #include 3. intmain() 4. intn,s,findf(int); 5. scanf(%d,&n); 6. s=findf(n); 7. printf(%dn,s); 8. return0; 9. 10. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/测试输入期待的输出时间限制内存限制额外进程测试用例 11. 101. 81秒64M01. intfindf(intn) 2. if(n=0&n=4)return1;if(n4&n%2=0)returnfindf(n-1)+findf(n-3); 4. if(n4&n%2=1)returnfindf(n-2)+findf(n-4);53.【大学递归】求解平方根成绩5开启时间2014年05月10日 星期六 11:35折扣0.8折扣时间2014年05月24日 星期六 11:35允许迟交否关闭时间2014年06月1日 星期日 11:35小明上了大学，学习了用求解平方根的迭代公式。 其中：p 为 x 的近似平方根，e 是结果允许的误差。 输入：x, e 输出：p 保留小数点后 8 位。1. #include2. #include3. floatf(floatx,floatp,floate)4. if(fabs(p*p-x)e)returnp;elsereturnf(x,(p+x/p)/2,e);5. intmain()floatp,e,x;scanf(%f%f,&x,&e);p=f(x,x,e);printf(%.8fn,p);return0;H12：安全的密码（选做）成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55随着电子设备的广泛运用，密码也渐渐融入每个人的生活。保护好密码，不仅关系到个人隐私，更关系到个人的财产和安全。一个安全的密码，最好由大小写字母、数字或符号组成。包含越多种类的字符，其安全性就越高。同时密码还需要有一定的长度，通常至少要由六个以上的字符组成。并不是每个人都喜欢这样复杂的密码，很多人在设置密码的时候，喜欢使用自己的名字或者生日，但这是很大的安全隐患。任务 林晓炜正在设计一个网络交易系统，为了保证用户的密码安全，他需要一个程序，判断用户自己设置的密码是否安全，如果不安全，则给出提示。现在他向你求助，请你帮忙设计一个程序来解决这个问题。应当按照以下的规则来判断密码是否安全：如果密码长度小于 6 位，则不安全；如果组成密码的字符只有一类，则不安全；如果组成密码的字符有两类，则为中度安全；如果组成密码的字符有三类或以上，则为安全通常，可以认为数字、大写字母、小写字母和其它符号为四类不同的字符。输入 输入的第一行是一个整数 N，表明后面有多少组密码。随后的 N 行输入包括 N 个密码，每个密码的长度均小于 20 个字符。输出 针对每一个密码判断并输出它是否安全。对于不安全的密码输出 Not Safe，对于中度安全的密码输出 Medium Safe，对于安全的密码输出 Safe输入样例41234abcdefABC1231#c3Gh输出样例Not SafeNot SafeMediumSafe Safe测试输入期待的输出时间限制内存限制额外进程测试用例 11. 102. abcDEF3. ABC4. qw5. 6. ABCDEFGHIJKLMNOPQRST7. 123456789012345678908. 1aB9. 1B10. aX11. qwe123%&ABC 1. MediumSafe2. NotSafe3. NotSafe4. NotSafe5. NotSafe6. NotSafe7. Safe8. NotSafe9. Safe10. Safe1秒64M01. #include 2. #include 3. intmain(void) 4. intn,i,j,x,m,b4;chara100;scanf(%d,&n); 5. for(i=1;i=n;i+)gets(a);if(i=1)gets(a);x=strlen(a); 6. if(x6)printf(NotSafen);continue; 7. b0=0;b1=0;b2=0;b3=0;for(j=0;j=x-1;j+) 8. if(48=aj&aj=57)b0=1; 9. elseif(65=aj&aj=91)b1=1; 10. elseif(97=aj&aj=123)b2=1;11. elseb3=1; 12. if(a0+a1+a2+a3=4)break;m=b0+b1+b2+b3; 13. switch(m) 14. case1:printf(NotSafen);break;case2:printf(MediumSafen);break; 15. case3:printf(Safen);break;case4:printf(Safen);return0;H13：编码问题（选作）成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55 设有一个整形数组 A0.N-1；存放的元素为 0N-1 (1N=10)之间的整数，且 AiAj（ij）。例如，当N=6时，有：A=（4，3，0，5，1，2）。此时，数组A的编码定义如下：A0编码为0；Ai编码为：在A0，A1，Ai-1中比Ai的值小的个数 （i=1，2，N-1） 例如上面数组 A的编码为：B=（0，0，0，3，1，2）若给出数组A，则可求出其编码。同理，若给出数组A的编码，可求出A中的原数据。输入：推导方向（取值为1或2，如为1，则表示根据数组求数组编码；如为2，则表示根据编码反求数组）数组个数 数组或数组编码元素输出：数组编码、或数组本身（元素之间以空格分隔）测试输入期待的输出时间限制内存限制额外进程测试用例 1 1. 12. 63. 4305121. 0003121秒64M0测试用例 2 1. 12. 83. 103256741. 002245641秒64M0测试用例 4 1. 22. 63. 0023131. 2045131秒64M01. #include 2. intmain()intmode,n,i,j,s,a100,b100;staticintc100; 3. scanf(%d,&mode);scanf(%d,&n); 4. for(i=0;in;i+)scanf(%d,&ai); 5. if(mode=1)for(i=1,b0=0;in;i+) 6. for(j=0,bi=0;jaj)bi+; 7. elsefor(i=n-1;i=0;i-)for(j=0,s=0;sai+1;j+) 8. if(cj=0)s+;bi=j-1;cbi=1; 9. for(i=0;in-1;i+)printf(%d,bi); 10. printf(%dn,bn-1);return0;54. 回文字符串递归（请使用递归算法实现。）成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:00 有一种特殊形式的字符串，其正反序相同，被称为“回文字符串”。例如LeveL就是一个回文字符串。输入：字符串 输出： Yes或者No说明：如输出Yes，说明输入的字符串是一个回文字符串。输出No，说明输入的字符串不是一个回文字符串测试输入期待的输出时间限制内存限制额外进程测试用例 11. LeveL1. Yes1秒64M0测试用例 101. 1. Yes1秒64M01. #include 2. #include 3. intf(charx,chary)intp=x=y;returnp; 4. intmain()chara500;inti,j=1,k;5. fgets(a,500,stdin);k=strlen(a)-1;if(k=0)printf(Yesn); 6. elsefor(i=0;i=k/2;i+)j*=f(ai,ak-1-i); 7. if(j=1)printf(Yesn);elseprintf(Non);55. 子串反向递归成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:00请编写一个递归函数 reverse(char str, int start, int end ) ，该函数的功能是将串 str 中下标从 start 开始到 end 结束的字符颠倒顺序。假设 start 和 end 都在合理的取值范围。例如：执行前：str=0123456；start=1 ；end=4 执行后：strr=0432156要求在该函数中不使用新的数组，没有循环。注意：只需要编写递归函数 reverse，系统中已经设置好了main函数。预设代码前置代码1. /*PRESETCODEBEGIN-NEVERTOUCHCODEBELOW*/2. #include 3. #include 4. voidreverse(); 5. intmain() 6. charstr100; 7. intstart,end; 8. gets(str); 9. scanf(%d%d,&start,&end); 10. reverse(str,start,end); 11. printf(%sn,str); 12. return0; 13. 14. /*PRESETCODEEND-NEVERTOUCHCODEABOVE*/测试输入期待的输出时间限制内存限制额外进程测试用例 1 1. 01234562. 141. 04321561秒64M0测试用例 6 1. 01234562. 6101. 01234561秒64M0测试用例 7 1. 01234562. 0101. 65432101秒64M01. #include 2. voidreverse(charstr,intstart,intend) 3. chart;if(end=strlen(str)reverse(str,start,end-1); 4. elseif(startend)t=strstart;strstart=strend;strend=t; 5. reverse(str,start+1,end-1);56. 【字符】单词排序成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交是关闭时间2014年06月1日 星期日 23:55输入 5 个单词，将它们按从大到小的顺序排列后输出。 输入： 5个单词 输出：排序后的顺序测试输入期待的输出时间限制内存限制额外进程测试用例 1 1. BASIC2. C+3. Pascal4. C5. Fortran 1. Pascal2. Fortran3. C+4. C5. BASIC1秒64M01. #include 2. #include 3. intmain()charch526,c26;inti,j,k; 4. for(i=0;i5;i+)gets(chi); 5. for(i=0;i4;i+)k=i;for(j=i+1;j5;j+) 6. if(strcmp(chk,chj)0)k=j; 7. if(k!=i)strcpy(c,chi);strcpy(chi,chk);strcpy(chk,c); 8. for(i=0;i5;i+)puts(chi);57. 【日期】车辆限行成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:552012年4月1日，北京是人民政府根据中华人民共和国道路交通安全法和北京市实施中华人民共和国大气污染防治法办法有关规定，自2012年4月11日起，继续对机动车实施按车牌尾号工作日高峰时段 区域限行交通管理措施。根据规定，按车牌尾号限行的机动车车牌尾号分为五组，每13周轮换一次限行日，分别为：(1) 自2012年4月9日至2012年7月7日，星期一至星期五限行机动车车牌尾号分别为：3和8、4和9、5和0、1和6、2和7(含临时号牌，机动车车牌尾号为英文字母的按0号管理，下同)；(2) 自2012年7月8日至2012年10月6日，星期一至星期五限行机动车车牌尾号分别为：2和7、3和8、4和9、5和0、1和6；(3) 自2012年10月7日至2013年1月5日，星期一至星期五限行机动车车牌尾号分别为：1和6、2和7、3和8、4和9、5和0；(4) 自2013年1月6日至2013年4月10日，星期一至星期五限行机动车车牌尾号分别为：5和0、1和6、2和7、3和8、4和9。现给出 2012 年 4 月 9 日之后的任意日期，如果不考虑国家统一的公假，只考虑日期一个因素，请计算指定日期要限行的车牌尾号。（政府的公告确实有点意思，在时间衔接上和限号安排上公告（/GB/14748/17574443.html）与公告（/gzdt/2013-04/02/content_2367908.htm）之间有重叠，显然，后面的公告是覆盖前面的公告的，我们计算的时候，只能是“理论”上的事情，咱严格按照从 2012年4月9日 星期一 开始，每 13 周进行一次轮换计算就可以了。）测试输入期待的输出时间限制内存限制额外进程测试用例 11. 2012791. 2and7.无限制64M0测试用例 21. 20127121. 5and0.无限制64M0测试用例 31. 20127141. Free.无限制64M0测试用例 51. 20134111. 2and7.无限制64M0测试用例 61. 2014441. 5and0.无限制64M0测试用例 91. 20143311. 1and6.无限制64M01. #include 2. intleap_year(int);intyear_days(int);intdays(int,int,int); 3. intleap_year(intyear)return(year%4=0&year%100!=0)|year%400=0)?1:0; 4. intyear_days(intyear)returnleap_year(year)?366:365; 5. intdays(intyear,intmonth,intday) 6. intmonths13=0,31,28,31,30,31,30,31,31,30,31,30,31,i; 7. if(leap_year(year)&month2)day+; 8. for(i=1;imonth;i+)day+=monthsi; 9. returnday; 10. intmain()inta,b,c,i,d=0,m;scanf(%d%d%d,&a,&b,&c); 11. for(i=2012;ia;i+)d+=year_days(i); 12. d+=days(a,b,c)-days(2012,4,9);m=(d/91)%5; 13. switch(m) 14. case0:switch(d%91)%7) 15. case0:printf(3and8.n);break; 16. case1:printf(4and9.n);break; 17. case2:printf(5and0.n);break; 18. case3:printf(1and6.n);break; 19. case4:printf(2and7.n);break; 20. case5:printf(Free.n);break; 21. case6:printf(Free.n);break;break; 22. case1:switch(d%91)%7) 23. case0:printf(2and7.n);break; 24. case1:printf(3and8.n);break; 25. case2:printf(4and9.n);break; 26. case3:printf(5and0.n);break; 27. case4:printf(1and6.n);break; 28. case5:printf(Free.n);break; 29. case6:printf(Free.n);break;break; 30. case2:switch(d%91)%7) 31. case0:printf(1and6.n);break; 32. case1:printf(2and7.n);break; 33. case2:printf(3and8.n);break; 34. case3:printf(4and9.n);break; 35. case4:printf(5and0.n);break; 36. case5:printf(Free.n);break; 37. case6:printf(Free.n);break;break; 38. case3:switch(d%91)%7) 39. case0:printf(5and0.n);break; 40. case1:printf(1and6.n);break; 41. case2:printf(2and7.n);break; 42. case3:printf(3and8.n);break; 43. case4:printf(4and9.n);break; 44. case5:printf(Free.n);break; 45. case6:printf(Free.n);break;break; 46. case4:switch(d%91)%7) 47. case0:printf(4and9.n);break; 48. case1:printf(5and0.n);break; 49. case2:printf(1and6.n);break; 50. case3:printf(2and7.n);break; 51. case4:printf(3and8.n);break; 52. case5:printf(Free.n);break; 53. case6:printf(Free.n);break;break; 54. return0;58. 缩写展开成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交是关闭时间2014年06月1日 星期日 23:55在保存字符串时，对出现在连续位置的若干个字符，如这些字符在ASCII表中也是连续出现，则可以将这些字符使用缩写形式进行保存，以节省保存空间。例如用A-Z表示ABCD.XYZ，1-5表示12345，c-f表示cdef。输入：包含缩写形式的字符串 输出：将缩写形式进行还原后的字符串说明：只处理大小写字母和数字，即对于形如A-9，a-C这样的缩写不进行处理测试输入期待的输出时间限制内存限制额外进程测试用例 11. 0-91. 01234567891秒64M0测试用例 21. a-z1. abcdefghijklmnopqrstuvwxyz1秒64M0测试用例 31. G-I1. GHI1秒64M0测试用例 41. ABDG-K035-9abd-h1. ABDGHIJK0356789abdefgh1秒64M0测试用例 51. 2-9a0-77cbdj1. 23456789a012345677cbdj1秒64M0测试用例 61. asasdasdasdasdA-H9871. asasdasdasdasdABCDEFGH9871秒64M0测试用例 71. A-9A-0c-80-A9-0z-aZ-A1. A-9A-0c-80-A9-0z-aZ-A1秒64M0测试用例 81. abcdefghijklmn1. abcdefghijklmn1秒64M0测试用例 9 1.asjfdhlkdsa-7812389=-ert=9-1,.;1=-=43 1.asjfdhlkdsa-7812389=-ert=9-1,.;1=-=431秒64M0测试用例 10 1.A-Z 1.ABCDEFGHIJKLMNOPQRSTUVWXYZ1秒64M0测试用例 111. 1-11. 1-11秒64M01. #include 2. #include 3. intmain()chara200;inti,j;fgets(a,200,stdin); 4. for(i=0;i=A&ai+1=Z&ai-1ai+1) 7. for(j=ai-1+1;j=a&ai+1=z&ai-1ai+1) 9. for(j=ai-1+1;j=0&ai+1=9&ai-1ai+1) 11. for(j=ai-1+1;j=ai+1-1;j+)printf(%c,j); 12. elseprintf(%c,ai);elseprintf(%c,ai);H14：洗牌（选作）成绩5开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55 假设我们有 2n 张牌，它们以 1, 2, ., n, n+1, ., 2n 编号并在开始时保持着这种顺序。一次洗牌就是将牌原来的次序变为 n+1, 1, n+2, 2, ., 2n, n，也就是将原来的前 n 张牌放到位置 2, 4, ., 2n，并且将余下的 n 张牌按照他们原来的次序放到奇数位置 1, 3, ., 2n-1。已经证明对于任何一个自然数 n，这 2n 张牌经过一定次数的洗牌就回到原来的次序。但我们不知道对于一个特定的 n，需要几次洗牌才能将牌洗回原来的次序。输入：牌张数的一半n，即初始情况下一共有2n张牌，n为int型整数 输出：将牌洗回原来的次序所需要的洗牌次数测试输入期待的输出时间限制内存限制额外进程测试用例 11. 101. 61秒64M0测试用例 21. 201. 201秒64M0测试用例 31. 31. 31秒64M0测试用例 41. 301. 601秒64M0测试用例 51. 11. 21秒64M0测试用例 61. 100001. 8121秒64M0测试用例 71. 45001. 22501秒64M01. #include 2. intmain(void) 3. intn,x,total=1;scanf(%d,&n);x=2; 4. while(x!=1)if(x=n)x=x*2; 5. elsex=2*(x-n)-1;total=total+1; 6. printf(%dn,total);return0;H15：高精度加减法（选作）成绩10开启时间2014年05月10日 星期六 14:00折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交否关闭时间2014年06月1日 星期日 23:55背景： 计算机所能完成的一个基本功能就是完成数据的计算，譬如加法、减法等等。但是在任何一种计算机上，计算中能够使用的数字都是有一定范围的，超过了范围，就没法得到精确的结果。你现在接受了一个任务，要编写一个高精度计算器的核心部分。所谓高精度计算器，就是可以计算很大很大的数据的计算器。输入：输入的第一行是一个正整数，表示下面有几组数据需要计算。之后的每一行是两个十进制的正整数和一个运算符，每个整数可以由最多 500 个数字组成。运算符可以是加号或者减号。输出：对应着输入的每一行数据，输出计算的结果，每个结果占一行。测试输入期待的输出时间限制内存限制额外进程测试用例 1 1. 22. 213914+234661233. 32862934-23481243 1. 236800372. 93816911秒64M0测试用例 2 1.32.483291674192731231+12361872368127351233.123129678463287562378-289356872648712364.999999999+1 1.17194789110054663542.1231007427760226911423.10000000001秒64M0测试用例 3 1. 112. 56789+567893. 45555+444454. 1+123455. 12345+16. 98765-987607. 12345-98768. 12345-123459. 12345-1234610. 1-5432111. 0-012. 0+0 1. 1135782. 900003. 123464. 123465. 56. 24697. 08. -19. -5432010. 011. 01秒64M01. #include 2. #include 3. voidmain() 4. charz,sign,a1010;intn,i,j,f,x,b1010,c1010; 5. voidadd(intb1010,intc1010,intf);voidsub(intb1010,intc1010,intf); 6. scanf(%d%c,&n,&z); 7. for(;n0;n-,printf(n) 8. gets(a);x=strlen(a); 9. for(i=0;i1010;i+)bi=ci=0; 10. for(i=x-1,j=0;0=ai&ai=0;i-,j+) 13. bj=ai-0;if(fj)f=j; 14. if(sign=+)add(b,c,f); 15. elsesub(b,c,f); 16. voidadd(intb1010,intc1010,intf) 17. inti,r,d1010; 18. for(i=0,r=0;i=0;i-) 23. printf(%d,di); 24. voidsub(intb1010,intc1010,intf) 25. inti,r,flag,d1010; 26. for(i=f-1,flag=1;i=0;i-) 27. if(bici)flag=1;break; 28. elseif(bici)flag=-1;break; 29. if(flag=1) 30. for(i=0,r=0;if;i+) 31. di=bi-ci+r; 32. if(di0)di=di+10;r=-1; 33. elser=0; 34. if(flag=-1) 35. printf(-); 36. for(i=0,r=0;if;i+) 37. di=ci-bi+r; 38. if(di0;i-); 42. for(;i=0;i-) 43. printf(%d,di);H16：拱猪计分（选作）成绩5开启时间2014年05月10日 星期六 14:35折扣0.8折扣时间2014年05月24日 星期六 23:55允许迟交是关闭时间2014年06月1日 星期日 23:55背景：拱猪是一种很有趣的扑克牌游戏。即使你不知道它的玩法，你也可以由它的计分方式来了解它的趣味性。 假设在此我们仅考虑四个人的拱猪牌局，本题要求你根据下面的计分规则，在牌局结束时计算四位玩家所得分数。1. 我们分别以S、H、D及C来代表黑桃，