汉诺塔问题

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

在函数递归中，有一个非常经典的问题——汉诺塔问题。接下来我将介绍一下这个经典案例。

我们先来规定一下三个柱子分别为a,b,c柱，当我们在a柱上有一个圆盘时，只需将a柱上的圆盘移动到c柱上即可完成。那有两个圆盘时，我们先将第一个圆盘放到b柱上再将第二个圆盘放到c柱上，最后将在b柱上的小圆盘放到c柱上即可完成，一共用三步。

那我们以此类推，现在有n个圆盘在a柱上，我们只需要使用上面所述的方法，将n-1个圆盘看作一个整体，把n-1个圆盘先挪到b柱上再将第n个圆盘挪到c柱上，最后将n-1个圆盘在挪到c柱上即可完成。

那当我们考虑如何将n-1个盘子挪到b柱上时，我们不妨将n-2个圆盘看成整体，一起挪到b柱上去。以此类推，就可以求出n个圆盘挪到c柱上去的步数。

这个问题就可以用函数的递归非常巧妙的解决。下面就进行实际操作。

#include<stdio.h>
int sum = 0;
void hanoi(int n, char x, char y, char z)
{
  if (n == 1)
  {
    printf("%c-->%c\n", x, z);
    sum++;
  }
  else
  {
    hanoi(n - 1, x, z, y);//把n-1的盘子从a柱通过c柱移到b柱
    printf("%c-->%c\n", x, z);//将a柱的第n个盘子移到c柱
    sum++;
    hanoi(n - 1, y, x, z);//把n-1的盘子从b柱通过a柱移到c柱
  }
}
int main(void)
{
  int n;
  printf("Please input n:");
  scanf("%d", &n);
  hanoi(n, 'a', 'b', 'c');
  printf("%d\n", sum);
  return 0;
}

我们创建hanoi函数，给予函数四个形参，分别为盘子的个数，以及a,b,c三个柱子。当进入函数体后，先判断圆盘个数是否为1，如果不是将进入else部分。先将n-1的圆盘从a柱经过c柱移动到b柱上，进行第一个递归，当第一步完成后，然后将第n个圆盘从a柱移到c柱上去。最后在将n-1圆盘从b柱通过a柱移动到c柱上，进行第二次递归，最终完成汉诺塔游戏。这个问题的难点就在于要分两部完成，使用两次递归。

当我们有三个圆盘时，我们使用七步即可完成这个问题。函数的调用分析如下：

从第一步到最后一步，这张图分析了两次递归的顺序以及函数形参的变化，更好的帮助我们理解了两次递归的意义。

函数递归可以有效巧妙的解决一些步骤相似且复杂的问题，让复杂问题简单化，大事化小。