算法合集之《数学归纳法与解题之道》.ppt

《算法合集之《数学归纳法与解题之道》.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学归纳法与解题之道山西省实验中学　张昆玮道IOI2009国家集训队论文演示张昆玮贪心构造优化如此之多的算法，是怎样想到的？这些算法巧诚巧矣，可正确性怎么证明呢？引言道生一，一生二，二生三，三生万物。——老子：《道德经》数学归纳法IOI2009国家集训队论文演示张昆玮概览2.在证明算法正确性上的应用贪心算法其他算法3.在构造性算法中的应用数据结构的恢复性构造策略与解决方案的构造4.数学归纳法与算法优化巧妙选择归纳对象力求完善归纳基础慎重选择归纳方向适当加强归纳假设5.启发作用与美学价值6.问题与缺陷理论上是否欠完备应用上是否较繁琐不适用的问题1.关于数学归纳法简短的回顾基本的定理、概念

2、与方法是总结更是探索例5（线性结构）SetCover例6（树状结构）RomanRoadsIOI2009国家集训队论文演示张昆玮难缺乏固定套路依赖于具体的数据结构通用灵活适用于各种数据结构易构造性问题数学归纳法IOI2009国家集训队论文演示张昆玮【例5】SetCover——数据结构的恢复性构造子集覆盖问题定义为选出尽量少的子集，使已知集合中的每个元素至少属于其中的一个。线段覆盖问题定义为选出尽量少的整点，使给定的每条线段上都至少有其中的一个。以整点为子集，所有包含这个整点的线段为子集中的元素，可以把一个线段覆盖问题归约到子集覆盖问题。如果给定一个由线段覆盖问题归约成的子集覆盖问题，该怎

3、么解决呢？IOI2009国家集训队论文演示张昆玮线段覆盖问题在数轴上选出尽量少的整点给定的每条线段上必须至少有其中的一个按左端点排序后有简单的贪心算法IOI2009国家集训队论文演示张昆玮转化成子集覆盖问题整点作为集合（实际上只需每线段的右端点）所有包含此整点的线段为其元素一般的子集覆盖问题→NP完全123451,22,33,44,55IOI2009国家集训队论文演示张昆玮怎么办？恢复线性结构直接搜索Tips：只需要恢复线段的位置关系和每个线段的右端点IOI2009国家集训队论文演示张昆玮定义线段的位置线段的位置即为其中点的位置两线段距离即为其中点的距离两线段距离可以使用对应集合运算求

4、出两线段必须相交！IOI2009国家集训队论文演示张昆玮到底是“＋”还是“－”？问题：如何拓展连通分量？我们把问题分为连通分量来处理两个连通分量之间线段距离可以任意，不影响结论每个连通分量的第一条线段位置任意归纳假设已知当前连通分量中已计算完成的所有线段的位置以及其中一条与要添加的线段X相交的线段A。IOI2009国家集训队论文演示张昆玮调整归纳假设只有一条线段时方向无关紧要初始时刻选择不同的方向只会使最终的结果互为轴对称而已。其他情形中为了判断方向，我们需要调整归纳假设归纳假设如果线段总数不止一条，除以上假设外，还需要取一条已求出的线段B，知道其关于A的方向。归纳假设已知当前连通分量

5、中已计算完成的所有线段的位置以及其中一条与要添加的线段X相交的线段A。IOI2009国家集训队论文演示张昆玮同侧？异侧？X与B在A的同侧的充分必要条件是他们在A之内的部分存在包含关系IOI2009国家集训队论文演示张昆玮同侧？异侧？X与B在A的同侧的充分必要条件是他们在A之内的部分存在包含关系ABXABX同侧ABXAXB异侧IOI2009国家集训队论文演示张昆玮线段的右端点A所有与A相交、在A右侧的线段与A的公共点问题解决IOI2009国家集训队论文演示张昆玮小结以上解题过程用庖丁解牛的方法步步推进，将问题分为多个部分，逐一化解数学归纳法灵活的归纳假设为主要问题的求解提供了不少便利算法

6、实现中我们不断克服困难的过程正是归纳假设不断完善的过程解题之道故弄玄虚简单自然神来之笔直剖核心数学归纳法从简单情形做起从不同角度观察与IOI2009国家集训队论文演示张昆玮谢谢欢迎大家提问IOI2009国家集训队论文演示张昆玮