2022-2023学年奥数专家点拨小学五年级下册《递推方法》试题附答案

状元必读专家点缓

小学五年级下册数学奥数知识点讲解第13课《递推方法》试题附答案

第十四讲递推方法

递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例

如自然数中最小的数是1,比1大1的数是2,接下来比2大1的数是3,…由此得

到了自然数数列：1,2,3,4,5,….在这里实际上就有了一个递推公式，假

设第n个数为5则

an-l=an+1

即由自然数中第n个数加上1,就是第n+l个数。由此可得

4+2=4+I+1，

这样就可以得到自然数数列中任何一个数

再看一个例子：

例1平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把

囱的内部分成几部分？

例2平面上10个两两相交的圆最多能将平面分割成多少个区域？平面上1993个

圆最多能将平面分割成多少个区域？

例3在一个圆周上按下面规则标上一些数：第一次先把圆周二等分，

在两个分点旁标上q和右如图（a）.第二次把两段半圆弧二等分，在

分点旁标上相邻两分点旁所标两数的和，如图（b）,标上亮［;+g）第

三次把4段圆弧分别二等分，并在4个分点旁边标上两个相邻分点旁所

标数的和，如图G）,分别标上中f斜出3|）.如此继续下

去，当第八次标完数以后，圆周上所有己标的数的和是多少?

例5传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插

着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64片中心

有孔的金片.每天都有一个值班僧侣按下面规则移动金片：把金片从第一

根宝石针移到其余的某根宝石针上.要求一次只能移动一片，而且小片永

远要放在大片的上面.当时传说当64片金片都按上面的规则从第一根宝石

针移到另一根宝石针上时，世界将在一声霹雳中毁灭.所以有人戏称这个

问题叫“世界末日”问题（也称为“Han。谐”问题），当然,移金片和

世界毁灭并无联系，这只是一个传说而己，但说明这是一个需要移动很

多很多次才能办到的事情解这个问题的方法在算法分析中也常用到.究竟

按上述规则移动完成64片金片需要移动多少次呢？解：设有n片金片，把

从第一片金片至第k片金片按题目要求由第4艮宝石针移到另一根宝石针共

需移动4次。

先对4片金片的简单情形用下列的几组图来表示移动过程中的各种状

态，并计数，归纳出递归关系式。

答案

笫十四讲递推方法

递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想.例

如自然数中最小的数是1,比1大1的数是2,接下来比2大1的数是3,…由此得

到了自然数数列：1,2,3,4,5,….在这里实际上就有了一个递推公式，假

设第n个数为4则

an，l=an+1

即由自然数中第n个数加上1,就是第n+1个数。由此可得

4.+2=4+i+1,

这样就可以得到自然数数列中任何一个数

再看一个例子：

例1平面上5条直线最多能把圆的内部分成几部分？平面上100条直线最多能把

圆的内部分成几部分？

解:

假设用与表示k条直线最多能把圆的内部分成的部分数.这里k=0,1,2,

…一如图可见。

,=]

4=3c+1=2

,二己工+2=4

a3=a-+3=7

a4=a3+4=11

归纳出递推公式4+1=4rI.（1）

即画第n+1条直线时，最多增加n部分原因是这样的：第一条直线最多把

圆分成两部分，故a,=2.当画第二条直线时要想把圆内部分割的部分尽可能

多，就应和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线

段，而每条线段又把原来的一个区域划分成两个区域，因而增加的区域数是

2,正好等于第二条直线的序号祠理，当画第三条直线时，要想把圆内部分割

的部分数尽可能多，它就应和前两条直线在圆内各有一个交点.两个交点把第三

条线在圆内部分成三条线段.而每条线段又把原来一个区域划分成两个区域.因

而增加的区域部分数是3,正好等于第三条直线的序号，….这个道理适用于任

意多条直线的情形所以递推公式（1）是正确的.这样就易求得5条直线最多把

圆内分成：

a5=a4+5=11=5=16（部分）。

要想求出100条直线最多能把圆内分成多少区域，不能直接用上面公式

了，可把上面的递推公式变形：

+=

aJ.=a,-liinI1_-+（n-1）+n

=a*-3+(n-2)+(n-n)也

=•••=1+1+2+…+n=l+n'n：D(2)

2

100X101…八、

..a100=H------------=5051(部分)o

公式（2）也称为数列1,2,4,7,11,16,…的通项公式

一般来说，如果一个与自然数有关的数列中的任一项与可以由它前面的k

«n-l）项经过运算或其他方法表示出来，我们就称相邻项之间有递归关系，

并称这个数列为递归数列.如果这种推算方法能用公式表示出来，就称这种公式

为递推公式或递推关系式.通过寻求递归关系来解决问题的方法就称为递推方

法.许多与自然数有关的数学问题都常常具有递推关系，可以用递推公式来表达

它的数量关系.如何寻求这个递推公式是解决这类问题的关键之一，常用的方法

是“退”到问题最简单情况开始观察.逐步归纳并猜想一般的速推公式.在小学

生阶段，我们仅要求学生能拨开问题的一些表面现象由简到繁地归纳出问题的

递推公式就行了，不要求严格证明一当然能证明更好.所谓证明，就是要严格推

出你建立的关系式适合所有的n,有时，仅仅在前面几项成立的关系式，不一定

当n较大时也成立。

例2平面上10个两两相交的圆最多能将平面分割成多少个区域？平面上1993个

圆最多能将平面分割成多少个区域？

解：设平面上k个圆最多能将平面分割成a,部分.我们先“退”到最简单的

情形如图可见

ax=2,a:=4=2+2X1,

a3=8=4+2X2,

a4=14=8+2X3,

ar=ar-l+2(n-1).(3)

(3)是这个问题的递推公式再把它变形为当蹶大时也能方便求出

结果的公式：

4=3sT+2(n-1)

=an..+2[(n-2)+(n-1)]

=a,.-3+2[(n-3)+(n-2)+(n-1)]

=•••=a1+2(1+2+3+,,-+n-2-hi-1)

_n(n-1),

—2o+2oXy——----=n2-n+2o

2

/.a,0=102-10+2=92(个)，

a,993=19932-1993+2=3970058(个)。

关于这个递推公式成立的正确性分析与例1完全类似.比如，第一个圆

显然将平面分为两个区域；当画第二个圆时，应与原来的一个圆有两个

交点，即被第一个圆截成两段弧，而每一段弧将原来的每一个区域分成

两个区域，故区域数增加了2,即增加了原来圆的个数的2倍；当画第三

个圆时，应与原来的两个圆共有4个交点，圆弧被截成4段，而每段弧又

将原来的每个区域分成两个区域，所以区域增加了4,即原来圆的个数的

2倍，…，同理类推，说明递推公式应该是

Wl+2(n-1)。

例3在一个圆周上按下面规则标上一些数：第一次先把圆周二等分，

在两个分点旁标上［和提如图(a),第二次把两段半圆弧二等分，在

分点旁标上相邻两分点旁所标两数的和，如图(b),标上.(=；+§,第

三次把4段圆弧分别二等分，并在4个分点旁边标上两个相邻分点旁所

标数的和，如图G),分别标上中［+W和4fl).如此继续下

去，当第八次标完数以后，圆周上所有己标的数的和是多少?

解:

解：我们一般地设第一次所标的两数分别为a、b,用S,表示第k次标

完后各分点所标数的和.如图可见

Si=a+b,S2=S1+2S1=3S1=3(a+b)。

原因是这样的：S2是两类分点旁的标数和，一类是原来分点所标数

的和S1，另一类是新增分点所标数的和，它正好是由原来各分点所标的数

向左加一次，又向右加一次的和，故新增分点旁所标数的和恰好是原来

所有数之和的2倍2S1，因此有

S2=S1+2S1=3SJ同理类推

S3=S2+2S2=3s2=32S],

S4=32S1+2X32SI=32S],

Sr311Tsi=3_1（a+b）（4）

（4）式为递推公式：在S1=a+b时己解出的表达式.所谓解

出，即S.直接依赖于n与S,而计算出.不再是$£依赖于Sr-1,S门又依赖于

Si…这样的形式。

例5传说在印度的佛教圣地贝拿勒斯圣庙里安放着个一个黄铜板，板上插

着三根宝石针，在第一根宝石针上，从下到上穿着由大到小的64片中心

有孔的金片每天都有一个值班僧侣按下面规则移动金片：把金片从第一

根宝石针移到其余的某根宝石针上.要求一次只能移动一片，而且小片永

远要放在大片的上面.当时传说当64片金片都按上面的规则从第一根宝石

针移到另一根宝石针上时，世界将在一声霹雳中毁灭.所以有人戏称这个

问题叫“世界末日”问题（也称为“Han。谐”问题），当然，移金片和

世界毁灭并无联系，这只是一个传说而己，但说明这是一个需要移动很

多很多次才能办到的事情解这个问题的方法在算法分析中也常用到.究竟

按上述规则移动完成64片金片需要移动多少次呢？解：设有n片金片，把

从第一片金片至第k片金片按题目要求由第4艮宝石针移到另一根宝石针共

需移动4次。

先对4片金片的简单情形用下列的几组图来表示移动过程中的各种状

态，并计数，归纳出递归关系式。

W=4n［帘一片壮到JL

初始状壬币=i

第!/；,皿第一片移到HL

卷到皿（第1、2片格

到D［充成）

a

a2=2zi+1

二3（次J

第3井1亚第DL在上的研片移到1L

百到U上,第1、2、3片移到

上完成

第4片I1皿第U柱上的两片移到亚

苍到亚上,第1、2、3、片移

到柱皿上先成

2----84=2打+1

=15（次j

这节的前几个例子都是“退''到简单的特殊情况来归纳出一般规律.

在这个例子里，我们将先用一般推理得出递推公式，再以n=64代入，便

可解决我们这个例题.这种从一般到特殊来解决问题的方法也是数学上的

一种常用方法。

我们可以这样来想：为了移动第n片到第山根宝石针上，我们必须先

把它上面的nJ片按题目的规则采用某种程序移到第II根宝石针上，这需

要移动an-1次.然后才能把最下面第n片（最大的），称到第IH根宝石针上.

最后再经过4-1次才能把第II根宝石针上的nJ片金片按上面规则采用同样

程序移到第而根宝石针上因此把n片金片按题中的规则全部移到另一根宝

石针上共应移

4=231rl+1（次）.（5）

这就是递推公式。为了求得n=64时匕的值，我们当然不能一次次地

由a1=La*3,a3=7,…直到算出也现龙我们设法把递推公式（5）变形

为由以直接计算〜的形式。

二,=24-1+1=2（2a,,.:+1）+1=224.1+2+1

=22（2an-3+l）+2+1=23ali-3+22+2J1

=2*-呵+2丁2+21r3+―+2+1

=l+2+22+-+2n_2+2r-l,

•'•4=2'-4

=2（1+2+22+,•,+2B-1）-（1+2+…+2，）

=2:1，

.,.、=2丈1。

不是一个非常大的数.如果按每移动一片次需一秒钟算，把64片金片

从一根宝石针移到另一根宝石针上大约需要580陀年。

习题十四

1.请你根据下列各个数之间的关系，在括号里填上恰当的数:

①1,5,9,13,17,()。

③22幺上…3

10T6'22'28'58'

②6625,1.25,2.5,5,()。

④198,297,396,495,(),()。

一►22f23-----------

8f9f1

12

1—1

>

1—2

►

16-15—14—

2.将自然数1,2,3,…，按图排列，在“2”处转第一个弯，“3”处转第

二个弯，“5”处转第三个弯，….问哪个数处转第二十个弯？

3.请用速推方法求出甲、乙、丙、丁四人站成一排照相，共有多少种不同

站法？

4.上一段12级楼悌，规定每一步只能上一级或两级.问要登上第12级楼梯共

有多少种不同走法？

5.有10个村庄，分别用A/A:,•••,\：表示，某人从A1出发按箭头方向绕

一圈最后经由A1：再回到A】，有多少种不同走法？

注：每点(村)至多过一次，两村之间，可走直线，也可走圆周上弧线,

但都必须按箭头方向走.

五年级奥数下册：第十四讲递推方法习题解答

习题十四解答

1.①;相邻两数的差均为4,故括号里应填17+4=21o

②：1.25-0.625=0.625,

2.5-1.25=1.25,

3.525=25

可见差正好等于减数。

()-5=5,

/.()=5+5=10。

或者：后一个数为前一个数的2倍，故

括号里应填2X5=10。

③:从数列可见分子从2开始逐个增大15分母从10开始逐个增

大6,要填()，须先知道二^是第几个数.分母顺序为：10,16,

JO

22,28,34,40,46,52,58。

..・这个分数为第9个数。

..•括号里应填10。

④十位上数不变，百位上数依次递增1,个位上数依次递减1,故括号中数

应填594,693。

2.解：拐弯处数的规律可见下页表。

拐弯处序号拐弯处的数前后关系

①21+①=2

②32+9=3

③53+②=5

75+②=7

⑤107+③=10

⑥1310+③=13

⑦1713+@=17

2117+④=21

・•.第19个拐弯处的数比第18个拐弯处的数大10,第20个拐弯处的数比第19

个拐弯处的数也大10,故第20个拐弯处的数为：

1+2X(1+2+3+-+10)=111。

3解：假设n个人站成一排共有4种不同站法.可以先让其中的n-l个人站成

一排，共有乙,种不同的站法，再让厕下的那个人站在他们中间或两头，又有n

种站法.由乘法:原理，可得到递推公式：

4=nXj。

又...4=1,

.,.a4=4Xa,=4X3Xa.=4X3X2Xai=4!=24,

4.解：设登上该楼梯共有a.种不同走法，n=l,2,….把上到第遨楼梯的

情形分为两种走法.一类是先上到第n-l级楼梯，然后再上一级，共有4T种走法.

另一类是先上到第n-2级楼梯，然后再上两级，共有a_［种走法.由加法原理，上

到第薇楼梯的走法4满足下列递推关系式：

ar=ar.-l+ar.-2°

又...药=1,&=2,故上楼梯方法数与.依次为1,2,3,5,8,13,21,34,

55,89,144,233,…一

・•・上到第12级楼梯共有233种不同走法。