《《ACM算法与程序设计》期末问题集.doc》由会员分享，可在线阅读，更多相关《《ACM算法与程序设计》期末问题集.doc（13页珍藏版）》请在金锄头文库上搜索。
1、一、综合处理题1、两倍 - http:/ 比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。 Input输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。Output对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。Sample Input1 4 3 2 9 7 18 22 02 4 8 10 07 5 11 13 1 3 0-1
2、Sample Output3202、谁拿了最多奖学金 - http:/ 1) 院士奖学金，每人8000元，期末平均成绩高于80分（80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（85），并且班级评议成绩高于80分（80）的学生均可获得； 3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（90）的学生均可获得； 4) 西部奖学金，每人1000元，期末平均成绩高于85分（85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（80）的学生干部均可获得； 只要符合条件就可以得奖，每项奖学金
3、的获奖人数没有限制，每名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87分，班级评议成绩82分，同时他还是一位学生干部，那么他可以同时获得五四奖学金和班级贡献奖，奖金总数是4850元。 现在给出若干学生的相关数据，请计算哪些同学获得的奖金总数最高（假设总有同学能满足获得奖学金的条件）。 Input输入的第一行是一个整数N（1 = N = 100），表示学生的总数。接下来的N行每行是一位学生的数据，从左向右依次是姓名，期末平均成绩，班级评议成绩，是否是学生干部，是否是西部省份学生，以及发表的论文数。姓名是由大小写英文字母组成的长度不超过20的字符串（不含空格）；期末平均成绩和班级评议成
4、绩都是0到100之间的整数（包括0和100）；是否是学生干部和是否是西部省份学生分别用一个字符表示，Y表示是，N表示不是；发表的论文数是0到10的整数（包括0和10）。每两个相邻数据项之间用一个空格分隔。Output输出包括三行，第一行是获得最多奖金的学生的姓名，第二行是这名学生获得的奖金总数。如果有两位或两位以上的学生获得的奖金最多，输出他们之中在输入文件中出现最早的学生的姓名。第三行是这N个学生获得的奖学金的总数。Sample Input4YaoLin 87 82 Y N 0ChenRuiyi 88 78 N Y 1LiXin 92 88 N N 0ZhangQin 83 87 Y N 1
5、Sample OutputChenRuiyi900028700二、字符串处理1、古代密码 - http:/ 替换方法是将所有出现的字符替换成其它的字符。有些字符会碰巧替换成它自己。例如：替换规则可以是将A 到 Y替换成它的下一个字符，将Z替换成 A，如果原词是 VICTORIOUS 则它变成 WJDUPSJPVT。 排列方法改变原来单词中字母的顺序。例如：将顺序 应用到 VICTORIOUS 上，则得到IVOTCIRSUO。 人们很快意识到单独应用替换方法或排列方法，加密是很不保险的。但是如果结合这两种方法，在当时就可以得到非常可靠的加密方法。所以，很多重要信息先使用替换方法加密，再将加密的结
6、果用排列的方法加密。用两中方法结合就可以将VICTORIOUS 加密成JWPUDJSTVP。 考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义，所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码，现在他们想检查解读的是否正确。他们需要一个计算机程序来验证她，你的任务就是写这个验证程序。 Input输入有两行。第一行是石台上的文字。文字中没有空格，并且只有大写英文字母。第二行是被解读出来的加密前的文字。第二行也是由大写英文字母构成的。 两行字符数目的长度都不超过计划100。Output如果第二行经过某种加密方法后可以产生第一行的信息，输出 YES，否则输出N
7、O。Sample InputJWPUDJSTVPVICTORIOUSSample OutputYES2、词典 - http:/ Sample Inputdog ogdaycat atcaypig igpayfroot ootfrayloops oopslayatcayittenkayoopslaySample Outputcatehloops3、最短前缀 - http:/ carbon的字串是: c, ca, car, carb, carbo, 和 carbon。注意到这里我们不认为空串是字串, 但是每个非空串是它自身的字串. 我们现在希望能用前缀来缩略的表示单词。例如, carbohydra
8、te 通常用carb来缩略表示. 现在给你一组单词, 要求你找到唯一标识每个单词的最短前缀 在下面的例子中，carbohydrate 能被缩略成carboh, 但是不能被缩略成carbo (或其余更短的前缀) 因为已经有一个单词用carbo开始 一个精确匹配会覆盖一个前缀匹配，例如，前缀car精确匹配单词car. 因此 car 是 car的缩略语是没有二义性的 , “car”不会被当成carriage或者任何在列表中以car开始的单词. Input输入包括至少2行，至多1000行. 每行包括一个以小写字母组成的单词，单词长度至少是1，至多是20.Output输出的行数与输入的行数相同。每行输出
9、由相应行输入的单词开始，后面跟着一个空格接下来是相应单词的没有二义性的最短前缀标识符。Sample InputcarbohydratecartcarburetorcaramelcariboucarboniccartilagecarboncarriagecartoncarcarbonateSample Outputcarbohydrate carbohcart cartcarburetor carbucaramel caracaribou caricarbonic carbonicartilage carticarbon carboncarriage carrcarton cartocar ca
10、rcarbonate carbona三、模拟1、数根 http:/ 比如，对于24来说，把2和4相加得到6，由于6是一位数，因此6是24的数根。再比如39，把3和9加起来得到12，由于12不是一位数，因此还得把1和2加起来，最后得到3，这是一个一位数，因此3是39的数根。Input输入包括一些正整数(小于101000)，每个一行。输入的最后一行是0，表示输入的结束，这一行不用处理。Output对每个正整数，输出它的数根。每个结果占据一行。Sample Input24390Sample Output632、循环数 http:/ 位的一个整数是循环数（cyclic）的条件是：当用一个 1 到 n 之间的整数去乘它时, 会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说，如果把原来的数字和新的数字都首尾相接，他们得到的环是相同的。只是两个数的起始数字不一定相同。例如，数字 142857 是循环数，因为: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571
