高中信息技术 全国青少年奥林匹克联赛教案 递推法二 (2).doc

1 递推法递推法 课题 递推法 目标 知识目标 递推概念与利用递推解决实际问题 能力目标 递推方程 重点 递推方程 难点 递推方程写出 板书示意 1 递推的理解 例 20 2 倒推法 例 21 3 顺推法 例 22 例 23 授课过程 递推就是逐步推导的过程 我们先看一个简单的问题 例 20 一个数列的第 0 项为 0 第 1 项为 1 以后每一项都是前两项的和 这个数列 就是著名的裴波那契数列 求裴波那契数列的第 n 项 分析 我们可以根据裴波那契数列的定义 从第2 项开始 逐项推算 直到第 n 项 因此可以设计出如下算法 f 0 1 f 1 2 for i 2 to n do f i f i 1 f i 2 从这个问题可以看出 在计算裴波那契数列的每一项目时 都可以由前两项推出 这 样 相邻两项之间的变化有一定的规律性 我们可以将这种规律归纳成如下简捷的递推关 系式 fn g fn 1 这就在数的序列中 建立起后项和前项之间的关系 然后从初始条件 或是最终结果 入手 按递推关系式递推 直至求出最终结果 或初始值 很多问题就 是这样逐步求解的 对一个试题 我们要是能找到后一项与前一项的关系并清楚其起始条件 或最终结果 问题就可以递推了 接下来便是让计算机一步步了 让高速的计算机从事这种重复运算 真正起到 物尽其用 的效果 2 12 01 21 nff n n f nn n 2 递推分倒推法和顺推法两种形式 算法流程如下 一 倒推法 所谓倒推法 就是在问题的解或目标是由初始值递推得到的问题中 已知解或目标 根据递推关系 采用倒推手段 一步步的倒推直至求得这个问题的初始陈述的方法 因为 这类问题的运算过程是一一映射的 故可分析其递推公式 看看下面的例题 例 21 贮油点 一辆重型卡车欲穿过 1000 公里的沙漠 卡车耗汽油为 1 升 公里 卡车总载油能力为 500 公升 显然卡车装一次油是过不了沙漠的 因此司机必须设法在沿途建立若干个贮油 点 使卡车能顺利穿过沙漠 试问司机如怎样建立这些贮油点 每一贮油点应存储多少汽 油 才能使卡车以消耗最少汽油的代价通过沙漠 编程计算及打印建立的贮油点序号 各贮油点距沙漠边沿出发的距离以及存油量 格 式如下 no distance k m oil litre 1 2 分析 设 way i 第 i 个贮油点到终点 i 0 的距离 oil i 第 i 个贮油点的贮油量 我们可以用倒推法来解决这个问题 从终点向始点倒推 逐一求出每个贮油点的位置 及存油量 图 19 表示倒推时的返回点 从贮油点 i 向贮油点 i 1 倒推的方法是 卡车在贮油点 i 和贮油点 i 1 间往返若干次 卡车每次返回 i 1 点时应该正好耗尽 500 公升汽油 而每次从 i 1 点出发时又必须装足 图 19 倒推过程 满足求解 y 顺推 初始条件 f1 n 倒推 由题意 或递推关系 定初始值 f1 边界条件 求出顺推关系式 fi g fi 1 由题意 或递推关系 确定最终结果 fn 求出倒推关系式 fi 1 g fi i 1 由边界条件 f1出发进行顺推 i n 从最终结果 fn出发进行倒推 while 当前结果 fi非最终结果 fn do while 当前结果 fi非初始值 f1 do 由 fi g fi 1 顺推后项 由 fi 1 g fi 倒推前项 输出顺推结果 fn和顺推过程 输出倒推结果 f1和倒推过程 3 500 公升汽油 两点之间的距离必须满足在耗油最少的条件下 使 i 点贮足 i 500 公升汽 油的要求 0 i n 1 具体来说 第一个贮油点 i 1 应距终点 i 0 处 500km 且在该点 贮藏 500 公升汽油 这样才能保证卡车能由 i 1 处到达终点 i 0 处 这就是说 way i 500 oil i 500 为了在 i 1 处贮藏 500 公升汽油 卡车至少从 i 2 处开两趟满载油的车至 i 1 处 所 以 i 2 处至少贮有 2 500 公升汽油 即 oil 2 500 2 1000 另外 再加上从 i 1 返回至 i 2 处的一趟空载 合计往返 3 次 三次往返路程的耗油量按最省要求只能为 500 公升 即 d12 500 3km way 2 way 1 d12 way i 500 3 此时的状况如图 20 所示 为了在 i 2 处贮藏 1000 公升汽油 卡车至少从 i 3 处开三趟满载油的车至 i 2 处 所 以 i 3 处至少贮有 3 500 公升汽油 即 oil 3 500 3 1500 加上 i 2 至 i 3 处的二趟返 程空车 合计 5 次 路途耗油亦应 500 公升 即 d23 500 5 way 3 way 2 d23 way 2 500 5 此时的状况如图 21 所示 依次类推 为了在 i k 处贮藏 k 500 公升汽油 卡车至少从 i k 1 处开 k 趟满载车至 i k 处 即 oil k 1 k 1 500 oil k 500 加上从 i k 返回 i k 1 的 k 1 趟返程空间 合计 2k 1 次 这 2k 1 次总耗油量按最省要求为 500 公升 即 dk k 1 500 2k 1 图 20 倒推到第二步 图 21 倒推到第三步 4 way k 1 way k dk k 1 way k 500 2k 1 此时的状况如图 22 所示 最后 i n 至始点的距离为 1000 way n oil n 500 n 为了在 i n 处取得 n 500 公 升汽油 卡车至少从始点开 n 1 次满载车至 i n 加上从 i n 返回始点的 n 趟返程空车 合计 2n 1 次 2n 1 趟的总耗油量应正好为 1000 way n 2n 1 即始点藏油为 oil n 1000 way n 2n 1 程序设计如下 program oil lib var k integer 贮油点位置序号 d 累计终点至当前贮油点的距离 d1 real i n 至终点的距离 oil way array 1 10 of real i integer begin writeln no distance 30 oil 80 k 1 d 500 从 i 1 处开始向终点倒推 way 1 500 oil 1 500 repeat k k 1 d d 500 2 k 1 way k d oil k oil k 1 500 until d 1000 way k 1000 置始点到终点的距离值 d1 1000 way k 1 求 i n 处至至点的距离 oil k d1 2 k 1 oil k 1 求始点贮油量 由始点开始 逐一打印至当前贮油点的距离和贮油量 for i 0 to k do writeln i 1000 way k i 30 oil k i 80 end 图 22 倒推到第 n 步 5 二 顺推法 顺推法是从边界条件出发 通过递推关系式推出后项值 再由后项值按递推关系式推 出再后项值 依次类推 直至从问题初始陈述向前推进到这个问题的解为止 看看下面的问题 例 22 昆虫繁殖 科学家在热带森林中发现了一种特殊的昆虫 这种昆虫的繁殖能力很强 每对成虫过 x 个月产 y 对卵 每对卵要过两个月长成成虫 假设每个成虫不死 第一个月只有一对成 虫 且卵长成成虫后的第一个月不产卵 过 x 个月产卵 问过 z 个月以后 共有成虫多少 对 x 1 y 1 z x 输入 x y z 的数值 输出 成虫对数 事例 输入 x 1 y 2 z 8 输出 37 分析 首先我们来看样例 每隔 1 个月产 2 对卵 求过 8 月 即第 8 1 9 月 的成虫 个数 月份 123456789 新增卵 0 222610142646 成虫 111357132337 设数组 a i 表示第 i 月新增的成虫个数 由于新成虫每过 x 个月产 y 对卵 则可对每个 a i 作如下操作 a i k x 2 a i k x 2 a i y 1 k i k x 2z 1 1 1 z i iaans 6 end begin readln x y z a 1 1 初始化 for i 1 to z do add i 对每个 a i 进行递推 ans 0 for i 1 to z 1 do ans ans a i 累加总和 writeln ans end 例 23 实数数列 noi94 第 3 题 一个实数数列共有 n 项 已知 ai ai 1 ai 1 2 d 1 i n n 60 键盘输入 n d a1 an m 输出 am 输入数据均不需判错 分析 根据公式 ai ai 1 ai 1 2 d 变形得 ai 1 ai 1 2ai 2d 因此该数列的通项公式为 ai ai 2 2ai 1 2d 已知 a1 如果能求出 a2 这样就可以根据公式递推求出 am ai ai 2 2ai 1 2d ai 2 2 ai 3 2ai 2 2d 2d 2ai 3 5 ai 4 2ai 3 2d 2d 5ai 4 12ai 3 8d 一直迭代下去 直到最后 可以建立 ai和 a1与 a2的关系式 设 ai pia2 qid ria1 我们来寻求 pi qi ri的变化规律 ai ai 2 2ai 1 2d ai pi 2a2 qi 2d ri 2a1 2 pi 1a2 qi 1d ri 1a1 2d pi 2 2pi 1 a2 qi 2 2qi 1 2 d ri 2 2ri 1 a1 pi pi 2 2pi 1 qi qi 2 2qi 1 2 ri ri 2 2ri 1 显然 p1 0 q1 0 r1 1 i 1 p2 1 q2 0 r2 0 i 2 将初值 p1 q1 r1和 p2 q2 r2代入 可以求出 pn qn rn an pna2 qnd rna1 a2 an qnd rna1 pn 然后根据公式 递推求出 am 问题解决 但仔细分析 上述算法有一个明显的缺陷 在求由于在求 a2要运用除法 因此会存在 实数误差 这个误差在以后递推求 am的过程又不断的扩大 在实际中 当 m 超过 30 时 求出的 am就明显偏离正确值 显然 这种算法虽简单但不可靠 为了减少误差 我们可设计如下算法 ai pia2 qid ria1 pi 1a3 qi 1d ri 1a2 7 pi 2a4 qi 2d ri 2a3 pi 2 kak qi 2 kd ri 2 kak 1 an pn k 2ak qn k 2d rn k 2ak 1 ak an qn k 2d rn k 2ak 1 pn k 2 根据公式 可以顺推 a2 a3 am 虽然仍然存在实数误差 但由于 pn k 2递减 因此最后得出的 am要比直接利用公式 精确得多 程序如下 program noi94 3 const maxn 60 var n m i integer d real a array 1 maxn of real f array 1 maxn 1 3 of real f i 1 对应 pi f i 2 对应 qi f i 3 对应 ri procedure init begin write n m d readln n m d 输入项数 输出项序号和常数 write a1 a n readln a 1 a n 输入 a1和 an end procedure solve 根据公式 pi pi 2 2 pi 1 qi qi 2 2 qi 1 ri ri 2 2 ri 1求 pi qi ri begin f 1 1 0 f 1 2 0 f 1 3 1 f 2 1 1 f 2 2 0 f