汉诺塔问题

从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数。

image-20201022112855233

考虑最后可能的步骤:要想把 n 个圆盘从 A 移动到 C,在移动最大的圆盘时,C 上不能有任何圆盘,A上面只能有一个大圆盘,这就意味着其余的 n-1 个圆盘必须都位于 B 上面。此时我们只需要:将第 n 个圆盘从 A 移动到 C,再将 前 n-1 个圆盘从 B 移动到 C 即可,用函数可表示为:
$$
\begin{split}
\text{move}([1 \dots n], A, C) =& \text{move}([1\dots n-1], A, B) \\
+& \text{move}(n, A, C) \\
+& \text{move}([1\dots n-1], B, C)
\end{split}
$$
$\text{move}([1\dots n-1], A, B)$ 表示把前 $n-1$ 个圆盘从 A 移动到 B,它与把前 $n$ 个圆盘从 A 移动到 C 是类似的。后者需要借助 B,而前者需要借助于 C。特别地,当 $n=1$ 时,$\text{move}(1,\ast,\ast)$ 总是等于1。

这是汉诺塔问题的递归解法,下面看一下时间复杂度:
$$
\begin{split}
T_n &= T_{n-1} + 1 + T_{n-1} = 2T_{n-1} + 1 \\
&= 2(2T_{n-2}+1)+1 = 2^2T_{n-2}+2+1 \\
&= 2^2(2T_{n-3}+1)+3 = 2^3T_{n-3}+2^2+2+1 \\
&\dots \\
&= 2^{n-1}T_1 + 2^{n-2} + \dots + 2 + 1 \\
&= 2^{n-1} + 2^{n-2} + \dots + 2 + 1
\end{split}
$$
显然这是一个指数级的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int move(int, char, char, char);

int main(){
int n;
n = move(5, 'A', 'C', 'B');
printf("Total moving counts = %d", n);
return 0;
}

int move(int n, char src, char dst, char medi) {
if (n == 1) {
printf("Move the disc(1) from %c to %c\n", src, dst);
return 1;
}
int x1 = move(n-1, src, medi, dst);
printf("Move the disc(%d) from %c to %c\n", n, src, dst);
int x2 = move(n-1, medi, dst, src);
return x1 + x2 + 1;
}
----- For reprint please indicate the source -----
0%