六年级上册数学竞赛试题——递推计数习题（含答案）

这是一份六年级上册数学竞赛试题——递推计数习题（含答案），共7页。试卷主要包含了三个人分别穿着红等内容，欢迎下载使用。
有许多计数问题很复杂，直接处理比较困难，此时硬碰硬是不行的．一个比较有效的策略是退而求其次：先考虑该问题的简单情形，看看简单情形如何处理；在解决了简单情形后，再考虑如何利用简单情形的结论来解决更复杂的问题……这个由简单到复杂的推导过程就叫“递推”．
那如何利用“递推法”来解决计数问题呢？下面我们就来看几个例子．
老师给小高布置了12篇作文，规定他每天至少写1篇．如果小高每天最多能写3篇，那么共有多少种不同的完成方法？（小高每天只能写整数篇）
「分析」从简单情况入手，看看能否找到合适的突破口．如果老师只布置1篇作文，小高有多少种不同的完成方法？如果老师布置2篇作文，小高有多少种不同的完成方法？如果老师布置3篇、4篇、……小高又分别有多少种不同的完成方法？篇数由少到多，完成方法数也会逐渐变多，这其中有什么规律呢？
练习1、一个楼梯共有12级台阶，规定每步可以迈二级台阶或三级台阶．走完这12级台阶，共有多少种不同的走法？
用10个的长方形纸片覆盖一个的方格表，共有多少种覆盖方法？
「分析」与例1的类似，我们还是从简单情形入手找递推关系．可具体从什么样的情形入手呢？
练习2、用7个的长方形纸片覆盖一个的方格表，共有多少种覆盖方法？
在一个平面上画出100条直线，最多可以把平面分成几个部分？
「分析」当直线数量不多时，画图数一数即可．但现在有100条，画图数并不现实．我们不妨在纸上将直线逐一画出，并在画的过程中仔细观察：每增加一条直线，平面被分成的部分会增加多少？这个增量有什么变化规律？
练习3、如果在一个圆内画出50条直线，最多可以把圆分成多少部分？
下面我们来学习一类很经典的递推计数问题——传球问题．
四个人分别穿着红、黄、绿、蓝四种颜色的球衣练习传球，每人都可以把球传给另外三个人中的任意一个．先由红衣人发球，并作为第1次传球，经过8次传球后球仍然回到红衣人手中．请问：整个传球过程共有多少种不同的可能？
「分析」看到这个问题，很多同学可能想通过树形图来求解，我们不妨来试一试．设穿着红、黄、绿、蓝四种颜色球衣的人分别是A、B、C、D．如下图，最开始时，球在A手上，第一次传球由A传给B、C、D，也就是第一层有三个字母就够了．然后B、C、D都会继续往下传球，各有3种传法，传到第二层需要9个字母．再传到第三层，需要27个字母……每一层需要的字母增加迅猛！如果传8次球，到最后一层会用到个字母，这要多大的一个树形图啊！
B
C
D
A
C
D
A
B
D
A
B
C
A
B
C
D
A
B
D
A
B
C
B
C
D
A
C
D
A
B
C
B
C
D
A
C
D
A
B
D
可见画树形图的方案不可行．但树形图对这道题就没有用了吗？并非如此．它可以帮助我们找出传球过程中所隐藏的递推关系．事实上，我们并不关心树形图长啥样，我们关心的是数量——树形图每一层分支的数量．因此，只要知道每一层各字母出现的次数就可以了，我们不妨制作一个表格来统计这个次数．如下表，我们用第一列来表示层数，第一行来表示每个人，其余空格用于填写字母在该层中出现的次数．请你从上方的树形图中数一数，填出表格中的前几行．然后思考一下：这其中隐藏着什么样的递推关系？
A
B
C
D
0
1
2
3
4
5
6
7
8
练习4、三个人分别穿着红、黄、蓝三种颜色的球衣练习传球，每人都可以把球传给另外两个人中的任意一个．先由红衣人发球，并作为第1次传球，经过7次传球后传到蓝衣人手中．请问：整个传球过程共有多少种不同的可能？
解传球问题的方法称为“传球法”．“传球法”是递推法的一种特殊形式，是一种极其实用的数表累加计数法．
一个七位数，每一位都是1、2或者3，而且没有连续的两个1，这样的七位数一共有多少个？
「分析」这道题与前面两道题有何异同？应该如何求解呢？
前面的计数问题，递推关系都表现为数列、数表的简单累加，但这不是递推的全部．简单累加只是递推的一种表现形式，递推还有很多其它形式．下面我们就来看一道无法通过简单累加求解的计数问题．
圆周上有10个点A1、A2、、A10，以这些点为端点连接5条线段，要求线段之间没有公共点，共有多少种连接方式？
「分析」圆周上10个点，连5条线段，连法很多，很难直接画出来枚举．像这类问题，我们同样还是从简单的情况入手．那么是应该按1个点、2个点、3个点、……这样依次计数，来找递推关系吗？
作业
有10个蛋黄派，萱萱每天吃1个或2个，那么共有多少种不同的吃法？
甲、乙两人玩抓石子游戏，共有12个石子，甲先乙后轮流抓取．每次可以抓取其中的2个、3个或4个，直到最后抓取完毕为止．那么共有多少种抓取石子的方案？
用直线把一个平面分成100部分，至少要在平面上画几条直线？
一个七位数，它由数字0、1、2、3、4组成，相邻位置上的数字不相同，并且个位数字是2．这样的七位数有多少个？
用8个
的长方形纸片覆盖下面的方格表，共有多少种覆盖方法？
作业：
答案：89
简答：
蛋黄派数
1
2
3
4
5
6
7
8
9
10
吃的方法数
1
2
3
5
8
13
21
34
55
89
答案：36
简答：
石子数
1
2
3
4
5
6
7
8
9
10
11
12
抓取方法数
0
1
1
2
2
4
5
8
11
17
24
36
0
1
2
3
4
0
0
1
1
1
1
1
4
3
3
3
3
2
12
13
13
13
13
3
52
51
51
51
51
4
204
205
205
205
205
5
820
819
819
819
819
6
3276
3277
3277
3277
3277
答案：14
简答：略．
答案：3277
简答：如右表所示，用传球法列表解决．传球规则是：0不能发球，其它都可以发球；传球不能传给自己，只能传给别人；总共传球传6次．
答案：29
简答：如下方左图所示，和例题2类似，找到某个方格，依据这个方格是横着覆盖还是竖着覆盖分两种情况讨论．情况一，横着覆盖：这类情况其实就是
的覆盖方法，利用练习2的分析方法和相关结论，可得答案为21．情况二，竖着覆盖：在这类情况下，有另外四个格子的覆盖方法唯一确定，如下方右图中的虚线所示，剩下需要覆盖的是一个
的方格表，其方法数量也可参考练习2的分析方法和相关结论来取得，答案为8．上述两种情况相加，可得答案为
．