福州大学数学与计算机科学学院11级研究生《算法设计与分析》期末试卷.pdfVIP

福州大学数学与计算机科学学院 2011 级研究生 《算法设计与分析》期末试卷 考生须知 *若试卷中试题字迹不清，考生可以在审题时举手请求解释，由考务人员加以说明。涉 及题意理解问题，则不得提问且考务人员不予解答。 *考生上机编程时应在指定目录“F:\”下工作，并请每隔5分钟存盘一次。发生机器故 障时由考务人员确认补给修复时间，且最长不超过10分钟。 *对考生答题测试有严格时间限制，若超时则该测试项判为0分。考生应注意优化算法。 *考生应严格遵守考场规则，不得违纪。 *试卷共三题，分值分别为50分、50分、50分，你只需要完成其中的任意两题，如果你 完成了所有的题目，我们将选取你成绩最高的两题作为你最后的成绩，满分为100分。 *每道试题都有多个测试文件，每个测试文件内只有一组测试数据。 *所有试题均为文件输入输出，考生应注意每道题目的文件命名。 *考试时间为 9:00 至 12:00，计 180 分钟。 *输入输出参照程序如下： #includecstdio int main() { /*请务必于代码开头加入以下两行*/ freopen(input.txt,r,stdin); freopen(output.txt,w,stdout); int a,b; scanf(%d%d,a,b); printf(%d\n,a+b); return 0; } 试题1点蜡烛问题(candle) 时限：1s 内存：32M (50 points) 提交文件名：candle.cpp ★问题描述： 已知有若干长短不一的蜡烛，每根蜡烛被使用一天后将耗掉一个单位长度。 现将按以下要求每天选择蜡烛进行使用：第一天需要同时使用一根蜡烛，第二天 需要同时使用两根蜡烛……以此类推，接下去每天比前一天需要使用蜡烛的数量 多一根，也就是说到了第i天需要同时使用i根蜡烛。如果一根蜡烛的长度为零， 表示这根蜡烛已经用光，不能再进行使用。 现给已知长度的n根蜡烛，请求出在最合理的情况下，这些蜡烛最多能使用 几天。比如现有3根蜡烛A、B、C，且长度均为2，若按下表方案则能使用3天。 使用 长度 第一天 A (2,2,2)-(1,2,2) 第二天 B、C (1,2,2)-(1,1,1) 第三天 A、B、C (1,1,1)-(0,0,0) ★数据输入： 读入数据由文件 input.txt 提供，输入数据的第一行为一个正整数 n(1≤n ≤1000)，表示有n根蜡烛。输入数据的第二行包含n个范围在1与1000之间的 整数，分别表示每根蜡烛的长度。 ★结果输出： 对于每组输入数据，输出一个整数，表示这些蜡烛最多能使用的天数，结果 输出到文件output.txt。 输入示例(input.txt) 输出示例(output.txt) 4 4 2 2 2 4 4 3 5 2 2 1 6 6 1 2 3 4 5 6 11