算法之汉诺塔

汉诺塔实质上是一个数学问题,但是在编程上也是十分出名的。

规则

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

  1. 每次只能移动一个圆盘;
  2. 大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

汉诺塔示意图

汉诺塔示意图

解法

关于汉诺塔的解法,其核心思想是 递归 + 整体化思想(这里我指的整体化思想有点类似动态规划里的子结构)。

假设有A、B、C三个塔,A塔有N块盘,目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔,再把A塔剩下的大盘移到C,最后把B塔的N-1块盘移到C。其中每次移动多于一块盘时,则再次使用上述算法来移动。

具体化得解法请参见 Geek_Ling的博客

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>

void moveElement(char start, char end);
int hanoiTower(char first, char second, char third, int n);

int main(int argc, const char * argv[]) {
// insert code here...
int n;

while (scanf("%d", &n) != EOF) {
printf("%d\n", hanoiTower('A', 'B', 'C', n));
}
return 0;
}


int hanoiTower(char first, char second, char third, int n) {
// 这里的 steps 用以计算汉洛塔的总步数,其公式为 h(n) = 2*h(n-1) -1;
int steps = 0;

if (n == 1) {
moveElement(first, third);
return 1;
}else {
// 把 n - 1 个圆盘从 A 塔移动至 B 塔,为第 n 个圆盘(也就是最大的圆盘)从 A 移动到 C 做准备;
steps += hanoiTower(first, third, second, n - 1) + 1;
// 第 n 个圆盘(也就是最大的圆盘)移动到 C;
moveElement(first, third);
// 把 n - 1 个圆盘从 B 塔移动至 C 塔;
steps += hanoiTower(second, first, third, n - 1) + 1;
steps--;
}

return steps;
}

void moveElement(char start, char end) {
printf("%c -> %c\n", start, end);
}
文章目录
  1. 规则
  2. 解法
  3. 代码
|