中学生信息学竞赛中贪心算法的教学和应用思考专 业：计算机应用姓 名：江涛摘要国际信息学奥林匹克(International Olympiad in Informatics,简称 IOI) 始于1989 年，由联合国教科文组织每年举行一次，宗旨是推动普及，并培训、发现这方面有特殊都能的学生。IOI 培训涉及知识有：程序设计语言、常用算法、组合数学、图论、人工智能搜索等。从信息学竞赛培训十多年经验出发，针对中学生的知识结构和思维方式进行了研究，发现很多知识用经典的教材教学效果并不理想。本文通过对贪心算法在培训中的教学实践的总结，体现了一些针对中学生的教学模式特点。第 1 章，以深入浅出、直观明了的形式尽量用图形形式描述了贪心算法与其它求最优性算法的不同之处。第 2 章，对贪心算法的核心问题：证明---参考了大量文献，抽象、归纳出三种证明思路，实用性强（在教学成果中已经体现），并有效地减少了数学性很强的形式逻辑证明。第 3 章，本着思维培训的开发性、创新性，进一步提出了贪心算法应用形式的多样性的几个问题和想法，以期在今后教学中多探索总结。关键词信息学奥林匹克竞赛贪心算法最优问题构造法反证法调整法1 引 言贪心算法 一般来说是解决“ 最优问题 ”，具有编程简单、运行效率高、空间复杂度低等特点。 是信息学竞赛中的一个有为武器，受到广大同学们的青睐。 本文根据十多年的竞赛培训实践，就贪心算法的特点和教学注意事项作些总结。2 贪心算法与简单枚举和动态规划的运行方式比较贪心算法一般是求“最优解”这类问题的。最优解问题可描述为：有n 个输入，它的解是由这 n 个输入的某个子集组成， 并且这个子集必须满足事先给定的条件。这个条件称为 约束条件 。而把满足约束条件的子集称为该问题的可行解 。这些可行解可能有多个。 为了衡量可行解的优劣， 事先给了一个关于可行解的函数，称为 目标函数 。目标函数最大（或最小）的可行解，称为最优解 。(a)求“最优解”最原始的方法为搜索枚举方案法（一般为回溯法）。除了极简单的问题，一般用深度优先搜索或宽度优先搜索。通常优化方法为利用约束条件进行可行性判断剪枝；或利用目标函数下界（或上界），根据当前最优解进行分枝定界。(b)其次现今竞赛中用的比较普遍的动态规划（需要满足阶段无后效性原则）。动态规划主要是利用最最优子问题的确定性，从后向前（即从小规模向大规模）得到当前最优策略，从而避免了重复的搜索。举例说明：求多段图的最...
