《算法合集之数学归纳法与解题之道》由会员分享，可在线阅读，更多相关《算法合集之数学归纳法与解题之道（16页珍藏版）》请在装配图网上搜索。
1、4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮数学归纳法与解题之道山西省实验中学 张昆玮道4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮数学归纳法4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮概览2.在证明算法正确性上的应用 贪心算法 其他算法3.在构造性算法中的应用 数据结构的恢复性构造 策略与解决方案的构造4.数学归纳法与算法优化 巧妙选择归纳对象 力求完善归纳基础 慎重
2、选择归纳方向 适当加强归纳假设5.启发作用与美学价值6.问题与缺陷 理论上是否欠完备 应用上是否较繁琐 不适用的问题1.关于数学归纳法 简短的回顾 基本的定理、概念与方法 是总结更是探索例5（线性结构）Set Cover例6（树状结构）Roman Roads4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮难缺乏固定套路依赖于具体的数据结构 通用灵活适用于各种数据结构 易4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮【例5】Set Cover子集覆盖问
3、题定义为选出尽量少的子集，使已知集合中的每个元素至少属于其中的一个。线段覆盖问题定义为选出尽量少的整点，使给定的每条线段上都至少有其中的一个。以整点为子集，所有包含这个整点的线段为子集中的元素，可以把一个线段覆盖问题归约到子集覆盖问题。如果给定一个由线段覆盖问题归约成的子集覆盖问题，该怎么解决呢？4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮线段覆盖问题 在数轴上选出尽量少的整点 给定的每条线段上必须至少有其中的一个 按左端点排序后有简单的贪心算法4251 10011 0010 1010 1101 0001 0100 1
4、011IOI2009国家集训队论文演示 张昆玮转化成子集覆盖问题 整点作为集合（实际上只需每线段的右端点）所有包含此整点的线段为其元素 一般的子集覆盖问题NP完全123451,2 2,33,44,554251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮怎么办？直接搜索Tips：只需要恢复线段的位置关系和每个线段的右端点 4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮定义线段的位置 线段的位置即为其中点的位置 两线段距离即为其中点的距离 两线段距离可以使用
5、对应集合运算求出xorDis,2ABA B 两线段必须相交！4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮到底是“”还是“”？问题：如何拓展连通分量？我们把问题分为连通分量来处理两个连通分量之间线段距离可以任意，不影响结论每个连通分量的第一条线段位置任意已知当前连通分量中已计算完成的所有线段的位置以及其中一条与要添加的线段X相交的线段A。MidMidDis,XAA X4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮调整归纳假设只有一条线段时方向无关紧
6、要初始时刻选择不同的方向只会使最终的结果互为轴对称而已。其他情形中为了判断方向，我们需要调整归纳假设如果线段总数不止一条，除以上假设外，还需要取一条已求出的线段B，知道其关于A的方向。已知当前连通分量中已计算完成的所有线段的位置以及其中一条与要添加的线段X相交的线段A。4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮同侧？异侧？XABA XABA 4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮同侧？异侧？ABXABX同侧ABXAXB异侧4251 10
7、011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮线段的右端点A所有与A相交、在A右侧的线段与A的公共点 4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮小结以上解题过程用庖丁解牛的方法步步推进，将问题分为多个部分，逐一化解数学归纳法灵活的归纳假设为主要问题的求解提供了不少便利算法实现中我们不断克服困难的过程正是归纳假设不断完善的过程解题之道故弄玄虚简单自然神来之笔直剖核心数学归纳法从做起从观察 与4251 10011 0010 1010 1101 0001 0100 1011IOI2009国家集训队论文演示 张昆玮
算法合集之数学归纳法与解题之道
