汉诺塔

什么是汉诺塔？

汉诺塔问题源于印度传说，传说中一个庞大的印度寺庙里，有一个72英尺高的铜制塔，塔中有三个针，最下面一个放着64个盘子，盘子大小不同，大的在下面，小的在上面，且每个盘子都比下面的盘子小得多。僧人们按照预言的指示把铜盘的一个个不同大小的圆盘从第一个针上移至第三个针上，保持原有顺序装满第三个针。据说，完成最后一个移动后，寺庙就会毁灭，太阳就会消失。

通俗的说 就是：有三根柱子，我们需要把第一个柱子的盘子全部移动到第三个柱子，有下面三个要求：

  1. 每次只能移动一个盘子；
  2. 小盘子必须在大盘子上面；
  3. 在移动盘子时，不能把一个盘子放到比它小的盘子上。

思路

先将前面n-1个盘子移动到辅助柱子上，再将第n个盘子移动到目标柱子上，最后将前面n-1个盘子移动到目标柱子上。

代码实现(递归)

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
#include <stdio.h>

void hanoi(int n, char a, char b, char c)
{
    if (n == 1)
    {
        printf("%c --> %c\n", a, c);  //只有1块的时候，直接从 a 移动到 c
    }
    else
    {
        hanoi(n - 1, a, c, b);  //将 n - 1 块从 a 移到到 c，借助 b
        printf("%c --> %c\n", a, c); //把 a 中剩下的那一块，移动到 c
        hanoi(n - 1, b, a, c);  //将 n - 1 块从 b 移动到 c，借助 a
    }
}

int main()
{
    int n;
    printf("请输入盘子的个数：");
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');

    return 0;
}