高中信息技术 全国青少年奥林匹克联赛教案 递推法二VIP免费

递推法课题：递推法目标：知识目标：递推概念与利用递推解决实际问题能力目标：递推方程重点：递推方程难点：递推方程写出板书示意：1）递推的理解（例20）2）倒推法（例21）3）顺推法（例22、例23）授课过程：递推就是逐步推导的过程。我们先看一个简单的问题。例20：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N项。分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算，直到第N项。因此可以设计出如下算法：F[0]:=1;F[1]:=2;FORI:=2TONDOF[I]:=F[I–1]+F[I–2];从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：Fn=g(Fn-1)，这就在数的序列中，建立起后项和前项之间的关系。然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。很多问题就是这样逐步求解的。对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。递推分倒推法和顺推法两种形式。算法流程如下：一、倒推法所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。因为这类问题的运算过程是一一映射的，故可分析其递推公式。看看下面的例题。例21：贮油点一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能顺利穿过沙漠。试问司机如怎样建立这些贮油点？每一贮油点应存储多少汽油，才能使卡车以消耗最少汽油的代价通过沙漠？编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。格式如下：No.Distance(k.m.)Oil(litre)1××××满足求解Y{顺推}初始条件F1N{倒推}由题意（或递推关系）定初始值F1（边界条件）求出顺推关系式Fi=g(Fi-1)；由题意（或递推关系）确定最终结果Fn；求出倒推关系式Fi-1=g’(Fi)；I=1；{由边界条件F1出发进行顺推}I=n；{从最终结果Fn出发进行倒推}While当前结果Fi非最终结果FndoWhile当前结果Fi非初始值F1do2××××……………分析：设Way[I]——第I个贮油点到终点（I=0）的距离；oil[I]——第I个贮油点的贮油量；我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及存油量。图19表示倒推时的返回点。从贮油点I向贮油点I+1倒推的方法是：卡车在贮油点I和贮油点I+1间往返若干次。卡车每次返回I+1点时应该正好耗尽500公升汽油，而每次从I+1点出发时又必须装足500公升汽油。两点之间的距离必须满足在耗油最少的条件下，使I点贮足I*500公升汽油的要求（0≦I≦n-1）。具体来说，第一个贮油点I=1应距终点I=0处500km，且在该点贮藏500公升汽油，这样才能保证卡车能由I=1处到达终点I=0处，这就是说Way[I]=500；oil[I]=500；图19倒推过程为了在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)，...