《ACM算法与程序设计》期末问题集

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

11、之间的整数去乘它时, 会得到一个将原来的数首尾相接循环移动若干数字再在某处断开而得到的数字。也就是说，如果把原来的数字和新的数字都首尾相接，他们得到的环是相同的。只是两个数的起始数字不一定相同。例如，数字 142857 是循环数，因为: 142857 *1 = 142857 142857 *2 = 285714 142857 *3 = 428571 142857 *4 = 571428 142857 *5 = 714285 142857 *6 = 857142 Input写一个程序确定给定的数是否是循环数。输入包括多个长度为 2 位到 60 位的整数。(注意，先导的0也是合理的输入不应该被忽略

12、,例如 01是 2 位数，1 是 1 位数。) Output对于每一个输入的整数，输出一行表明它是否是循环数。 Sample Input142857142856142858010588235294117647Sample Output142857 is cyclic142856 is not cyclic142858 is not cyclic01 is not cyclic0588235294117647 is cyclic四、高精度计算1、孙子问题 http:/ 为解决这个问题民间流传了如下歌诀：“三人同行七十稀，五树梅花廿一枝，七子团员正半月，除百零五便得知。” 把上面的问题说得明白一点

13、就是：有一个正整数N，除以3的余数是2，除以5的余数是3，除以7的余数是2，要求这个数。 民间给出的解法是：把N除以3的余数乘以70，把N除以5的余数乘以21，把N除以7的余数乘以15，把这三个结果加起来，最后把得到的结果除以105得到的就是答案。 其实在民间的解法中不除以105得到的也是一个符合题意的答案，而且民间的解法对于已知“除以3的余数，除以5的余数和除以7的余数” 的问题都能得到一个符合要求的答案。比如对于上面的问题，得到的结果是2 * 70 + 3 * 21 + 2 * 15 = 233，这个结果也能满足除以3的余数是2，除以5的余数是3，除以7的余数是2。如果已知的问题是“除以3

14、的余数是1，除以5的余数是4，除以7的余数是4”，民间解法得到的结果1 * 70 + 4 * 21 + 4 * 15 = 214，这个结果也满足除以3的余数是1，除以5的余数是4，除以7的余数是4。 把这个问题推广到更普遍的情况：对于给定的正整数a1, a2, . an，是否存在正整数b1, b2, . bn，使得对于任意的一个正整数N，如果用N除以a1的余数是p1，用N除以a2的余数是p2用N除以an的余数是pn，那么M = p1 * b1 + p2 * b2 + . + pn * bn能满足M除以a1的余数也是p1，M除以a2的余数也是p2M除以an的余数也是pn。 Input输入包括多组

15、测试数据，每组数据包括一行。在每组数据中，首先给出ai的个数n (1 = n = 10)，然后给出n个不大于50的正整数a1, a2, . an。最后一组测试数据中n = 0，表示输入的结束，这组数据不用处理。Output对于每一组测试数据，输出一行，如果存在正整数b1, b2, . bn满足题意，则输出这n个正整数（数的长度不要超过50位）如果有多组答案，输出任意一组即可，相邻的正整数之间用一个空格隔开；否则，输出“NO”。Sample Input3 3 5 70Sample Output70 21 15五、枚举1、数字方格 http:/ = a1, a2, a3 = n，而且a1 + a2

16、是2的倍数，a2 + a3是3的倍数， a1 + a2 + a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1 + a2 + a3最大。 Input输入的第一行是一个数t，表示测试数据的数目。接下来的t行，每行给出一个n (0 = n = 100)的值。Output对于每一个n的值，输出a1 + a2 + a3的最大值。Sample Input203Sample Output052、画家问题 http:/ j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色

17、都变成黄色。 Input第一行是个整数t(1t 20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n (1n 15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。Output每个案例输出一行。如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。Sample Input2 3 yyy yyy yyy 5wwwww wwwww wwwww wwwww wwwww Sample Output0 15 3、拨钟问题 http:/ 现在需要用最少的移动

18、，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。 移动 影响的时钟 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI (图 2) Input从标准输入设备读入9个整数，表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。Output输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果。Sample Input3 3 0 2 2 2 2 1 2 Sample Output4 5 8 9 六、递归与动态规

19、划1、算24 http:/ 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。 比如，对于5，5，5，1，我们知道5 * (5 1 / 5) = 24，因此可以得到24。又比如，对于1，1，4，2，我们怎么都不能得到24。 Input输入数据包括多行，每行给出一组测试数据，包括4个小于10个正整数。最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。Output对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。Sample Input5 5 5 11 1 4 20 0 0 0Sample OutputYESNO2、滑雪 http:/ 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 516 17