汉诺塔（C语言）

汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度​古老传说的益智玩具​。大梵天​创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门​把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

汉诺塔玩法：有三根柱子A B C，假设A柱子上有n个盘子:

1. 
   

• 我们的思路是要把A柱子最底下的盘子（最大的那个盘子）先移动到C柱子上
• 前提是要把A柱子除了最底下的那个盘子通过C柱子中转，移动到B柱子上（也就是要把n-1个盘子移动到B柱子上）
• 最后再把A柱子上最底下的盘子移动到C柱子上

2. 
   

• 然后通过A柱子中转把B柱子上n-1个盘子移动到C柱子上

有了这个思路代码就好写了：

#include <stdio.h>

void hanoi(int n, char A, char B, char C)
{
  if (n == 1)
    printf("%c-->%c\n", A, C);
  else
  {
    hanoi(n - 1, A, C, B);//通过C柱子，把A柱子上的n-1个盘子移动到B柱子上
    printf("%c-->%c\n", A, C);

    hanoi(n - 1, B, A, C);//最后通过A柱子，把B柱子上的n-1个盘子移动到C柱子上

  }

}

int main()
{
  int n = 0;
  printf("请输入汉诺塔层数:>");
  scanf("%d", &n);
  hanoi(n, 'A', 'B', 'C');
  return 0;

}

下面是我自己做的思维导图（比较潦草），用3个盘子做例子比较好理解

移动盘子次数为：2^n -1

步骤为：A->C  A->B  C->B  A->C  B->A  B->C  A->C