递推法解题
超大声手机铃声-
递推法解题
基础知识
对于某些与自然数有关的问题，
我们有时可以用递推法解决，
扎谓用递推法解题，
就是
根据题目的特点，<
/p>
构造出递推关系解题的一种方法，
解决问题的关键在于构造递推关
系。
递
推关系一般可以用归纳、猜想等途径获得。
利用递推法解题的一般步骤为：
(1)
确定初始值；
(2)
建立递推关系；
(3)
利用递推关系求
通项。
递推方法是人们从开始认识数量关系时就很自然地产生的一种推理思想
.
例如自然数中
最小的数是
1
，
比
1
大<
/p>
1
的数是
2
，<
/p>
接下来比
2
大
1
的数是
3
，
…
由此得到了自然数数列：
1
，
2
，
3
，
4
，
5
，…
.
在这里实际上就有了一个递推公式，假设第
n
个数为
a
n
，则
a<
/p>
n+1
=a
n
+
1;
即
由自然数中第
n
个数加上
1
，就是第
n+1
个数。由此可得
a
n
＋
2
=a
n
＋
1
＋
1
，
这样
就可以得到自然数数列中任何一个数
.
再看一个例子：
平面上
5
条直线最多能把圆的内部分成几部分？平面上
10
0
条直线最多能把圆的内部
分成几部分？
解：假设用
< br>a
k
表示
k
条直线最多能把圆的内部分成的部分数
.
这里
k
＝
0
，
< br>1
，
2
，…
.
a
0
＝
1
a
1
=a
0
+1
＝
2
a
2
=a
1
＋
2=4
a
3
=a
2
＋
3=7
a
4
=a
3
+4
＝
11
…
归纳出
递推公式
a
n
＋
1
＝
a
n
+
n.
（
1
）
即画第
n
＋
1
条直线时，最多增加
n
部分
.
原因是这样的：第
一条直线最多把圆
分成两部分，故
a1
＝
2.
当画第二条直线时要想把圆内部分割的部分尽可能多，就
应
和第一条直线在圆内相交，交点把第二条直线在圆内部分分成两条线段，而每条线
段又把原来的一个区域划分成两个区域，因而增加的区域数是
2
，正好等于第二条
直线的序号
.
同理，当画第三条直线时，要想把圆内部分割的部分数尽可能多，它就
应和
前两条直线在圆内各有一个交点
.
两个交点把第三条线在圆内部
分成三条线段
.
而每条线段又把原来一个区域划分成两个区域<
/p>
.
因而增加的区域部分数是
3
，正好等
于第三条直线的序号，…
.
这个道理适用于任意多条直线的情形
.
所以递推公式
（
1
）
是正确的
.
这样就易求得
5
条直线最多把圆内
分成：
a
5
=a
4
+
5
＝
11=5
＝
16
（部分）
。
要想求出
100
条直线最多能把圆内分成多少区域，就去求通项公式。
一般来说，如果一个与自然数有关的数列中的任一项
a
n
可以由它前面的
k
（
≤
n-1
）项经
过运算或其他方法表示
出来，我们就称相邻项之间有递归关系，并称这个数列为递归数列
.
1
如果这种推算方法能用公式表示出来，就称这种公式
为递推公式或递推关系式
.
通过寻求递
归关系来解决问题的方法就称为
递推方法
.
许多与自然数有关的数学问题都常常具有递推关系，
可以用递推公式
来表达它的数量关
系
.
如何寻求这个递
推公式是解决这类问题的关键之一，常用的方法是“退”到问题最简单
情况开始观察
.
逐步归纳并猜想一般的速推公式
.
在小学生阶段，我们仅要求学生能拨开问题
的一些表面现象由简到繁地
归纳出问题的递推公式就行了，不要求严格证明
.
当然能证明更
好
.
所谓证明，
就是要严格推出你建立的关系式适合所有的
n
，
有时，
仅仅在前面几项成立的
关系式，不一定当
n
较大时也成立。
1
、
“河内塔问题”
传说在印度的佛教圣
地贝拿勒斯圣庙里安放着个一个黄铜板，板上插着三根宝石针，
在第一根宝石针上，
从下到上穿着由大到小的
64
片中心有孔的
金片
.
每天都有一个值班僧侣
按下面规
则移动金片：把金片从第一根宝石针移到其余的某根宝石针上
.
要求一次只能移动
一片，
而且小片永远要放在大片的上面
.
当时传说当
64
片
金片都按上面的规则从第一根宝石
针移到另一根宝石针上时，世界将在一声霹雳中毁灭<
/p>
.
所以有人戏称这个问题叫“世界末日”
问题（也称为“
Hanoi
塔”问题），当然，移金片和世界毁
灭并无联系，这只是一个传说而
已，但说明这是一个需要移动很多很多次才能办到的事情
.
解这个问题的方法在算法分析中
也常
用到
.
究竟按上述规则移动完成
64<
/p>
片金片需要移动多少次呢？
将此问题一般化为：
设有
n
个银圈，
大小不同，
从
大到小排列在三根金棒中的一根。
这些银圈要搬到另一根
金棒上
，
每次搬一个。
第三根金棒作为银圈暂时摆放用。
在搬动过程中，
仍要保持大圈在下，
小圈在上，
问要搬动多少次，
才能将所有银圈从一根棒搬到另一根，
且搬完后银圈相对位置
不变？
< br>思路：寻找
a
n
与前面各项之间
的关系，由题设条件列出等式。
解：令用
a
n
表所求的搬动次数，把第一棒
n
个银圈的
n
1
个搬到第三棒，再将最大一
个银圈搬到第二棒，然后又将第
三棒上的
n
1
个圈搬到第二棒上，如此继续，可完成这次
搬动任务。
因为搬
n
1
个银圈从一棒到另一棒需
a
n
1
次，故可得递推式
a<
/p>
n
2
a
n
1
1
,
a
1
1
。
下面对递推式
a
n
2
a
n
< br>1
1
,
a
1
1
的
求解。
n
最后，可得
a
n
2
1
。
典例分析
例
1
．用
100
元人民币购买物品，规定
每天只能用以下三种方式之一购买物品：
(1)
买甲物品
1
元；
(2)
买乙物品
2
元；
(3)
买丙物品
2
元
而且规
定不允许不买物品。试问有多少种方式花完这
100
元钱？
2