7-6-4 计数之递推法.教师版

5312487161415326121011241328303164其中经1次操作变为1的1个，即2， 经2次操作变为1的1个，即4， 经3次操作变为1的2个，是一奇一偶，

以后发现，每个偶数可以变成两个数，分别是一奇一偶，每个奇数变为一个偶数，于是，经1、2、…次操作变为1的数的个数依次为：1，1，2，3，5，8，…

这一串数中有个特点：自第三个开始，每一个等于前两个的和，即即经过9次操作变为1的数有34个.

为什么上面的规律是正确的呢？

道理也很简单. 设经过n次操作变为1的数的个数为an,则a1?1，a2?1，a3?2，… 从上面的图看出，an?1比an大.

一方面，每个经过n次操作变为1的数，乘以2，就得出一个偶数，经过n?1次操作变为1；反过来，每个经过n?1次操作变为1的偶数，除以2，就得出一个经过n次操作变为1的数. 所以经过n次操作变为1的数与经过n?1次操作变为1的偶数恰好一样多.前者的个数是an,因此后者也是an个. 另一方面，每个经过n次操作变为1的偶数，减去1，就得出一个奇数，它经过n?1次操作变为1，反过来.每个经过n?1次操作变为1的奇数，加上1，就得出一个偶数，它经过n次操作变为1. 所以经过n次操作变为1的偶数经过n?1次操作变为1的奇数恰好一样多. 而由上面所说，前者的个数就是an?1,因此后者也是an?1.

经过n?1次操作变为1的数，分为偶数、奇数两类，所以an?1?an?an?1，即上面所说的规律的确成立.

【答案】34

【例 11】 有20个石子，一个人分若干次取，每次可以取1个，2个或3个，但是每次取完之后不能留下

质数个，有多少种方法取完石子？（石子之间不作区分，只考虑石子个数） 【考点】计数之递推法 【难度】5星 【题型】解答

【解析】 如果没有剩下的不能使质数这个条件，那么递推方法与前面学过的递推法相似，只不过每次都是前

面3个数相加．现在剩下的不能是质数个，可以看作是质数个的取法总数都是0，然后再进行递推．

【答案】25

7-6-4.计数之递推法.题库 教师版 page 5 of 9

【巩固】有20个相同的棋子，一个人分若干次取，每次可取1个，2个，3个或4个，但要求每次取之后留

下的棋子数不是3或4的倍数，有 种不同的方法取完这堆棋子. 【考点】计数之递推法 【难度】5星 【题型】填空

【解析】 把20、0和20以内不是3或4的倍数的数写成一串，用递推法把所有的方法数写出来：

【答案】54

【例 12】 4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作

为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方法？ 【考点】计数之递推法 【难度】5星 【题型】解答

【解析】 设第n次传球后，球又回到甲手中的传球方法有an种．可以想象前n?1次传球，如果每一次传球都

任选其他三人中的一人进行传球，即每次传球都有3种可能，由乘法原理，共有3?3?3…?3?3n?1(种)

(n?1)个3

传球方法．这些传球方法并不是都符合要求的，它们可以分为两类，一类是第n?1次恰好传到甲手中，这有an?1种传法，它们不符合要求，因为这样第n次无法再把球传给甲；另一类是第n?1次传球，球不在甲手中，第n次持球人再将球传给甲，有an种传法．根据加法原理，有an?1?an?3?3?…?3?3n?1．

(n?1)个3由于甲是发球者，一次传球后球又回到甲手中的传球方法是不存在的，所以a1?0．

利用递推关系可以得到：a2?3?0?3，a3?3?3?3?6，a4?3?3?3?6?21，a5?3?3?3?3?21?60．

这说明经过5次传球后，球仍回到甲手中的传球方法有60种． 本题也可以列表求解．

由于第n次传球后，球不在甲手中的传球方法，第n?1次传球后球就可能回到甲手中，所以只需求出第四次传球后，球不在甲手中的传法共有多少种．

从表中可以看出经过五次传球后，球仍回到甲手中的传球方法共有60种．

【答案】60

【巩固】五个人互相传球，由甲开始发球，并作为第一次传球，经过4次传球后，球仍回到甲手中．问：共

有多少种传球方式？ 【考点】计数之递推法 【难度】5星 【题型】解答

【解析】 递推法．设第n次传球后球传到甲的手中的方法有an种．由于每次传球有4种选择，传n次有4n次

可能．其中有的球在甲的手中，有的球不在甲的手中，球在甲的手中的有an种，球不在甲的手中的，下一次传球都可以将球传到甲的手中，故有an?1种．所以an?an?1?4n．

由于a1?0，所以a2?41?a1?4，a3?42?a2?12，a4?43?a3?52．即经过4次传球后，球仍回到甲手中的传球方法有52种．

7-6-4.计数之递推法.题库 教师版 page 6 of 9

【答案】52

【例 13】 设A、E为正八边形ABCDEFGH的相对顶点，顶点A处有一只青蛙，除顶点E外青蛙可以从

正八边形的任一顶点跳到其相邻两个顶点中任意一个，落到顶点E时青蛙就停止跳动，则青蛙从顶点A出发恰好跳10次后落到E的方法总数为 种． 【考点】计数之递推法 【难度】5星 【题型】填空 【关键词】清华附中 【解析】 可以使用递推法．

回到A 2 6

跳到B或H 1 3

1 4

1 4 14 48

28

8

2

跳到C或G

跳到D或F

停在E

1步 2步 3步 4步 5步 6步 7步 8步 9步

10 34 116

20 68

14 48

其中，第一列的每一个数都等于它的上一行的第二列的数的2倍，第二列的每一个数都等于它的上一行的第一列和第三列的两个数的和，第三列的每一个数都等于它的上一行的第二列和第四列的两个数的和，第四列的每一个数都等于它的上一行的第三列的数，第五列的每一个数都等于都等于它的上一行的第四列的数的2倍．这一规律很容易根据青蛙的跳动规则分析得来． 所以，青蛙第10步跳到E有48?2?96种方法．

【答案】96

【巩固】在正五边形ABCDE上，一只青蛙从A点开始跳动，它每次可以随意跳到相邻两个顶点中的一个上，

一旦跳到D点上就停止跳动．青蛙在6次之内(含6次)跳到D点有 种不同跳法． 【考点】计数之递推法 【难度】5星 【题型】填空

ABECD【解析】 采用递推的方法．列表如下：

跳到A

2 5 13

跳到B

跳到C

1步 2步 3步 4步 5步 6步

跳到E

停在D

1 1

1 1

1 2 2

3 5 5

3 8

3 8

其中，根据规则，每次可以随意跳到相邻两个顶点中的一个上，一旦跳到D点上就停止跳动．所以，

7-6-4.计数之递推法.题库 教师版 page 7 of 9

每一步跳到A的跳法数等于上一步跳到B和E的跳法数之和，每一步跳到B的跳法数等于上一步跳到A和C的跳法数之和，每一步跳到C的跳法数等于上一步跳到B的跳法数，每一步跳到E的跳法数等于上一步跳到A的跳法数，每一步跳到D的跳法数等于上一步跳到C或跳到E的跳法数． 观察可知，上面的递推结果与前面的枚举也相吻合，所以青蛙在6次之内(含6次)跳到D点共有1?1?2?3?5?12种不同的跳法．

【答案】12

【例 14】 有6个木箱，编号为1，2，3，……，6，每个箱子有一把钥匙，6把钥匙各不相同，每个箱子

放进一把钥匙锁好．先挖开1，2号箱子，可以取出钥匙去开箱子上的锁，如果最终能把6把锁都打开，则说这是一种放钥匙的“好”的方法，那么“好”的方法共有 种． 【考点】计数之递推法 【难度】5星 【题型】填空 【关键词】迎春杯，中年级组，决赛

【解析】 (法1)分类讨论．如果1，2号箱中恰好放的就是1，2号箱的钥匙，显然不是“好”的方法，所以“好”

的方法有两种情况：

⑴1，2号箱的钥匙恰有1把在1，2号箱中，另一箱装的是3～6箱的钥匙． ⑵1，2号箱的钥匙都不在1，2号箱中．

对于⑴，从1，2号箱的钥匙中选1把，从3～6号箱的钥匙中选1把，共有2?4?8(种)选法，每一种选法放入1，2号箱各有2种放法，共有8?2?16(种)放法．

不妨设1，3号箱的钥匙放入了1，2号箱，此时3号箱不能装2号箱的钥匙，有3种选法，依次类推，可知此时不同的放法有3?2?1?6(种)． 所以，第⑴种情况有“好”的方法16?6?96(种)．

对于⑵，从3～6号箱的钥匙中选2把放入1，2号箱，有4?3?12(种)放法．不妨设3，4号箱的钥匙放入了1，2号箱．

此时1，2号箱的钥匙不可能都放在3，4号箱中，也就是说3，4号箱中至少有1把5，6号箱的钥匙．

如果3，4号箱中有2把5，6号箱的钥匙，也就是说3，4号箱中放的恰好是5，6号箱的钥匙，那么1，2号箱的钥匙放在5，6号箱中，有2?2?4种放法；

如果3，4号箱中有1把5，6号箱的钥匙，比如3，4号箱中放的是5，1号箱的钥匙，则只能是5号箱放6号箱的钥匙，6号箱放2号箱的钥匙，有2?1?2种放法；

同理，3，4号箱放5，2号箱或6，1号箱或6，2号箱的钥匙，也各有2种放法． 所以，第⑵种情况有“好”的放法12??4?2?2?2?2??144(种)． 所以“好”的方法共有96?144?240(种)．

(法2)递推法．设第1，2，3，…，6号箱子中所放的钥匙号码依次为k1，k2，k3，…，k6．当箱子数为n(n?2)时，好的放法的总数为an．

当n?2时，显然a2?2(k1?1，k2?2或k1?2，k2?1)．

当n?3时，显然k3?3，否则第3个箱子打不开，从而k1?3或k2?3，如果k1?3，则把1号箱子和3号箱子看作一个整体，这样还是锁着1，2两号钥匙，撬开1，2两号箱子，那么方法有a2种；当k2?3也是如此．于是n?2时的每一种情况对应k1?3或k2?3时的一种情况，这样就有a3?2a2?4．

当n?4时，也一定有kn?n，否则第n个箱子打不开，从而k1、k2、……、kn?1中有一个为n，不论其中哪一个是n，由于必须要把该箱子打开才能打开n号箱子，所以可以将锁着这把钥匙的箱子与

7-6-4.计数之递推法.题库 教师版 page 8 of 9