1、第三讲 递推计数 有许多计数问题很复杂，直接处理比较困难，此时硬碰硬是不行的一个比较有效的策 略是退而求其次： 先考虑该问题的简单情形， 看看简单情形如何处理； 在解决了简单情形后， 再考虑如何利用简单情形的结论来解决更复杂的问题这个由简单到复杂的推导过程就 叫“递推” 那如何利用“递推法”来解决计数问题呢？下面我们就来看几个例子 例1 老师给小高布置了 12 篇作文， 规定他每天至少写 1 篇 如果小高每天最多能写 3 篇， 那么共有多少种不同的完成方法？（小高每天只能写整数篇） 分析分析从简单情况入手，看看能否找到合适的突破口如果老师只布置 1 篇作文，小 高有多少种不同的完成方法？如果老
2、师布置 2 篇作文， 小高有多少种不同的完成方法？ 如果老师布置 3 篇、4 篇、小高又分别有多少种不同的完成方法？篇数由少到多， 完成方法数也会逐渐变多，这其中有什么规律呢？ 练习 1、一个楼梯共有 12 级台阶，规定每步可以迈二级台阶或三级台阶走完这 12 级 台阶，共有多少种不同的走法？ 例2 用 10 个1 3的长方形纸片覆盖一个10 3的方格表，共有多少种覆盖方法？ 分析分析与例 1 的类似，我们还是从简单情形入手找递推关系可具体从什么样的情形 入手呢？ 练习 2、用 7 个1 2的长方形纸片覆盖一个72的方格表，共有多少种覆盖方法？ 例3 在一个平面上画出 100 条直线，最多可以
3、把平面分成几个部分？ 分析分析当直线数量不多时，画图数一数即可但现在有 100 条，画图数并不现实我 们不妨在纸上将直线逐一画出，并在画的过程中仔细观察：每增加一条直线，平面被分 成的部分会增加多少？这个增量 有什么变化规律？ 练习 3、如果在一个圆内画出 50 条直线，最多可以把圆分成多少部分？ 下面我们来学习一类很经典的递推计数问题传球问题 例4 四个人分别穿着红、黄、绿、蓝四种颜色的球衣练习传球，每人都可以把球传给另外 三个人中的任意一个先由红衣人发球，并作为第 1 次传球，经过 8 次传球后球仍然回 到红衣人手中请问：整个传球过程共有多少种不同的可能？ 分析分析看到这个问题，很多同学可
4、能想通过树形图来求解，我们不妨来试一试设穿 着红、黄、绿、蓝四种颜色球衣的人分别是 A、B、C、D如下图，最开始时，球在 A 手上，第一次传球由 A 传给 B、C、D，也就是第一层有三个字母就够了然后 B、C、 D 都会继续往下传球，各有 3 种传法，传到第二层需要 9 个字母再传到第三层，需要 27 个字母每一层需要的字母增加迅猛！ 如果传 8 次球， 到最后一层会用到 8 36561 个字母，这要多大的一个树形图啊！ 可见画树形图的方案不可行 但树形图对这道题就没有用了吗？并非如此 它可以帮助 我们找出传球过程中所隐藏的递推关系事实上，我们并不关心树形图长啥样，我们关 心的是数量树形图每一
5、层分支的数量 因此， 只要知道每一层各字母出现的次数就 可以了，我们不妨制作一个表格来统计这个次数如下表，我们用第一列来表示层数， 第一行来表示每个人， 其余空格用于填写字母在该层中出现的次数 请你从上方的树形 图中数一数，填出表格中的前几行然后思考一下：这其中隐藏着什么样的递推关系？ 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 练习 4、三个人分别穿着红、黄、蓝三种颜色的球衣练习传球，每人都可以把球传给另 外两个人中的任意一个先由红衣人发球，并作为第 1 次传球，经过 7 次传
6、球后传到蓝 衣人手中请问：整个传球过程共有多少种不同的可能？ 解传球问题的方法称为“传球法” “传球法”是递推法的一种特殊形式，是一种极其实用的 数表累加计数法 例5 一个七位数，每一位都是 1、2 或者 3，而且没有连续的两个 1，这样的七位数一共有 多少个？ 分析分析这道题与前面两道题有何异同？应该如何求解呢？ 前面的计数问题，递推关系都表现为数列、数表的简单累加，但这不是递推的全部简单累 加只是递推的一种表现形式， 递推还有很多其它形式 下面我们就来看一道无法通过简单累 加求解的计数问题 例6 圆周上有 10 个点 A1、A2、A10，以这些点为端点连接 5 条线段，要求线段之间没 有公
7、共点，共有多少种连接方式？ 分析分析圆周上 10 个点， 连 5 条线段，连法很多， 很难直接画出来枚举 像这类问题， 我们同样还是从简单的情况入手那么是应该按 1 个点、2 个点、3 个点、这样依 次计数，来找递推关系吗？ A B C D 0 1 2 3 4 5 6 7 8 神奇的汉诺塔 一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的 圣庙里，一块黄铜板上插着三根宝石针印度教的主神梵天在创造世界的时候，在其中一根 针上从下到上地穿好了由大到小的 64 片金片，这就是所谓的汉诺塔不论白天黑夜，总有 一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针
8、上，小片必须在 大片上面僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界 就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽 不管这个传说的可信度有多大，如果考虑一下把 64 片金片，由一根针上移到另一根针 上，并且始终保持上小下大的顺序这需要多少次移动呢?这里需要递归的方法假设有 n 片，移动次数是 ( )f n显然(1)1f ， (2)3f ， (3)7f ，且 (1)2 ( )1f kf k 此后不 难证明( )21 n f n 64n 时， 64 (64)21 18446744073709551615f 假如每秒钟一次，共需多长时间呢？一个平年 365 天有
9、31536000 秒，闰年 366 天有 31622400秒，平均每年31556952秒，计算一下， 18446744073709551615/31556952=584554049253.855 年 这表明移完这些金片需要 5845 亿年以上， 而地球存在至今不过 45 亿年， 太阳系的预期 寿命据说也就是数百亿年真的过了 5845 亿年，不说太阳系和银河系，至少地球上的一切 生命，连同梵塔、庙宇等，都早已经灰飞烟灭 课 堂 内 外 作业 1. 有 10 个蛋黄派，萱萱每天吃 1 个或 2 个，那么共有多少种不同的吃法？ 2. 甲、乙两人玩抓石子游戏，共有 12 个石子，甲先乙后轮流抓取每次可
10、以抓取其中的 2 个、3 个或 4 个，直到最后抓取完毕为止那么共有多少种抓取石子的方案？ 3. 用直线把一个平面分成 100 部分，至少要在平面上画几条直线？ 4. 一个七位数，它由数字 0、1、2、3、4 组成，相邻位置上的数字不相同，并且个位数字 是 2这样的七位数有多少个？ 5. 用 8 个的长方形纸片覆盖下面的方格表，共有多少种覆盖方法？ 1 2 第五讲 进位制问题 例题：例题： 例7 答案： （1）31023、3735、11B9、7DD； （2）257； （3）1742 详解： （1） （2） 320 2 50 51 52 5257 ； （3） 320 2 120 121 122
11、121742 例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 5 2013 3 5 402 2 5 80 1 5 1
12、6 0 5 3 3 8 2013 2 8 251 3 8 31 7 8 3 3 12 2013 9 12 167 12 12 13 1 12 1 1 16 2013 13 16 125 13 16 7 7 详解：所看页数列为 1、1、2、4、8、256、512、989 练习：练习： 6.6. 答案：554；2781；195；722 7.7. 答案：16157 8.8. 答案：21234 9.9. 答案：248a=5、b=0、c=3 作业：作业： 1. 答案： （1）354； （2）458； （3）C30； （4）14443； （5）433； （6）85 2. 答案： （1）1131； （2）12312 3. 答案：100 简答：a 很容易知道只能为 1，再根据进位制展开解方程得出 b、c 均为 0，所以原数十 进制是 100 4. 答案：22 简答： 由题意有， 其中 a、 b、 c 均小于 3， 则有， 化简得，符合条件的 a、b、c 为 2、1、1，化成十进制是 22 5. 答案：24 简答：由题意有，其中 a、b 均要大于 7，则有，符合条件 的最小的 a、b 为 15、9，和是 24 4774ab 4774 ab 815abc 93164abccba 34 abccba
