高斯小学奥数六年级上册含答案第03讲 递推计数

1、第三讲递推计数有许多计数问题很复杂，直接处理比较困难，此时硬碰硬是不行的一个比较有效的策略是退而求其次：先考虑该问题的简单情形，看看简单情形如何处理；在解决了简单情形后，再考虑如何利用简单情形的结论来解决更复杂的问题这个由简单到复杂的推导过程就叫“递推”那如何利用“递推法”来解决计数问题呢？下面我们就来看几个例子例1老师给小高布置了12篇作文，规定他每天至少写1篇如果小高每天最多能写3篇，那么共有多少种不同的完成方法？（小高每天只能写整数篇）分析从简单情况入手，看看能否找到合适的突破口如果老师只布置1篇作文，小高有多少种不同的完成方法？如果老师布置2篇作文，小高有多少种不同的完成方法？如果老师

2、布置3篇、4篇、小高又分别有多少种不同的完成方法？篇数由少到多，完成方法数也会逐渐变多，这其中有什么规律呢？练习1、一个楼梯共有12级台阶，规定每步可以迈二级台阶或三级台阶走完这12级台阶，共有多少种不同的走法？例2用10个13的长方形纸片覆盖一个103的方格表，共有多少种覆盖方法？分析与例1的类似，我们还是从简单情形入手找递推关系可具体从什么样的情形入手呢？练习2、用7个12的长方形纸片覆盖一个72的方格表，共有多少种覆盖方法？例3在一个平面上画出100条直线，最多可以把平面分成几个部分？分析当直线数量不多时，画图数一数即可但现在有100条，画图数并不现实我们不妨在纸上将直线逐一画出，并在画

3、的过程中仔细观察：每增加一条直线，平面被分成的部分会增加多少？这个增量有什么变化规律？练习3、如果在一个圆内画出50条直线，最多可以把圆分成多少部分？下面我们来学习一类很经典的递推计数问题传球问题例4四个人分别穿着红、黄、绿、蓝四种颜色的球衣练习传球，每人都可以把球传给另外三个人中的任意一个先由红衣人发球，并作为第1次传球，经过8次传球后球仍然回到红衣人手中请问：整个传球过程共有多少种不同的可能？分析看到这个问题，很多同学可能想通过树形图来求解，我们不妨来试一试设穿着红、黄、绿、蓝四种颜色球衣的人分别是a、b、c、d如下图，最开始时，球在a手上，第一次传球由a传给b、c、d，也就是第一层有三个

4、字母就够了然后b、c、d都会继续往下传球，各有3种传法，传到第二层需要9个字母再传到第三层，需要27个字母每一层需要的字母增加迅猛！如果传8次球，到最后一层会用到386561个字母，这要多大的一个树形图啊！abacdacbdadbcbcdabdabcbcdacdabcbcdacdabd可见画树形图的方案不可行但树形图对这道题就没有用了吗？并非如此它可以帮助我们找出传球过程中所隐藏的递推关系事实上，我们并不关心树形图长啥样，我们关心的是数量树形图每一层分支的数量因此，只要知道每一层各字母出现的次数就可以了，我们不妨制作一个表格来统计这个次数如下表，我们用第一列来表示层数，第一行来表示每个人，其余

5、空格用于填写字母在该层中出现的次数请你从上方的树形图中数一数，填出表格中的前几行然后思考一下：这其中隐藏着什么样的递推关系？abcd012345678练习4、三个人分别穿着红、黄、蓝三种颜色的球衣练习传球，每人都可以把球传给另外两个人中的任意一个先由红衣人发球，并作为第1次传球，经过7次传球后传到蓝衣人手中请问：整个传球过程共有多少种不同的可能？解传球问题的方法称为“传球法”“传球法”是递推法的一种特殊形式，是一种极其实用的数表累加计数法例5一个七位数，每一位都是1、2或者3，而且没有连续的两个1，这样的七位数一共有多少个？分析这道题与前面两道题有何异同？应该如何求解呢？前面的计数问题，递推关

6、系都表现为数列、数表的简单累加，但这不是递推的全部简单累加只是递推的一种表现形式，递推还有很多其它形式下面我们就来看一道无法通过简单累加求解的计数问题例6圆周上有10个点a1、a2、l、a10，以这些点为端点连接5条线段，要求线段之间没有公共点，共有多少种连接方式？分析圆周上10个点，连5条线段，连法很多，很难直接画出来枚举像这类问题，我们同样还是从简单的情况入手那么是应该按1个点、2个点、3个点、这样依次计数，来找递推关系吗？课堂内外神奇的汉诺塔一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针印度教的主神梵天在创造世界的时候，在其

7、中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序这需要多少次移动呢?这里需要递归的方法假设有n片，移动次数是f(n)显然f(1)=1，f(2)=3，f(3)=7，且f(k+1)=2f(k)+1此后不难证明f(n)=2n-1n=64时，f(64)=

8、264-1=18446744073709551615假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，18446744073709551615/31556952=584554049253.855年这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭作业1.有10个蛋黄派，萱萱每天吃1个或2个，那么共有多少种不同的吃法？2.甲、乙两人玩抓石子游戏，共有12个石

9、子，甲先乙后轮流抓取每次可以抓取其中的2个、3个或4个，直到最后抓取完毕为止那么共有多少种抓取石子的方案？3.用直线把一个平面分成100部分，至少要在平面上画几条直线？4.一个七位数，它由数字0、1、2、3、4组成，相邻位置上的数字不相同，并且个位数字是2这样的七位数有多少个？5.用8个12的长方形纸片覆盖下面的方格表，共有多少种覆盖方法？第五讲进位制问题例题：例7答案：（1）31023、3735、11b9、7dd；（2）257；（3）1742详解：（1）5201338201321220139540228251312167125801831712131516083312115331620131

10、316125131677（2）253+052+15+250=257；（3）2123+0122+112+2120=1742例8答案：（1）5；（2）13121、731详解：三进制转九进制从右往左两位两位转换；二进制转四进制从右往左两位两位转换；二进制转八进制从右往左三位三位转换例9答案：15031详解：列竖式计算例10答案：212a=5、b=5、c=2例11答案：10个详解：若要称量1克的重量必须有1克的砝码，若要称量2克的重量必须有2克的砝码，依次类推可得：1+2+4+8+16+32+64+128+256+512，此时可以称量1克到1023克的所有重量，此时需要10个砝码例12答案：12详解：所看页数列为1、1、2、4、8、256、512、989练习：6.答案：554；2781；195；7227.答案：161578.答案：212349.答案：248a=5、b=0、c=3作业：（1.答案：1）354；（2）458；（3）c30；（4）14443；（5）433；（6）85（2.答案：1）1131；（2）123123.答案：100简答：a很容易知道只能为1，再根据进位制展开解方程得出b、c均为0，所以原数十进制是