【C语言】汉诺塔 —— 详解

一、介绍

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

面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）

二、问题描述

有 A，B，C 三根柱子，A 上面有 n 个盘子，我们想把 A 上面的盘子移动到 C 上，但是必须要满足以下三个条件：

• 每次只能移动一个盘子;
• 盘子只能从柱子顶端滑出移到下一根柱子;
• 盘子只能叠在比它大的盘子上。

三、解题思路

这是一道递归方法的经典题目。

1、如果 n = 1，只有一个盘子，那么就直接将它从 A 移到 C 上

2、如果 n = 2，这时我们就需要借助 B，因为小盘子必须时刻都在大盘子上面，共需要 4 步

3、如果 n > 2，思路和上面是一样的。我们将 n 个盘子看成两个部分，一部分有 1 个盘子，另一部分有 n-1 个盘子

可是，那 n-1 个盘子是如何从 A 移动到 B 再移动到 C 的呢？

将最初的 n 个盘子从 A 移到 C 的问题，转化成了将 n-1 个盘子从 A 移到 C 的问题， 以此类推，直至转化成 1 个盘子的问题时，这个问题也就解决了。这里利用了分治的思想。

1. 当 n = 1 时，直接将盘子从 A 移到 C 上；
2. 当 n > 1 时，

• 先把上面的 n-1 个盘子从 A 借助 C 移动到 B（化为子问题，进行递归）；
• 再将 A 上最后一个盘子从 A →C；
• 再将 B 上 n - 1 个盘子从 B 借助 A 移动到 C（化为子问题，进行递归）。

四、代码

#include<stdio.h>
 
void move(char A, char C, int n)
{
  printf("把第%d个圆盘从%c——>%c\n", n, A, C);
}
 
void HanoiTower(char A, char B, char C, int n)
{
  if (n == 1)
  {
    move(A, C, n);
  }
  else
  {
    // 1.把A上n-1个圆盘从A柱借助C移动到B上
    HanoiTower(A, C, B, n - 1);
 
    // 2.将A最后一个圆盘从A->C
    move(A, C, n);
 
    // 3.把B上n-1个圆盘从B借助A移动到C上
    HanoiTower(B, A, C, n - 1);
  }
}
 
int main()
{
  int n = 0;
  printf("输入A柱上的圆盘的个数：");
  scanf("%d\n", &n);
 
  //将n个圆盘从A柱借助B柱移动到C柱上
  HanoiTower('A', 'B', 'C', n);
 
  return 0;
}

五、扩展

如果想要计算移动了多少次盘子，只需要加入多一个 move() 函数即可。