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

递推

发布时间:2013-10-22 09:34:52  

递推算法
朱全民

例1.Fibonacci数列
Fibonacci数列的代表问题是由意大利著 名数学家Fibonacci于1202年提出的“兔 子繁殖问题”(又称“Fibonacci问题”)。 ? 问题: 一个数列的第0项为0,第1项为1,以后 每一项都是前两项的和,这个数列就是著 名的裴波那契数列,求裴波那契数列的第 N项。
?

解答
?

由问题,可写出递推方程
1?n ? 0 ? ? ? fn ? ? 2?n ? 1? ? f ? f ?n ? 2 ? n?2 ? n ?1

算法:

F[0] := 1; F[1] := 2; FOR i := 2 TO N DO F[I] := F[I – 1] + F[I – 2];

总结
?

?

从这个问题可以看出,在计算裴波那契数列的每一项目 时,都可以由前两项推出。这样,相邻两项之间的变化 有一定的规律性,我们可以将这种规律归纳成如下简捷 的递推关系式:Fn=g(Fn-1),这就在数的序列中,建立 起后项和前项之间的关系。然后从初始条件(或是最终 结果)入手,按递推关系式递推,直至求出最终结果 (或初始值)。很多问题就是这样逐步求解的。 对一个试题,我们要是能找到后一项与前一项的关系并 清楚其起始条件(或最终结果),问题就可以递推了, 接下来便是让计算机一步步了。让高速的计算机从事这 种重复运算,真正起到“物尽其用”的效果。

递推概念
?

给定一个数的序列H0,H1,…,Hn,…若存在 整数n0,使当n>n0时,可以用等号(或大于 号、小于号)将Hn与其前面的某些项 Hn(0<i<n)联系起来,这样的式子就叫做 递推关系。
如何建立递推关系 ? 递推关系有何性质 ? 如何求解递推关系
?

递推的形式
?

顺推法和倒推法

例1:昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫, 这种昆虫的繁殖能力很强。每对成虫过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月)的成虫个数
月份
成虫

1

2
2 1

3
2 1

4
2 3

5
6 5

6

7

8
26 23

9
46 37


… …

新增卵 0 1

10 14 7 13

分析
设数组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+2<=z+1) ? 因为A [i]的求得只与A[1]~A[i-1]有关,即可用递推求法。 ? 则总共的成虫个数为:
?

ans ? ? A[i]
i ?1

z ?1

例2 : Hanoi塔问题
?

Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。 开始时,这n个圆盘由大到小依次套在a柱上,如图1所 示。要求把a

柱上n个圆盘按下述规则移到c柱上:
(1)一次只能移一个圆盘; (2)圆盘只能在三个柱上存放; (3)在移动过程中,不允许大盘压小盘。

?

问将这n个盘子从a柱移动到c柱上,总计需要移动多少 个盘次? a b c

图1

分析
?

设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然, 当n=1时,只需把a 柱上的盘子直接移动到c柱就可以了, 故h1=1。当n=2时,先将a柱上面的小盘子移动到b柱上 去;然后将大盘子从a柱移到c 柱;最后,将b柱上的小 盘子移到c柱上,共记3个盘次,故h2=3。以此类推,当 a柱上有n(n>=2)个盘子时,总是先借助c柱把上面的n-1 个盘子移动到b柱上,然后把a柱最下面的盘子移动到c 柱上;再借助a柱把b柱上的n-1个盘子移动到c柱上;总 共移动hn-1+1+hn-1个盘次。

?
?

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

例3 :平面分割问题
?

设有n条封闭曲线画在平面上,而任何两条封闭曲线恰 好相交于两点,且任何三条封闭曲线不相交于同一点, 问这些封闭曲线把平面分割成的区域个数。

分析
?

? ?

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

例4:贮油点
?

?

一辆重型卡车欲穿过1000公里的沙漠,卡车耗汽油为1 升/公里,卡车总载油能力为500公升。显然卡车装一次 油是过不了沙漠的。因此司机必须设法在沿途建立若干 个贮油点,使卡车能顺利穿过沙漠。试问司机如怎样建 立这些贮油点?每一贮油点应存储多少汽油,才能使卡 车以消耗最少汽油的代价通过沙漠? 编程计算及打印建立的贮油点序号,各贮油点距沙漠边 沿出发的距离以及存油量。格式如下:
? ? ? ?

No. Distance(k.m.) 1 × × 2 × × … ……

Oil(litre) ×× ×× ……

分析
?
? ? ?

设Way[i]——第i个贮油点到终点(i=0)的距离; oil[i]——第i个贮油点的贮油量; 我们可以用倒推法来解决这个问题。从终点向始点倒推, 逐一求出每个贮油点的位置及存油量。 从贮油点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[1]=500;oil[1]=500;
?

倒推第二步
为了在i=1处贮藏500公升汽油,卡车至少从I=2处开两 趟满载油的车至i=1处,所以i=2处至少贮有2*500公升 汽油,即oil[2]=500*2=1000;另外,再加上从i=1返回 至i=2处的一趟空载,合计往返3次。三次往返路程的耗 油量按最省要求只能为500公升,即d1,2=500/3km, Way[2]=Way[1]+d1,2=Way[1]+500/3

倒推第三步
?

?

为了在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]+d2,3=Way[2]+500/5;

倒推第k步
?
?

?

…… 为了在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) Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1);

i=n的情形
?

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)。

问题讨论1:青蛙过河(Frog )
?

大小各不相同的一队青蛙站在河左岸的石墩(记为A) 上,要过到对岸的石墩(记为D)上去。河心有几片菏叶 (分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图 示如下:
荷叶Yi 左岸石墩A 右岸石墩D

河心石墩Sj

试题描述
? 1. 2. 3. 4. 5. 6.

7. 8. 9.

青蛙的站队和移动方法规则如下: 每只青蛙只能站在荷叶、石墩,或者仅比它大一号的青蛙背上 (统称为合法的落脚点); 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到 另一个落脚点; 青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上, 允许从河心的石墩和荷叶跳到右岸的石墩D上; 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回 跳动; 青蛙在离开左岸石墩后,不能再返回左岸;到达右岸后,不能再 跳回; 假定石墩承重能力很大,允许无论多少只青蛙都可呆在上面。但 是,由于石墩的面积不大,至多只能有一只青蛙直接站在上面, 而其他的青

蛙只能依规则1落在比它大一号的青蛙的背上。 荷叶不仅面积不大,而且负重能力也有限,至多只能有一只青蛙 站在上面。 每一步只能移动一只青蛙,并且移动后需要满足站队规则; 在一开始的时候,青蛙均站在A上,最大的一只青蛙直接站在石墩 上,而其它的青蛙依规则6站在比其大一号的青蛙的背上。

试题描述
青蛙希望最终能够全部移动到D上,并完成站队。 ? 设河心有m片荷叶和n个石墩,请求出这队青蛙至多有 多少只,在满足站队和移动规则的前提下,能从A过到 D。 [输入文件] 文件仅有两行,每一行仅包含一个整数和一个换行/回 车符。第一行的数字为河心的石墩数n(0<=n<=25), 第二行为荷叶数m(0<=m<=25)。 [输出文件] 文件中仅包含一个数字和一个换行/回车符。该数字为 在河心有n个石墩和m片荷叶时,最多能够过河的青蛙 的只数。
?

计算河心n个石礅可承载的最大青蛙数
设f[i]表示河心i个石礅可承载的最大青蛙数(1<=i<=n) 左岸为A,右岸为D (1) 0个石礅,f[0]=0 (2) 1个石礅,f[1]=m+1 (3) 2个石礅s1,s2,f[2]=? (1)A上m+1只青蛙?s1 (2) A上m+1只青蛙? s2 , (3)s1上的m+1青蛙? s2 (4) A上m+1只青蛙?s1 因此,f[2]=m+1+f[1]+f[1]=3*(m+1) (4) 3个石礅s1,s2,s3, (1)A上3(m+1)只青蛙?s1,s2 (2) A上m+1只青蛙? s2 , (3)s1,s2上的3(m+1)青蛙? s2 (4) A上3(m+1)只青蛙?s1,s2 因此,f[3]=m+1+2*f[2]=7*(m+1) …… (5) n个石礅? (1)A上f(n-1)只青蛙?s1…sn-1 (2) A上m+1只青蛙? sn (3)s1…sn-1上的f(n-1)只青蛙?sn (4) A上f(n-1)只青蛙?s1…sn-1 因此, f[n]=m+1+2*f[n-1]

计算能过河青蛙的最大值
? ? ? ?

f(n)只青蛙移到河心的石礅后,按照站队和移动规则,首先应该将 A上的m+1只青蛙移到D 设g(n)表示n个石礅,m片荷叶,能过河青蛙的最大值,则 g(n)=m+1+f(n) 由于f(n)=m+1+2*f(n-1),可以递推求出,当然,可以求出g(n). 实际上f(n)=m+1+2*f(n-1)也可以通过化简得出公式 f(0)=0 f(1)= m+1 f(2)= m+1+2*f(1)=(m+1)*(1+2) f(2)= m+1+2*f(1)=(m+1)*(1+2+22) f(3)= m+1+2*f(1)=(m+1)*(1+2+22+23)

…… f(n)=m+1+2*f(n-1)=(m+1)*(1+2+22+23+…+2n-1) =(m+1)* (2n -1) 因此 g(n)=(m+1)*2n

分析
(4)3个石礅s1,s2,s3, (1)A上3(m+1)只青蛙?s1,s2 (2) A上m+1只青蛙? s2 , (3)s1,s2上的3(m+1)青蛙? s2 (4) A上3(m+1)只青蛙?s1,s2 因此,f[3]=m+1+2*f[2]=7*(m+1) …… (5)n个石礅? (1)A上f(n-1)只青蛙?s1…sn-1 (2) A上m+1只青蛙? sn (3)s1…sn-1上的f(n-1)只青蛙?sn (4) A上f(n-1)只青蛙?s1…sn-1

问题讨论2:2k进制数
设r是个2k 进制数,并满足以下条件: (1)r至少是个2位的2k 进制数。 (2)作为2k进制数,除最后一位外,r的每一位 严格小于它右边相邻的那一位。 (3)将r转换为2进制数q后,则q的总位数不超 过w。 ? 在这里,正整数k(1≤k≤9

)和w(w≤30000) 是事先给定的。 问:满足上述条件的不同的r共有多少个?

举例
?

?

?

?

设k=3,w=7。则r是个八进制数(23=8)。由于w=7, 长度为7的01字符串按3位一段分,可分为3段(即1,3, 3,左边第一段只有一个二进制位),则满足条件的八 进制数有: 2位数:高位为1:6个(即12,13,14,15,16, 17),高位为2:5个,…,高位为6:1个(即67)。 共6+5+…+1=21个。 3位数:高位只能是1,第2位为2:5个(即123,124, 125,126,127),第2位为3:4个,…,第2位为6: 1个(即167)。共5+4+…+1=15个。 所以,满足要求的r共有36个。

分析(1)
?

设M=2k,令A= an?1an?2 ...a2a1a0 为一个满足条件的 M进制数,先不看第三个位数限制的条件,原 来的两个条件可以翻译为: (1)an-1>0,n>1 (2)ai<ai-1 这些条件是否满足是很好判断的。 现在考虑A,若它的位数多于两位,即n>2,则将 它的最高位即an-1去掉,为A’,由0<an-1<an-2, 可知an-2>0,由此可进一步证明A’也满足这两个 条件。当然,很容易证明,A’会满足位数限制 条件。

分析(2)
?

首先来计算an-1为一个固定值的M进制数的总数。 设an-1=V1,则an-2可以取V1+1到M-1中的任何数, 当an-2取V2(在V1+1到M-1中)时,其总数对应于 n’=n-1,an’-1=V2时的数的总数,这是一个更小规 模的子问题。不难想到,如果用T[n,V1]表示位 数为n的M进制数,最高位的值为V1,且满足题 设条件的M进制数的总数,则得到递推公式
T [n,V1 ] ?
M ?1 V2 ?V1 ?1

?

T [n ? 1,V2 ]

分析(3)
?

令函数S[n,V1]表示位数为n的M进制数,最高位 的值不小于V1,且满足题设条件的M进制数的 总数,则 T[n,V1]=S[n-1,V1+1],
S[n,V1 ] ?
M ?1 V ?V1

? T[n,V ] ? S[n,V ? 1] ? T [n,V1]
1

边界条件: T[1,V1]=1 (1<=V1<M) S[n,M]=0

分析(4)
? ?

现在我们能计算出任何T[n,V1]的值,是否可以计算出 原问题的解呢? 可以!首先看一下两位M进制数中满足条件的数的个数 (暂不考虑w<2k的情况):最高位可以取1到M-1。其满 足题设条件的数的总数应该是
M ?1 V ?1

? T [2,V ] ? S[2,1]

同样的,当w>=nk时,n位满足条件的数应该为S[n,1]。现在, 所以位数小于[w/k]的数都找出来了,只要找位数等于[w/k] 的数。同样,只要枚举最高位就可以得出解,由于M正好为2 的整幂,所以最高位的取值范围是可以算出来的,设能取的 最大值为U,则倍数正好为[w/k]位的满足条件的数的总数为
? w? T [ ? ? ,V ] ? ?k ? V ?1
U

分析(5)
计算T的复杂度是O(2k * w/k * 高精度),较高! 一个很直接的问题就是w/k很大,但实现上,由 于k最大为9,即M最大为512,当w/k超过512 时,就不会存在满足条件的方案了。所以, w<=30000并没有什么

意思,可以认为w/k是 <=2k的。这样,时间复杂度为O(22k *高精度), 已能满足条件。 ? 空间上,观察T和S的公式,T[n]只与S[n-1]有 关,而S[n]只与T[n]有关,所以可以利用两个 滚动数组来存储T与S,所需要的空间为O(2k * 高精度),已能满足题设要求。
? ?


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