递推的方法
王朝霸域图标怎么点亮-
第一讲
递推的方法
知识要点和基本方法
有时，
我们会遇上一些具有规律性的数学问题，
这就需要我们在解题时根据已知
条件尽
快地去发现规律，并利用这一规律去解决问题。
例如：按规律填数：
1
，
4
，
9
，
16
，
25
，
（
）
，
49
，
64
；
分析：
要在括
号填上适当的数，
就要正确判断出题目所呈现出的规律。
若你仔
细地观察
这一数列，就会发现这些数之间的规律：
⑴先考虑相邻两个数之间的差，依次是
3
，
5
，
7
，
9
，……，
15
；可以看
到相邻两数的
差从
3
开始呈现递增
2
的规律，所以括号里的数应是
25+11
=36
，再看
36+13=49
得到验
证。
⑵如果我们换一个角度去考虑，
那么我们还可以发现，
这数列的第一项是
1
的平方，
第
二项是
2
的平方，
第三项是
3
的平方
，
……，
从这些事实中，
发现规律是第
n
项是
n
的平
方。
那么所求的是第六项是
6
2
=36
。
我们把相
邻数之间的关系称为
递归关系
，
有了递
归关系可以利用前面的数求出后面的未
知数。象这种解题方法称为
递推法
。
例题精讲
例
1 999
…
999
×
999
…
< br>999
的乘积中有多少个数字是奇数？
10
个
9
10
个
9
分析
<
/p>
我们可以从最简单的
9
×
9
的乘积中有几个奇数着手寻找规律。
9
×
9=81
，有
1
个
奇数；
99<
/p>
×
99=99
×（
100-1
）
=9900-99=9801
< br>，有
2
个奇数；
999
×
999=999
（
1000-1
）
=999000-999=998001
，
有
3
个奇数；
……
<
/p>
从而可知，
999
…
999
×
999
…
999
的乘积中共有
10
个数
字是奇数。
10
个
9
10
个
9
例
2
如图所示：线段
AB
上共有
10
个点（包括两个端点）那么这条线段上一共
有多
少条不同的线段？
A
a
1
a
2
a
3
a
4
a
5
a
6
a
7
a
8
B
分析
先从
AB
之间只有一个点开始，在逐步增加
AB
之间的点数，找出点和线段之间
的规律。
< br>
我们可以采用列表的方法清楚的表示出点和线段数之间的规律。
AB
之间只有
1
个
点：线段有
1+2=3
条。
AB
之间只有
2
个
点：线段有
1+2+3=6
条。
AB
之间只有
3
个点：线段有
1+2+3+4=10
条。
AB
之间只有
4
个
点：线段有
1+2+3+4+5=15
条。
……
不难发现，当
AB
之间有
8
个点时，线段有
1+2+3+4+5+6+7+8+9=45
条。
若再进一步研究可得出这样得规律
，线段数
=
点数×（点数
-1
）÷
2
。
例
3
计算
1<
/p>
3
+2
3
+3<
/p>
3
+4
3
+5<
/p>
3
+6
3
+7<
/p>
3
+8
3
+9<
/p>
3
+10
3
得值
。
分析
这是一道特殊的计算题，
当然我们可以采用分别求出每个数的立
方是多少再求和
计算出这题的结果。这样的计算工作量比较大，是否可以采用其它较简便
的方法计算呢
下面我们就来研究这个问题。
1
3
+2<
/p>
3
=
（
1+2<
/p>
）
2
；
1
3
+2
3
+3
3
=
（
1+2+3
）
2
；
1
3
+2
3
+3
3
+4
3
=
（
1+2+3+4
）
2
；
……
这样我们可以容易地得到
1
3
+2
3
+3
3
+4
3
+5
3
+6
3
+7
3
+8
3
+9
3
+10
3
=
（
1+2+3+4+5+6+7+8+9+10
）
2
=
55
2
= 3025
< br>通过这个例题我们可以得到
1
3
+2
3
+3
3
++
……
+n
3
=
（
1+2+3+
…
+n
）
2
例
4
2000
个学生排成一行，依次从左
到右编上
1
～
2000
号，然后从右到左按一、二
报数，报一的离开队伍，剩下的人继续按一、二报数
，报一的人离开队伍，……按这个规律
如此下去，直至当队伍只剩下一人为止。问：最后
留下的这个人原来的号码是多少？
分析
我们通过前几次留在队伍中的学生的编号找出规律。
第一次留下的学生编号是：
2
，
4
，
6
，
8
，
10
，……；
都是
< br>2
的倍数。即
2
1
的倍数
第二次留下的学生编号是：
4
，
8
，
12
，
16
，
20
，……；
都是
4
的倍数，即
2
2
的倍数
第一次留下的学生编号是：
8
，
16
，
24
，
32
，
40
，……；都是
8
的倍数
。即
2
3
的倍数
……
由于
2
10
=1024
＜
2000
＜
2
11
=2048
；
这样可知
，最后留下学生的号码一定是
1024
。
例
5
圆周上两个点将圆周分为两半，在这两点上写上数
1
；然后将两段半圆弧对分，
在两个分点上写上相邻两点上的数之和；
再把
4
段圆弧等分，
在分点上写上相邻两点上的数
之和，如此继续下去，问第
6
步后，圆周上所有点上的之和是多少？
分析
先可以采用作图尝试寻找规律。
第一
步，圆周上有两个点，第二步有四个点，第三步有八个点，第四步有十六个点，
……，第六步有
32
个点。
< br>
2
2
3
3
1
1
1
1
1
1
3
3
2
2
因为问题是求圆周上所有数的和，
所以我们不必去考虑每一步具
体增加了哪些数，
只须
知道每一步增加数的总和是多少。
第一步：圆周上有两个点，两个数的和是
1
+1=2
；
第二步：
圆周上有四个点，
四个数的和是
1+1+2+2=6<
/p>
；
增加数之和恰好是第一步圆周上
所有数
之和的
2
倍。
第三步：圆周上有八个点，八个数的和是
1+1+2+2+3+3+3+3=18
，增加数之和恰好是第
二步数圆周上所有数之和的
< br>2
倍。
第四步：圆
周
上
有
十
六
个
点
，
十
六
个
数
的
和
是
1+1+2+2+3+3+3+
3+4+4+4+4+5+5+5+5=54
，
增加数之和恰好是第三步数圆周上所有数之和的
2
倍
。
……
这样我们可以知道，圆周上所有数
之和是前一步圆周上所有数之和的
3
倍。用递推法关
系表示。
设
a
n
为第
n
步后得出的圆周上所有数之和，则<
/p>
a
n
=3
×
a
n
－
1
利用上式可以得到：
a
n
=3<
/p>
×
a
n
－
1
=3
×
3
a
n
－
2
=3
×
3
×
3
a
n
－
3
=
……
=3
×
3
×……×
3
< br>a
1
（
n
－
1
）
个
3
因为
a
1
=2
，所以：
（
）
a
n
=3<
/p>
×
3
×……×
3
a
1
=3
6-
1
×
2=486
。
（
n
－
1
）个
3
例
6
4<
/p>
个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由
甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？
分析
< br>设第
n
次传球后，球又回到甲手中的传球方式有
a
n
种。可以想象前
n
-1
次传球，
如果每一次传球都任选其他三人中的一人进行传球
，
即每次传球都有
3
种可能，
由乘法原理，
共有
3
×
3
×……×
3=3
（种）传球方法。这些传球方式并不是符合要求的，它们可以
（
n
－
1
）个
3
分为两类，一类是第
n-1
次恰好传到甲手中，这有
a
n-1
传法，它们不符合要求，因为这样第
n
次无法再把球传给甲；另一类是第
n-1
次传球，球不在甲手中，第
n
次持球人
再将球传给
甲，有
a
n
传法。根据加法原理，有
a
n-1
+
a
n
=3
×
3
×……×
3=3
n-1
。
（
n
－
1
）个
< br>3
由于甲是发球者，一次传球后球又回到甲手中的传
球方式是不存在的，所以
a
1
=0
。
利用递推关系可以得到
a
2
=3-0=3
，
a
3
=3
×
3-3=6
，
a<
/p>
4
=3
×
3
×
3-6=21
，
a
4
=3
×<
/p>
3
×
3
×
3-21=60
。
这说明经过
5
次传球后，球仍回到甲手中的传球方法有
60
种。
当然这题也可以利用列表法求解。
我们可
以这样想，
第
n
次传球后，
球不在甲手中的传球方法，
第
n+1
次传球后球就可能
回到甲手中，所以只需求出第四次传球后，球不在甲手中的
传法共有多少种。
第
n
次
传球
1
2
3
4
5
传球的方法
3
9
27
81
243
球在甲手中
的传球方法
0
3
6
21
60
球不在甲手中
的传球方法
3
6
21
60
183
从图中可以看出经过四次传球后，球仍回到甲手中的传球方法共有
60
种。
A
组
1
、根据各数间的关系，在括号填上一个恰当的数。
⑴
1
，
2
，
6
，
24
，
（
）
，
720
；
⑵
1
，
2
，
4
，
7
，
11
，
16
，
（
）
；
（
1
）⑴<
/p>
120
⑵
22
2
、
1999
1999
< br>的末位数字是几？
（
2
）
1999
1
的末位
数字是
9
；
1999
2
的末位数字是
< br>1
；
1999
3
的末位数字是
< br>9
；
1999
4
的末位数字是
< br>1
；
9
n
次方积的末位数字是
< br>9
，
1
，
9
，
1
，…变化。
< br>
所以当
n=
奇数时，末位数字
是
9
。
当
n=
偶数时，末位数字是
1
。
n=1999
是奇数，所以
1999
1999
的
末位数字是
9
。
3
、如图，从
A
到
B
最短的线路有几条？
B
A
1
（
3
）最
短路线，指的是从
A
到
B
只能向右或向上走。
1
在每个路口，用数字表示
A
点到该路口的最
短的
1
线路的条数，而且每一个路口数字恰好是到这个路口的
前面路口的数字和，这样我们标上到各路口最短线路数，
A
不难推出，从
A
< br>到
B
的最段路线有
20
条。
（如图）
4
3
2
10
6
3
B
20
10
4
1
1
1