汉诺塔

Algorithms

1. 问题描述

有一个梵塔，塔内有三个座A、B、C，A座上有诺干个盘子，盘子大小不等，大的在下，小的在上(如图)。把这些个盘子从A座移到C座，中间可以借用B座但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。

描述简化：把A柱上的n个盘子移动到C柱，其中可以借用B柱。

2. 简单分析

假设有n个盘子，我们把盘子从小到大标记为1、2、3…n。三柱子一共有三个状态：

  1. 状态0 A: 按顺序堆放的n个盘子。 B：空的。 C：空的。
    目标需要把A上的n个盘子移动到C，而且C盘最下面的盘子应该是最大的盘子，标号为n。要取得A上的第n个盘子，需要把它上面的n-1个盘子拿开放在B柱上。当然B柱上的盘子也是按照大在下小在上的原则堆放的。

    这一步完成之后三个塔变为状态一。

  2. 状态1 A：只有最大的一个盘子。 B:按规则堆放的n-1个盘子。 C:空的。
    这时候可以直接把A上的最大盘移动到C盘，移动后的状态：中间状态——A：空的。B：n-1个盘子。C：有一个最大盘（第n个盘子）。
    这时候C柱其实可以看做空的，因为剩下的的所有盘子都比它小，任何一个盘子都可以放在C柱上。所以现在的状态： 中间状态——A：空的。B：n-1个盘子。C：空的。
    现在的问题和原问题有些相似之处，如果把B柱上的n-1个盘子移动到A柱上，那么现在的问题和原问题相比就只是规模变小了而已。把B上的n-1个盘子移动到A上，其实和上文中把n-1个盘子从A柱移动到B柱是一样的，只是柱子的名称换了一下而已。（如果写成函数，只是参数的调用顺序改变了而已）

  1. 状态2 A：按顺序对方的n-1个盘子。B：空的。C：按顺序堆放的第n个盘子（可看为空柱）

此时我们完成了一次完美的递归，从状态0到状态2，除了规模变小，其他方面没有任何区别了。

3. 算法实现

定义函数:

1
2
Hanoi(a,b,c,n)//表示把a上的n个盘子移动到c上，其中可以用到b。
move(m,n)//表示把m上的盘子移动到n上

算法流程：

  1. 把A上的n-1个移动到B：Hanoi（a,c,b,n-1）//状态1
  2. 把A上的最后一个大盘子移动到C：move（a,c）
  3. 把B上的n-1个盘子移动到A: Hanoi（b,c,a,n-1）//状态2

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
main()
{
    int n;
    printf("请输入n阶汉诺塔：\n");
    scanf("%d",&n);
    hanoi(n,'A','B','C');
}

void hanoi(char A,char B,char C,int n)
{
    if(n==1)
    {
      printf("Move disk %d from %c to %c\n",A,C,n);
    }
    else
    {
      hanoi(A,C,B, n-1);
      printf("Move disk %d from %c to %c\n",n,A,C);
      hanoi(B,A,C,n-1,);
    }
}