具体数学(第2版)习题解析.pdf

1 递归问题 1.1 知识点总结 1.2 练习题 1.2.1 热身题 【1.1】所有的马都有同样的颜色，我们可以对给定集合中的马匹数量运用归纳法来证明之。 理由就是：“如果恰有一匹马，那么它与它自身有相同的颜色，故而基础是显然的。根据归纳法的 步骤，假设有n 匹马，标号从1到n。根据归纳假设，标号从1直到n-1 的马都有同样的颜色，类 似地，标号从2 直到n 的马也有同样的颜色。但是，处于中间位置标号从2 直到n-1 的马，当它们 在不同的马群中时不可能改变颜色，因为这些是马，而不是变色龙。故而依据传递性可知，标号从 1直到n 的马也必定有同样的颜色，于是全部n 匹马都有同样的颜色。证毕。”如果这一推理有误， 那么错在哪儿？ 解：略。 1.2 A B A B 【 】把有 个圆盘的塔从左边的桩柱 移动到右边的桩柱 ，不允许在 和 之间直接移 动，求最短的移动序列 （每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。像通常一 样，每次只能移动一个圆盘，且较大的圆盘永远不能放在较小圆盘的上面）。 解： 【1.2a】现有3 个排成一行的桩柱A、B 和C，柱B 位于柱A 和柱C 之间。初始状态是在A 柱上叠放了 个尺寸不同的圆盘，其叠放规则是自上而下按圆盘尺寸从小到大进行叠放。现要求将 A C 1 2 个圆盘从柱 移动到柱 ，移动规则如下：（）每次只能移动一个圆盘；（）所有的圆盘不可以 在柱A 和柱C 之间直接移动，而必须经过中间的桩柱B （可以移入到柱B 或从柱B 移出）；（3） 较大的圆盘永远不得放在较小圆盘的上面。对于上述问题，我们已知最短的移动序列 满足如下 递归式： 。请求解： （1）上述递归式的封闭形式解。 （2）如果放宽第3个条件，即：只允许最大的那个圆盘可以放在较小圆盘之上，而其它所有 圆盘仍遵守小盘在上、大盘在下的叠放和移动规则，那么最短的移动序列是多少？ 解： 1 （）由递归式 ，可得： 令 ，则有： -1- 可解得： ，因此有： （2）依然采用分治法，分而治之，把大问题化解成小问题。最开始在A 柱子上有 个盘子， 我们可以把 个盘子看成：前 个盘子、第 个盘子和第 个盘子。令 为移动 个盘子的最 短移动序列。 S1：把前 个盘子从A 柱移动到C柱，至少需要移动 步； S2：把第 个和第 个盘子从A 柱依次移动到B 柱，需要移动2 步； S3：把前 个盘子从C柱移回到A 柱，这又需要 步； S4：把第 个和第 个盘子从B 柱依次移动到C柱上，需要移动2 步； S5：把前 个盘子从A 柱移动到C柱，至少又需要移动 步。 最终按要求完成了 个盘子的移动，因此有： 【1.5】由3个重叠的圆做成的维恩图常用来描述与3个给定集合有关的8个可能得子集： 请问：由4 个给定集合给出的16种子集的子集能否用4 个重叠的圆来描述？ 解题分析：此题与直线的平面划分问题相同。 思考方法：考虑每增加一个圆圈，增加的交点与增加的区域的关系。 因为每增加一个圈，与每一个已存在的圈相交，最多每个圈有2个交点，而所增加的区域正好 与增加的交点数目相同。 设 为n 个圈划分的区域个数，可得： 最终可求得： ， 【1.6】平面上由 条直线定义的某些区域是无界的，而另一些区域则是有界的。有界区域的最 -2- 大个数是多少？ 解： 解题思路：当 时，每增加一条直线，增加的有限区域个数是(原直线个数-1)