目录
问题背景
汉诺塔问题是由法国数学家卢卡斯于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);
}