【递归问题】——汉诺塔

问题背景

汉诺塔问题是由法国数学家卢卡斯于1883年提出的。他还为此赋予了一个罗曼蒂克的传说：

在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

解题分析

       解决该问题的最好的方法就是对它进行稍加推广，汉诺塔有64个圆盘，8个圆盘，我们可以将问题推广到有n个圆盘，这就是递归的思想，先研究小的情况。

       只有一个或两个圆盘时是很容易求解的，现在将问题推广到三个圆盘，先将上面两个圆盘移动到中间的桩柱上，再移动第三块圆盘，接着再把其余两个放到它上面。现在我们再将问题推广到n个圆盘。

问题归纳

首先把n-1个小的圆盘移动到一个不同的桩柱上(需要T~n-1~次移动)，然后移动最大的圆盘(需要一次移动)，最后再把那n-1个小圆盘移到最大的圆盘上(这需要另外的T~n-1~次移动)

这样就需要2T~n-1~  +  1次移动就能移动n个圆盘了。

现在我们就可以根据得到的递归式连续计算T3=2*3+1=7，T4=2*7+1=15……

然后就根据上续计算结果用数学归纳法得到T~n~=2^n - 1

现在我们就已经把问题分析透彻了，只需要转化为代码就可以了

代码实现

现在设有N个盘子从X杆经由Y杆移动到Z杆

hanoi (N - 1, X , Y , Z );把n-1只碟子从X杆经Z杆移动到Y杆

move(X , Z);将X杆上第n只碟子移动到Z杆

hanoi (N - 1, Y , X , Z );然后再将n-1只碟子从Y杆经X杆移到Z杆

#include <stdio.h>
void hanoi(int, char, char, char);
void move(char, char);
int main()
{
  int n = 0;
  printf("Please input n:");
  scanf("%d", &n);
  hanoi(n, 'a', 'b', 'c');
  return 0;
}
//有n个圆盘，从x移到z，用y作临时存放
void hanoi(int n, char x, char y, char z)
{
  if (n == 1)
    move(x, z);
  else
  {
    hanoi(n - 1, x, z, y);
    move(x, z);
    hanoi(n - 1, y, x, z);
  }
}
//显示圆盘的移动
void move(char c1, char c2)
{
  printf("%c -> %c\n", c1, c2);
}