注:本节内容为《具体数学》(原书第二版) 第一章 递归问题 热身题答案。
写在前面
有的时候解决习题的最大难点是理解题意。
1.3
题意:每一种“能够成立的叠放”都会被遇到。
答案:
所有“能够成立的叠放”一共只有
根据 1.2 问的结论,由于最少使用
- 为什么会 +1?因为有初始状态
- 为什么这样是最少的?假设这样不是最少的,即某一种情况可能经历了两次,那么问题来了,为什么在第一次遇到那种情况的时候不直接执行第二次遇到那种情况后的步骤,第一次遇到到第二次遇到中间的步骤都是冗余。
1.4
证明:数学归纳法。省略初值证明。假设
(一)若最大的圆盘移动
对于
- 前
个圆盘移动到某个塔上,次数 - 将
个圆盘移动到目标塔,次数 - 将
个圆盘移动到目标塔,次数
故总次数
(二)若最大的圆盘不移动
对于
故总次数
1.5
答案:不可能
两个圆至多产生 2 个交点。对于 3 个圆,目前的状态共有 6 个圆。
第四个圆最多增加 6 个交点,变为
求证:增加 6 个交点最多增加 6 个区域
证明:
对于连续的两个交点,至多增加一个区域,增加区域有两种情况:
两个连续的交点也可能不增加区域,情况如下:
1.6
下面证明上界(即至多)
引理 1:构成一个必和图形至少需要三条边,故只有在
求证:对于平面上已有
证明:因为产生新闭合图形只有两种情况:
而上述两种情况都需要贡献两个连续的交点。第
下面证明下界(即至少)
我们可以采用 1.2 节给出的构造,就能够得到
Q.E.D.