haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 小学教育 > 学科竞赛学科竞赛

递推算法专题

发布时间:2014-01-28 11:00:13  

第三讲:
递推算法专题

安徽淮南师范附小

递推算法专题
事物总是千变万化的,在这些变化中,有些 是有规律的。 这种规律往往呈现出前因和后果 的关系。 也就是说,某种现象的变化结果与它 前面变化的一个或一些结果紧密关联。这正体现 了递推的思想。 递推关系几乎在所有的数学分支中都有重要 作用。

递推算法思想:
递推法是一种重要的数学方法。 一般是从已知的初始条件出发,依据某种递 推关系,逐次推出所要求的各中间结果及最后结 果。 其中初始条件可能由问题本身给定,也可能 是通过对问题的分析与化简后确定。但是,在实 际解题中,题目很少会直接出递推关系式,而是 需要通过分析各种状态,找出递推关系式。 一旦建立了递推关系式,就可以很方便地对 序列进行求值。 递推关系式的确立,一般都不是 那么容易实现的,这也是应用递推算法解决问题 的难点所在。

递推: 直接从边界出发 ,利用循环逐层推进 直到求出目标解的算法。 算法其基本思想是把一个复杂的庞大 的计算过程转化为简单过程的多次重复, 该算法充分利用了计算机的运算速度快和 不知疲倦的机器等特点,它能从头开始一 步步地推出问题最终的结果,按照一定的 规律来计算序列中的每个项,通常是通过 计算前面的一些项来得出序列中的指定项 的值。

小技巧
? 如何看出题目采用递推算法? ? 1、数据规模超大,往往无法用搜索或动 规方法。 ? 2、所给条件过少,无法模拟或枚举。

解决递推问题的一般步骤
? 建立递推关系式
? 确定边界条件 ? 递推求解

递推的两种形式
?

顺推法和倒推法

顺 推
? 求和
? 斐波拉契数列 1,1,2,3,5,8,13…

? [例1] 植树节那天,有五位参加了植树活动, 他们完成植树的棵数都不相同。问第一位同 学植了多少棵时,他指着旁边的第二位同学 说比他多植了两棵;追问第二位同学,他又 说比第三位同学多植了两棵;…如此,都说 比另一位同学多植两棵。最后问到第五位同 学时,他说自己植了10棵。到底第一位同学 植了多少棵树?

? 解:设第一位同学植树的棵数为a1,欲求a1, 需从第五位同学植树的棵数a5入手,根据 “多两棵”这个规律,按照一定顺序逐步进 行推算: ? ①a5=10; ? ②a4=a5+2=12; ? ③a3=a4+2=14; ? ④a2=a3+2=16; ? ⑤a1=a2+2=18;

? Pascal程序: ? Program Exam1; ? Var i, a: byte; ? begin ? a:=10; {以第五位同学的棵数为递推 的起始值} ? for i :=1 to 4 do {还有4人,递推计算4次} ? a:= a+2; {递推运算规律} ? writeln(’The Num is’, a); ? readln ? end.

? 本程序的递推运算可用如下图示描述: ? ? 递

推算法以初始{起点}值为基础,用相同 的运算规律,逐次重复运算,直至运算结束。 这种从“起点”重复相同的方法直至到达一 定“边界”,犹如单向运动,用循环可以实 现。递推的本质是按规律逐次推出(计算) 下一步的结果。

例题2:faibonacci数列
【问题描述】已知faibonacci数列的前几个数分 别为0,1,1,2,3,5,……编程求出此数列 的第n项。(n<=60)
? a[1]:=0;a[2]:=1; ? for i:=3 to n do a[i]:=a[i-2]+a[i-1];

?思考:当n<=109时,如何求解?

? ? ? ? ? ? ? ? ? ? ?

递推: Function fib(n:integer):integer; Var I,a,b,c:integer; Begin a:=0; b:=1; for i:=3 to n do begin c:=a+b; a:=b; b:=c; end; fib:=c; End;

逆推
例3、猴子吃桃 ? 第一天,x个桃 ? 第二天,吃一半多一个 ? 第三天,再吃剩下的一半多一个 ? …… ? 第十天,发现只剩下一个 ? 问第一天x是多少?

两种递推的比较
? 从已知条件出发,求什么结束来 判断采用哪种更合适方便 ? 都用循环来实现,而循环的条件 是边界条件 ? 递推往往是一种分析解题的思 路.

例题4:路径计数1

? ? ? ? ? ? ?

readln(n); for i:=1 to n do begin a[1,i]:=1;a[i,1]:=1;end; for i:=2 to n do for j:=2 to n do a[i,j]:=(a[i-1,j]+a[i,j-1])mod 100003; writeln(a[n,n]);

? 例题4 : Hanoi塔问题 . Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c 组成。开始时,这n个圆盘由大到小依次套在a柱上, 如图1所示。要求把a柱上n个圆盘按下述规则移到c 柱上: (1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上,总计需要移 动多少个盘次?

a

b

c

分析
当n=1时:A?C 当n=2时:A?B,A?C,B?C 当n=3时:

A
1 2 3

B

C

分析
? ? ? ? ?
? ? ? ?

设f(n)为n 个盘子从1柱移到3柱所需移动的最少盘次。 当n=1时,f(1)=1。 当n=2时,f(2)=3。 以此类推,当1柱上有n(n>2)个盘子时,我们可以利用下列步骤: 第一步:先借助3柱把1柱上面的n-1个盘子移动到2柱上,所需的 移动次数为f(n-1)。 第二步:然后再把1柱最下面的一个盘子移动到3柱上,只需要1 次盘子。 第三步:再借助1柱把2柱上的n-1个盘子移动到3上,所需的移动 次数为f(n-1)。 由以上3步得出总共移动盘子的次数为:f(n-1)+1+ f(n-1)。 所以:f(n)=2 f(n-1)+1

hn=2hn-1+1 =2n-1 边界条件:h1=1


网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com