信息学奥林匹克竞赛辅导课件_归纳策略

《信息学奥林匹克竞赛辅导课件_归纳策略》由会员分享，可在线阅读，更多相关《信息学奥林匹克竞赛辅导课件_归纳策略（122页珍藏版）》请在金锄头文库上搜索。

1、第三节 归纳策略 如果说对应策略的核心是举一反三 触类旁 通地对已经解决的类似问题和有关事实作联 想 外推出事物间联系的话 那么归纳策略 则是通过列举试题本身的特殊情况 经过深 入分析 最后概括出事物内在的一般规律 并得到一种高度抽象的解题模型 归纳法要比搜索的方法 例如以后将讲解 的枚举法 回溯法等 更能反映问题的本质 但是并不是所有实际问题都可以总结归纳 出一般规律 即便是可以 归纳也不是一件 容易的事情 尤其要归纳出一个数学模型更 为困难 而且归纳过程通常没有一定的规则 可供遵循 从本质上讲 归纳就是通过观察 一些简单而特殊的情况 最后总结出有用的 结论或解决问题的有效途径 通常 归纳的

2、过程分四个步骤 n 1 细心的观察 n 2 丰富的联想 n 3 继续尝试 n 4 总结归纳出结论 归纳是一种抽象 即从特殊现象中找出一般关 系 但在归纳过程中不可能列举所有情况 因而最后 得出的结论还只是一种猜测 即归纳假设 通过精 心观察而提出的归纳假设得不到证实或最后证明是错 的 也是常有的事 因此要尽可能对归纳假设加以严 格的证明 证明的方法通常使用数学归纳法 即便找 不到证明方法 也必须尽可能多地提出那些容易出错 和疏漏的边界情况加以验证 使归纳出的结论和解决 问题的途径经得起各种测试数据的检验 问题经过分析归纳后 一般产生 四种结果 1 递推式 2 递归式 3 制定目标 4 贪心方案

3、 当然 经过分析直接概括出高度抽象的数学公式 亦是一种归纳过程 一种解题的途径 但是怎样进行这 种归纳 这个问题太宽泛 与其说它是计算机算法的策 略 还不如说它是一种数学知识和数学能力 取决于解 题者本身的数学功底 我们已经在 对应策略 一节中 对如何将试题与数学公式对应的问题作了一些讨论 这 里不再赘述 一 递推法 瞬息变幻的世界 每一件事物都在随时间的流逝 发生着微妙的变化 而在这纷繁的变幻中 许多现象 的变化是有规律的 这种规律往往呈现出前因和后果 的关系 即某种现象的变化结果与紧靠它前面变化的 一个或一些结果紧密关联 所谓 三岁看老 说的就是 这个道理 这一道理也正体现了递推的思想 递

4、推关 系几乎在所有的数学分支中都有重要作用 在联赛中 更因其简捷高效而显示出独特的魅力 1 递推关系的定义和求解方法 有一类试题 每相邻两项数之间的变化有一定的规律 性 我们可将这种规律归纳成如下简捷的递推关系式 fn g fn 1 或者fn 1 g fn 这样就在数的序列中 建立起后项和前项之间的关 系 然后从初始条件 或最终结果 入手 一步步地按递 推关系式递推 直至求出最终结果 或初始值 很多程 序就是按这样的方法逐步求解的 如果对一个试题 我 们要是能找到后一项数与前一项数的关系并清楚其起始 条件 或最终结果 问题就比较容易解决 让计算机 一步步计算就是了 让高速的计算机从事这种重复运

5、算 可真正起到 物尽其用 的效果 顺推法就是由边界条件出发 通过递推关系式推 出后项值 再由后项值按递推关系式推出再后项值 依次递推 直到从问题初始陈述向前推进到这个问题 的解为止 倒推法就是在不知初始值的情况下 经推理而获 知问题的最终解或目标 再倒过来 推知它的初始条 件 因为这种问题的运算过程是一一映射的 故可分 析其倒推公式 然后再从最终解或目标出发 采用倒 推手段 一步步地倒推到这个问题的初始陈述 递推分倒推法和顺推法两种形式 一般分析思路 if 求解初始条件f1 倒推 由题意 或递推关系 确定最终结果fn 求出倒推关系式fi 1 g fi for i n i 2 i fi 1 g

6、fi 从最终结果fn进行倒推 推出倒推结果f1 else 顺推 由题意 或递推关系 确定初始值f1 边界条件 求出顺推关系式 fi g fi 1 for i 2 i 2 个盘子时 总是先借 助c柱把上面的n 1个盘子移动到b柱上 然后把a 柱最下面的盘子移动到c柱上 再借助a柱把b柱 上的n 1个盘子移动到c柱上 总共移动 hn 2hn 1 1 边界条件 h1 1 3 平面分割问题 设有n条封闭曲线画在平面上 而任何两条封闭曲线恰 好相交于两点 且任何三条封闭曲线不相交于同一点 问这些封闭曲线把平面分割成的区域个数 分析 设an为n条封闭曲线把平面分割成的区域个数 由图 可得 a2 a1 2

7、a3 a2 4 a4 a3 6 n从这些式子中可以看出 an an 1 2 n 1 n当然 上面的式子只是我们通过观察4幅图后得出的结 论 它的正确性尚不能保证 下面不妨让我们来试着证 明一下 当平面上已有n 1条曲线将平面分割成an 1个区 域后 第n条曲线每与其他曲线相交一次 就会增加一 个区域 因为平面上已经有了n 1条封闭曲线 且第n条 曲线与己有的每一条闭曲线恰好相交于两点 不会与任 两条曲线交于同一点 故平面上一共增加 2 n 1 个区 域 加上已有的an 1个区域 一共有an 1 2 n 1 个区域 所以本题的递推关系是 an an 1 2 n 1 边界条件是a1 2 n平面分割

8、问题是竞赛中经常触及到的一类问题 由 于其灵活多变 常常让选手感到棘手 下题是另一 种平面分割问题 有兴趣的读者不妨自己先试着求 一下其中的递推关系 4 Catalan 数 n在一个凸n边形中 通过不相交于n边形内部的对角线 把n边形拆分成若干三角形 不同的拆分数目用 hn表之 hn即为Catalan数 例如五边形有如图所示的五种拆 分方案 故h5 5 求对于一个任意的凸n边形相应的hn nCatalan 数首先是由Euler在精确计算对凸n边形不同的 对角三角形剖分的个数问题时得到的 它经常出现在组 合计数问题中 分析 设Cn表示凸n边形的拆分方案总数 由题目中的要 求可知一个凸n边形的任意

9、一条边都必然是一个三角形 的一条边 边P1Pn也不例外 再根据 不在同一直线上 的三点可以确定一个三角形 只要在P2 P3 Pn 1 点中找一个点Pk 1 k1 m 1 边界条件为 S2 n 0 0 S2 n 1 1 S2 n n 1 S2 n k 0 k n n第二类 stirling 数在竞赛中较少出现 但在竞赛 中也有一些题目与其类似 甚至更为复杂 读者不 妨自己来试着建立其中的递推关系 n通过上面对五种典型的递推关系建立过程的探讨 可知对待递推类的题目 要具体情况具体分析 通 过找到某状态与其前面状态的联系 建立相应的递 推关系 3 递推关系的应用 递推关系的应用十分广泛 其中一个非常

10、重要的应用就 是著名的杨辉三角 又称 Pascal三角 杨辉三角是 根据组合公式Cnr Cn 1r Cn 1r 1画出来的 很显然 组合 公式 杨辉三角都属于递推关系的范围 在今天的信息学竞赛中 递推关系的应用也日趋广泛 下面就让我们从近年来的两道竞赛题中体会递推关系的 应用 例13 蜜蜂爬行 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房 不 能反向爬行 如图所示 试求出蜜蜂从蜂房a 爬到蜂房b 的可能路线数 n分析 这是一道很典型的Fibonacci数列类题目 其中 的递推关系很明显 由于 蜜蜂只能爬向右侧相邻的蜂 房 不能反向爬行 的限制 决定了蜜蜂到 n 点的路径 只能是从 n 1 点或

11、n 2 点到达的 故 fn fn 1 fn 2 a 2 n b 边界条件为 fa 1 fa 1 1 例14 分割平面 同一平面内的n n 2 条直线 相交于同一点 则这n条直线最多能将平面分割成多少 个不同的区域 分析 直线的平面分割与封闭曲线的平面分割十分相似 不同之处就在于线条的曲直以及是否存在共点的直线 由于共点直线的特殊性 我们决定先考虑p条相交于一 点的直线 然后再考虑剩下的n p条直线 首先可以直接求出p条相交于一点的直线将平面划分成的 区域数为2 p个 然后在平面上已经有k k p 条直线的基础上 加上一条 直线 最多可以与k条直线相交 而每次相交都会增加 一个区域 与最后一条直

12、线相交后 由于直线可以无限 延伸 还会再增加一个区域 所以 fm fm 1 m m P 边界条件在前面己经计算过了 是fp 2 p 虽然这题看上去有两个参数 但是在实际做题中会发现 本题还是属于带一个参数的递推关系 例15 平面分割空间问题 一个平面把空间分成独立的两个部分 两个平面把空间分 成4个部分 n个平面 最多能把整个空间分割成多少个 部分 分析 立体空间的情况是陌生的 但是空间和平面的关系 与平面和直线的关系是相似的 平面把空间分割成两个 部分 直线也把平面分割成两个部分 于是得到了另一 个与例题相类似的问题 n条直线 最多能把整个平面 分割成多少个部分 如图所示 n一条直线 把平面

13、分割为两个部分 增加一条直线 它 与第一条直线相交 被分为两段射线 每一段射线又把 所在的区域分成两部分 因此增加了2个部分 再增加 一条直线 它与前两条直线相交 被分为三段 每一 段又把所在区域分成两部分 共增加了3个部分 n由此类推 设前k 1条直线共把平面分为ak 1个部分 加入第k条直线 与前k 1条直线相交 被分为k段 每 一段把所在区域分为两部分 总共增加了k部分 总共 有ak 1 k个部分 于是得到了递推关系 a1 2 ak ak 1 k 即 ak 1 k 1 k 2 于是直线分割平面的问题就解决了 既然空间和平面 与平面和直线的关系相似 那么直接把 平面换成空间 把直线换成平面

14、 就可以直接用以上的 过程来证明未知的问题了吗 显然是不可以的 这种仅仅根据主观的相似性得出的机械 模仿是错误的 n但是如果仔细分析一下错误的原因 将会发现问题的关 键 线线相交得到的是交点 面面相交得到的是直线 k个 点把直线分成k 1个部分 而k条直线则不是简单的把平 面分成k 1个部分 事实上 k条直线最多把平面分成ak 个部分 n因此两个问题真正的相似之处在于 一个为了计算直线 把平面分割成几部分 先计算这条直线被点 线线交点 分割成几部分 把二维的问题化为一维的问题 另一 个要计算平面把空间分割成几部分 先计算这个平面被 线 面面交线 分割成几部分 把三维的问题化为二维 的问题 而二

15、维的问题是已经被解决了的 于是反过来 三维的问题也解决了 同样是利用数学归纳法 一个平面把空间分割成两部分 设前k 1个平面共把空 间分割成 bk 1个部分 加入第k个平面后 与前k 1个平 面相交 共有k 1条交线 k 1 条交线把这个平面分为 几块呢 这买际上就是刚刚解决过的回题 k 1条直线 把平面分割成 ak 1 1 k 1 k 2 分别把所在原来空间一分为二 总共增加了ak 1个部分 于是平面总共把空间分割成 个部分 于是得到了递推关系 n利用这一递推关系来编写程序 不难求出 bn 而且即便对很大的 n 程序的运算速度仍然 是很快的 当然 也可以计算出 bn的通项公 式 二 递归法

16、设一个未知函数f 用其自身构成的已知函数g来定义 f n g n f n 1 n 0 f 0 a n 0 为了定义f n 必须先定义f n 1 为了定义 f n 1 又必须先定义f n 2 上述这种用自身的简单情况 来定义自己的方式称为递归定义 一个递归定义必须是有确切含义的 也就是说 必须一步 比一步简单 最后是有终结的 决不能无限循环下去 在 f n 的定义中 当n为0时定义一个已知数a 是最简单 的情况 称为递归边界 它本身不再使用递归的定义 与递推一样 每一个递归定义都有其边界条件 但 不同的是 递推是由边界条件出发 通过递推公式求 f n 的值 从边界到求解的全过程十分清楚 而递归则是从函数自身出发来达到边界条件 在通 往边界条件的递归调用过程中 系统用堆栈把每次调用 的中间结果保存在栈区 直至求出递归边界值f 0 a 然后返回调用函数 返回过程中 中间结果相继出栈恢 复 f 1 g 1 a f 2 g 2 f 1 直到 f n g n f n 1 描述递归定义的函数或求解递归问题的过程称为递 归算法 一个递归算法 本质上是将较复杂的处理归结 为简单处理 直到最简单的处理 从