【具体数学】递归式1

具体数学学习笔记 1

1·三生万物

1.1 导言

考虑这么一道题：

题目描述

汉诺塔由三根柱子（分别用 A、B、C 表示）和 $n$ 个大小互不相同的空心盘子组成。一开始 $n$ 个盘子都摞在柱子 A 上，大的在下面，小的在上面，形成了一个塔状的锥形体。

对汉诺塔的一次合法的操作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。我们可以用两个字母来描述一次操作：第一个字母代表起始柱子，第二个字母代表目标柱子。例如，AB 就是把柱子 A 最上面的那个盘子移到柱子B。汉诺塔的游戏目标是将所有的盘子从柱子 A 移动到柱子 B 或柱子 C 上面。

问将 A 柱上整个塔移动到另一个柱上，最少需要移动多少步。

---

通过这道题，学习一些比较偏注意力的递归问题：

1.2 从一说起

让我们先研究小规模问题。

• $1$ 个盘子只用移动一下。
• $2$ 个盘子只用移动 $3$ 次。
• $3$ 个盘子移动 $7$ 下。具体方案非常建议自己手磨。

通过手磨，我们可以得到问题的边界情况。

也能得到一定的规律，或性质。

1.3 一生二三

接下来，应当引入适当记号，进行命名和求解。

我们设 $T_n$ 为 $n$ 个盘子时的方案数。

显然：

• $T_1=1$
• $T_2=3$
• $T_3=7$

那么，问题来了。

$T_n=??$

我们回想一下 $n=3$ 时怎么移动。（没印象的建议重新手磨）

整体过程分为 $3$ 个阶段：

1. 把前两个盘子移动到 B 柱上。

2. 将第三个盘子移到 C 柱上。

3. 将前两个盘子移到 C 柱上。

推广到任意数，我们就能得到一个结论。

$$T_n \le 2 \times T_{n-1} + 1 \ \ \ \ n \ge 1$$

$$T_n = 0 \ \ \ \ \ \ \ n = 0$$

同样的，想移动最后一根盘子，至少把前几个盘子挪走，需要 $T_{n-1}$ 次操作。

如果我们不太精明，第 $n$ 个盘子可能移动多次。

前几个盘子再移回去有是 $T_{n-1}$ 次。

所以又得到了一个结论

$$T_n \ge 2 \times T_{n-1} + 1 \ \ \ \ n \ge 1$$

$$T_n = 0 \ \ \ \ \ \ \ n = 0$$

两者取交集：

$$T_n = 2 \times T_{n-1} + 1 \ \ \ \ n \ge 1$$

$$T_n = 0 \ \ \ \ \ \ \ n = 0$$

但是这么算，你会飞起来，毕竟递归的效率很低。

我们考虑化简。

1.4 三生万物

1.4.1 见微知著

或许可以列表出来

$n$	$T_n$
$0$	$0$
$1$	$1$
$2$	$3$
$3$	$7$
$4$	$15$
$5$	$31$
$6$	$63$
$7$	$127$

加上超人的注意力，你会发现一个事实

$$T_n=2^n-1$$

证明见后。

1.4.2 以简易繁

我们注意到 式子两边同时加一会使处理更加简洁

$$T_n + 1 = 2 \times T_{n-1} + 2 \ \ \ \ n \ge 1$$

$$T_n + 1 = 1 \ \ \ \ \ \ \ n = 0$$

我们令 $U_n=T_n+1$

然后我们有了一组式子：

$$U_n = 2 \times U_{n-1} \ \ \ \ n \ge 1$$

$$U_n = 1 \ \ \ \ \ \ \ n = 0$$

然后这个东西就相当简单，

易得 $U_n=2^n \ \ \ \ \ \ \ n \ge 0$

代回原式

$$T_n = 2^n - 1 \ \ \ \ \ \ \ n \ge 0$$

1.5 数学归纳

对于 $n=0$ 显然成立。

假设这个对于 $n-1$ 成立。

所以

$$T_n=2 \times T_{n-1} + 1 = 2 \times (2^{n-1}-1) + 1 = 2^n-1$$

所以对于 $n$ 成立。

证明完了。

数学归纳法 还是太牛逼了。

具体可以查阅百度百科。

2 返璞归真

2.1 题目描述

一个平面，画上 $n$ 条直线，最多可以吧整个平面划成几份？

2.2 给出结论

注意到，再画一条直线最多和 $n-1$ 条直线，增加 $n$ 块。

我们设答案为 $L_n$ 。

有：

$$L_n=L_{n-1}+n \ \ \ \ \ \ \ \ \ n>0$$

$$L_n=1\ \ \ \ \ \ \ \ \ n=0$$

2.3 暴力拆解

这个式子我们采用一个暴力的方法：

我们把 $L_{n-1}$ 拆解。

这样就有另一个东西：

$$L_n=(L_(n-2)+n-1)+n=((L_{n-3}+n-2)+n-1)+n= \dots = (\sum ^n _{i=1} i)+1$$

这个东西，等差数列求和公式一下，

$$L_n = \frac{n(n+1)}{2}+1$$

随后，我们就暴力拆完了。

可以按 1.5 的方法证明它。

2.4 化直为折

我们将直线换为有一个拐点的折现，可以怎么做。

我们设答案为 $Z_n$。

一条这样的折线可以看做两条直线相交并砍掉一边。

但是一条折线至少比两条直线少两片区域。

所以

$$Z_n=L_{2n}-2n=\frac{2n(2n+1)}{2}-2n=2n^2+n+1-2n=2n^2-n+1$$

所以基本证完了。