1、数学归纳法与解题之 道山西省实验中学 张昆玮道IOI2009国家集训队论文演示 张昆玮如此之多的算法，是怎样想到的？如此之多的算法，是怎样想到的？这些算法巧诚巧矣，可正确性怎么证明呢？这些算法巧诚巧矣，可正确性怎么证明呢？引言引言数学归纳法IOI2009国家集训队论文演示 张昆玮概览2.在证明算法正确性上的应用 贪心算法 其他算法3.在构造性算法中的应用 数据结构的恢复性构造 策略与解决方案的构造4.数学归纳法与算法优化 巧妙选择归纳对象 力求完善归纳基础 慎重选择归纳方向 适当加强归纳假设5.启发作用与美学价值6.问题与缺陷 理论上是否欠完备 应用上是否较繁琐 不适用的问题1.关于数学归纳法
2、 简短的回顾 基本的定理、概念与方法 是总结更是探索例 5（线性结构） Set Cover例 6（树状结构） Roman RoadsIOI2009国家集训队论文演示 张昆玮难缺乏固定套路依赖于具体的数据结构 通用灵活适用于各种数据结构 易IOI2009国家集训队论文演示 张昆玮【例 5】 Set Cover数据结构的恢复性构造数据结构的恢复性构造子集覆盖问题定义为选出尽量少的子集，使已知集合中的每个元素至少属于其中的一个。线段覆盖问题定义为选出尽量少的整点，使给定的每条线段上都至少有其中的一个。以整点为子集，所有包含这个整点的线段为子集中的元素，可以把一个线段覆盖问题归约到子集覆盖问题。如果给
3、定一个由线段覆盖问题归约成的子集覆盖问题，该怎么解决呢？IOI2009国家集训队论文演示 张昆玮线段覆盖问题 在数轴上选出尽量少的整点 给定的每条线段上必须至少有其中的一个 按左端点排序后有简单的贪心算法IOI2009国家集训队论文演示 张昆玮转化成子集覆盖问题 整点作为集合 （实际上只需每线段的右端点） 所有包含此整点的线段为其元素 一般的 子集覆盖问题 NP 完全12 3451,2 2,3 3,4 4,5 5IOI2009国家集训队论文演示 张昆玮怎么办？直接搜索Tips： 只需要恢复线段的位置关系和每个线段的右端点 IOI2009国家集训队论文演示 张昆玮定义线段的位置 线段的位置即为其中点的位置 两线段距离即为其中点的距离 两线段距离可以使用对应集合运算求出两线段必须相交！IOI2009国家集训队论文演示 张昆玮到底是 “ ”还是 “ ”？问题：如何拓展连通分量？ 我们把问题分为连通分量来处理 两个连通分量之间线段距离可以任意，不影响结论 每个连通分量的第一条线段位置任意已知当前连通分量中已计算完成的所有线段的位置以及其中一条与要添加的线段 X相交的线段 A。 IOI2009国家集训队论文演示 张昆玮
