高中信息技术全国青少年奥林匹克联赛教案递推法二.pdf
《高中信息技术全国青少年奥林匹克联赛教案递推法二.pdf》由会员分享,可在线阅读,更多相关《高中信息技术全国青少年奥林匹克联赛教案递推法二.pdf(8页珍藏版)》请在三一文库上搜索。
1、1 递推法 课题:递推法 目标: 知识目标:递推概念与利用递推解决实际问题 能力目标:递推方程 重点:递推方程 难点:递推方程写出 板书示意: 1) 递推的理解(例20) 2) 倒推法(例21) 3) 顺推法(例22、例 23) 授课过程: 递推就是逐步推导的过程。我们先看一个简单的问题。 例 20:一个数列的第0 项为 0,第 1 项为 1,以后每一项都是前两项的和,这个数列就 是著名的裴波那契数列,求裴波那契数列的第N项。 分析:我们可以根据裴波那契数列的定义:从第2 项开始,逐项推算,直到第N项。因 此可以设计出如下算法: F0 := 1; F1 := 2; FOR I := 2 TO
2、N DO FI := FI 1 + FI 2; 从这个问题可以看出,在计算裴波那契数列的每一项目时,都可以由前两项推出。这样, 相邻两项之间的变化有一定的规律性,我们可以将这种规律归纳成如下简捷的递推关系式: Fn=g(Fn-1) ,这就在数的序列中,建立起后项和前项之间的关系。然后从初始条件 (或是最终 结果)入手,按递推关系式递推,直至求出最终结果(或初始值)。很多问题就是这样逐步 求解的。 对一个试题, 我们要是能找到后一项与前一项的关系并清楚其起始条件(或最终结果) , 问题就可以递推了,接下来便是让计算机一步步了。让高速的计算机从事这种重复运算, 真正起到“物尽其用”的效果。 2 1
3、2 01 21 nff n n f nn n 2 递推分倒推法和顺推法两种形式。算法流程如下: 一、倒推法 所谓倒推法,就是在问题的解或目标是由初始值递推得到的问题中,已知解或目标,根 据递推关系, 采用倒推手段, 一步步的倒推直至求得这个问题的初始陈述的方法。因为这类 问题的运算过程是一一映射的,故可分析其递推公式。看看下面的例题。 例 21:贮油点 一辆重型卡车欲穿过1000 公里的沙漠, 卡车耗汽油为1 升/ 公里, 卡车总载油能力为500 公升。 显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点,使 卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点?每一贮油点应存
4、储多少汽油,才能 使卡车以消耗最少汽油的代价通过沙漠? 编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。格式 如下: No. Distance(k.m.) Oil(litre) 1 2 , 分析: 设 WayI 第 I 个贮油点到终点(I=0 )的距离; oilI第 I 个贮油点的贮油量; 我们可以用倒推法来解决这个问题。从终点向始点倒推,逐一求出每个贮油点的位置及 存油量。图19 表示倒推时的返回点。 从贮油点I 向贮油点I+1 倒推的方法是:卡车在贮油点 I 和贮油点I+1 间往返若干次。 卡车每次返回I+1 点时应该正好耗尽500 公升汽油, 而每次从I+1 点出
5、发时又必须装足500 图 19 倒推过程 满足求解 Y 顺推 初始条件 F1 N 倒推 由题意 (或递推关系)定初始值F1(边 界条件)求出顺推关系式Fi=g(F i-1) ; 由题意(或递推关系)确定最终结果 Fn;求出倒推关系式 Fi-1 =g (Fi) ; I=1 ; 由边界条件F1出发进行顺推 I=n ; 从最终结果Fn出发进行倒推 While 当前结果Fi非最终结果Fn do While 当前结果Fi非初始值F1 do 由 Fi=g(F i-1) 顺推后项; 由 Fi-1=g(F i) 倒推前项; 输出顺推结果Fn和顺推过程;输出倒推结果F1和倒推过程; 3 公升汽油。 两点之间的距
6、离必须满足在耗油最少的条件下,使 I 点贮足 I*500 公升汽油的要 求( 0I n-1 ) 。具体来说,第一个贮油点I=1 应距终点I=0 处 500km ,且在该点贮藏500 公升汽油,这样才能保证卡车能由I=1 处到达终点I=0 处,这就是说 WayI=500 ;oilI=500; 为了在 I=1 处贮藏 500 公升汽油,卡车至少从I=2 处开两趟满载油的车至I=1 处,所以 I=2 处至少贮有2*500 公升汽油 ,即 oil2=500*2=1000;另外,再加上从I=1 返回至 I=2 处的一趟空载,合计往返3 次。三次往返路程的耗油量按最省要求只能为500 公升,即 d12=5
7、00/3km,Way2=Way1+d12=WayI+500/3 此时的状况如图20 所示。 为了在 I=2 处贮藏 1000 公升汽油,卡车至少从I=3 处开三趟满载油的车至I=2 处。所 以 I=3 处至少贮有3*500 公升汽油,即oil3=500*3=1500。加上 I=2 至 I=3 处的二趟返程 空车,合计5 次。路途耗油亦应500 公升, 即 d23=500/5 , Way3=Way2+d 23=Way2+500/5 ; 此时的状况如图21 所示。 依次类推,为了在 I=k 处贮藏 k*500 公升汽油,卡车至少从I=k+1 处开 k 趟满载车至I=k 处,即 oilk+1=(k+
8、1)*500=oilk+500,加上从 I=k 返回 I=k+1 的 k-1 趟返程空间,合计 2k-1 次。这 2k-1 次总耗油量按最省要求为500 公升,即dk,k+1=500/(2k-1), 图 20 倒推到第二步 图 21 倒推到第三步 4 Wayk+1=Wayk+dk,k+1=Wayk+500/(2k-1); 此时的状况如图22 所示。 最后, I=n 至始点的距离为1000-Wayn,oiln=500*n。为了在 I=n 处取得 n*500 公升 汽油,卡车至少从始点开n+1 次满载车至I=n ,加上从 I=n 返回始点的n 趟返程空车,合计 2n+1 次 , 2n+1趟 的 总
9、 耗 油 量 应 正 好 为 ( 1000-Wayn ) *(2n+1) , 即 始 点 藏 油 为 oiln+(1000-Wayn)*(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 处开始向终点倒推 Way1 := 500; Oil1 :=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中 信息技术 全国青少年 奥林匹克 联赛 教案 递推法二
链接地址:https://www.31doc.com/p-5157044.html