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

《算法合集之《数学归纳法与解题之道》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《数学归纳法与解题之道》.ppt（16页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、Roman RoadsIOI2009国家集训队论文演示 张昆玮难缺乏固定套路依赖于具体的数据结构 通用灵活适用于各种数据结构 易IOI2009国家集训队论文演示 张昆玮【例5】Set Cover数据结构的恢复性构造数据结构的恢复性构造子集覆盖问题定义为选出尽量少的子集，使已知集合中的每个元素至少属于其中的一个。线段覆盖问题定义为选出尽量少的整点，使给定的每条线段上都至少有其中的一个。以整点为子集，所有包含这个整点的线段为子集中的元素，可以把一个线段覆盖问题归约到子集覆盖问题。如果给定一个由线段覆盖问题归约成的子集覆盖问题，该怎么解决呢？IOI2009国家集训队论文演示 张昆玮线段覆盖问题在数轴

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

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

5、同侧？异侧？IOI2009国家集训队论文演示 张昆玮同侧？异侧？ABXABX同侧ABXAXB异侧IOI2009国家集训队论文演示 张昆玮线段的右端点A所有与A相交、在A右侧的线段与A的公共点 IOI2009国家集训队论文演示 张昆玮小结 以上解题过程用以上解题过程用庖丁解牛庖丁解牛的方法步步推进，将问题分为多个部分，逐一化解的方法步步推进，将问题分为多个部分，逐一化解 数学归纳法灵活的归纳假设数学归纳法灵活的归纳假设为主要问题的求解提供了不少便利为主要问题的求解提供了不少便利 算法实现中我们不断克服困难的过程正是算法实现中我们不断克服困难的过程正是归纳假设归纳假设不断完善的过程不断完善的过程解题之道故弄玄虚简单自然神来之笔直剖核心数学归纳法从简单情形简单情形做起从不同角度不同角度观察 与IOI2009国家集训队论文演示 张昆玮谢谢欢迎大家提问IOI2009国家集训队论文演示 张昆玮