算法分析与设计试卷1.doc

密 封线内不要答题姓 名 学 号 班 级 河南城建学院20142015学年第一学期期末考试（试）算法分析与设计试题（A卷） 供 计算机科学与技术 专业 0814111/2 班使用 2014年12月题 号一二三四五六总 分得 分阅卷人本套试卷共 页考试说明及要求：在F:考试文件下建立文件，以学号和姓名的命名方式如：0814131_张三。然后在“0814131_张三”文件夹下建立各个题目的文件夹01_5个数求最值，各个题目分别保存在各个文件夹下。一、5个数求最值（10分）描述：设计一个从5个整数中取最小数和最大数的程序输入：输入只有一组测试数据，为五个不大于1万的正整数输出：输出两个数，第一个为这五个数中的最小值，第二个为这五个数中的最大值，两个数字以空格格开。样例输入：1 2 3 4 5样例输出：1 5二、A+B Problem（V）（8分）问题的描述：读入两个小于100的正整数A和B,计算A+B.需要注意的是:A和B的每一位数字由对应的英文单词给出.输入：测试输入包含若干测试用例,每个测试用例占一行,格式为A + B =,相邻两字符串有一个空格间隔.当A和B同时为0时输入结束,相应的结果不要输出. 输出：对每个测试用例输出1行,即A+B的值.输入样例：one + two =three four + five six =zero seven + eight nine =zero + zero =输出样例39096三、全排列问题（15分）设A=a1,a2,an是要进行排列的n个元素的集合。n=1 输出：a1n=2 输出：a1a2 a2a1n=3 输出：a3a1a2 a3a2a1 a1a2a3 a1a3a2 a2a1a3 a2a3a1基本要求： 输入：输入n个元素； 输出：n个元素的全排列方式总数和全排列的排列结果。四、king 选 太子（8分）描述:啊，从前有一个国家。此国兵强马壮，但是国王却身体不好。于是就想挑一位太子出来；但是问题来了，国王不知道他有几个孩子（这国王糊涂吧！），他只知道他的孩子的年龄都是不同的。同时这个国王也有要求，他认为孩子年龄太大的过于迂腐，而年龄太小又不成熟，（这孩子挑的也太难了吧），他就想要年龄在他们孩子之间是最中间的（如果孩子的个数为偶数，那么选中间的两个皇子中年龄较大的那个）。输入:第一行有一个整数T，代表有T组数据（T=10）第二行有一个整数n（0n=15），紧随着有n个数代表有n个皇子（年龄都是整数）输出:每行输出这串数字的太子的年龄样例输入231 2 341 2 3 4 样例输出23五、最大子段和（动态规划） (20分)描述 ：给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。例子：0 -2 -7 09 2 -6 2密 封线内不要答题姓 名 学 号 班 级 -4 1 -4 1-1 8 0 -2其最大子矩阵为： 9 2-4 1-1 8其元素总和为15。输入：第一行输入一个整数n（0n=100）,表示有n组测试数据；每组测试数据：第一行有两个的整数r，c（0r,c=100），r、c分别代表矩阵的行和列；随后有r行，每行有c个整数；输出：输出矩阵的最大子矩阵的元素之和。样例输入：14 40 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 样例输出： 15六、背包问题（采用贪心算法）（25分）描述：现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1=v,w=10）；如果给你一个背包它能容纳的重量为m（10=m=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。输入：第一行输入一个正整数n（1=n=5）,表示有n组测试数据；随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1=s=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。输出：输出每组测试数据中背包内的物品的价值和，每次输出占一行。样例输入13 155 102 83 9样例输出65 1. /*2. *背包贪心法3. *4. *author*5. *6. */7. publicclassGreedy8. publicstaticvoidmain(Stringargs)9. Scannerin=newScanner(System.in);10. System.out.println(Pleaseenterthenumberofobjects(请输入物品的数量：):);11. intn=in.nextInt();12. intw=newintn;/物品重量数组13. intv=newintn;/物品价钱数组14. System.out15. .println(Now,pleaseentertheweightoftheseobjects(现在请输入这些物品的重量：);16. for(inti=0;in;i+)17. wi=in.nextInt();18. 19. System.out20. .println(Now,pleaseenterthevalueoftheseobjects(现在请输入这些物品的价值：);21. for(inti=0;in;i+)22. vi=in.nextInt();23. 24. System.out25. .println(Now,pleaseenterthecapacityofthepack(现在请输入背包的容量：);26. intc=in.nextInt();27. /*28. *按单位重量价值ri=vi/wi降序排列29. *30. *ps:排序用到了选择排序，详情请查看选择排序31. */32. doublestartTime=System.currentTimeMillis();33. doubler=newdoublen;34. intindex=newintn;35. for(inti=0;in;i+)36. ri=(double)vi/(double)wi;37. indexi=i;38. 39. doubletemp=0;40. for(inti=0;in-1;i+)41. for(intj=i+1;jn;j+)42. if(rirj)43. temp=ri;44. ri=rj;45. rj=temp;46. intx=indexi;47. indexi=indexj;48. indexj=x;49. 50. 51. 52. /*53. *排序后的重量和价值分别存到w1和v1中54. */55. intw1=newintn;56. intv1=newintn;57. for(inti=0;in;i+)58. w1i=windexi;59. v1i=vindexi;60. 61. /*62. *初始化解向量xn63. */64. intx=newintn;65. for(inti=0;in;i+)66. xi=0;67. 68. /*69. *求解并打印解向量70. */71. for(inti=0;in;i+)72. if(w1ic)73. xi=1;74. c=c-w1i;75. 76. 77. System.out78. .println(Thesolutionvectoris(解向量是：)+Arrays.toString(x);79. /*80. *根据解向量求出背包中存放物品的最大价值并打印81. */82. intmaxValue=0;83. for(inti=0;in;i+)84. if(xi=1)85. maxValue+=v1i;86. 87. doubleendTime=System.currentTimeMillis();88. System.out89. .println(Now,thelargestvaluesofobjectsinthepackis(背包中物品的最大价值为：)90. +maxValue);91. System.out.println(BasicStatementstake(基本语句用时)92. +(endTime-startTime)+milliseconds!);93. 94. 背包问题 背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中以使背包最后达到指定的总重量。不需要把所有的选项都放入背包中。 举例来说，假设想要背包精确地承重20磅，并且有5个可以选择 放入的数据项，它们的重量依次为11磅、8磅、7磅、6磅和5磅。对于选择放入的数据项数量不大时，人类很善于通过观察就可以解决这个问题。于是大概可以计算出只有8磅、7磅和5磅的数据项加在一起和为20磅。 如果想要计算机来解决这个问题，就需要给计算 机更详细的指令。算法如下：1如果在这个过程中的任何时刻，选择的数据项的总和符合目标重量，工作就完成了。2从选择第一个数据项开始。剩余的数据项的加和必须符合背包的目标重量减去第一个数据 项的重量；这是一个新的目标重量。3逐个地试每种剩余数据顶组合的可能性。但是，注意并不需要去试所有的组合，因为只要 数据顶朗和大于目标重量的时候，就停止添加数据项。4如果设有组合合适的话，放弃第个数据项，并且从第二个数据项开始再重复一边整个 过程。5继续从第三个数据项开始，如此下去直到你已经试过所有的组合，这时知道没有解决答案。java view plaincopyprint?1. publicclassBeibao2. staticinta=newint5;/背包重量3. staticintb=newint5;/结果数组4. staticintflag=0;/下一个候选项5. staticintbound=20;/总重量6. staticinttotle=0;/每次选择后的总重量7. /*8. *背包9. *10. *parami11. *元素坐标12. *paramleftbound13. *目标重量14. *paramt15. */16. publicstaticvoidinserttry(inti,intleftbound,intt)17. if(i5&leftbound=totle)18. if(aileftbound)/当前的所选的数大于已选数的总和，不符合条件，选择后的重量数减掉当前所选数，递归25. totle=totle-ai;26. i+;27. inserttry(i,leftbound,t);28. else/当前所选的数等于已选数的总和29. bt=ai;30. return;31. 32. else/数组中没有符合当前条件的元素，将前一个数值移除，递归33. leftbound=leftbound+b-t;34. for(intf=0;f5;f+)35. if(af=bt)36. flag=+f;37. break;38. 39. 40. bt=0;41. totle=0;42. for(intm=flag;m5;m+)43. totle+=am;44. 45. inserttry(flag,leftbound,t);46. 47. return;48. 49. publicstati