题目
Hanoi(汉诺)塔问题。这是一个古典的数学问题，是一个用递归方法解题的典型例子。问题是这样的：古代有一个梵塔，塔内有3座A,B,C。开始时A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。有一个老和尚想把这64个盘子从A座移到C座，但规定每次只允许移动一个盘，且在移动过程中在3个座上都始终保持大盘在下，小盘在上。在移动过程中可以利用B座。要求输出移动盘子的步骤
对小数值m的简单剖析
当一个题目难以解决的时候，我们就要学会将这个难题进行简化。
我们会创建一个函数hanoi，函数的功能就是将m个盘子从a转移到c。
当 m=1 时
我们只需要A -> C 就可以了。
int main() { hanoi(m,'A','B','C');//这里简洁写，是为了方便理解。 } void move(char x,char y)//move函数功能只是将结果打印出来 { printf("%c->%c\n"); } void haoni(int m,char a,char b,char c)//m=1进入函数，将1个盘子从a转移到c. { if(m==1) move(a,c); }
当 m=2 时
当m=2时，操作又会有些不同，往后的（1）（3）盘数会发生改变，所以这里的（1）（3）就提前用递归的方式解决
(1)先将1个盘从A放到B
// m=2，将m-1个盘子从A移到B
(2)再把A的1个盘放到C
(3)最后把B的1个盘放到C
// m=2，将m-1个盘子从B移到C
A->B A->C B->C
因为hanoi的功能就是把m个盘子从a移到c。
所以我们想要从A移到B时，我们只需要，传参的时候将A照常赋给a，将B赋给c就可以了。
int main() { hanoi(m,'A','B','C');//这里简洁写，是为了方便理解。m=2 } void haoni(int m,char a,char b,char c)//m=2从这里进来，haoni的功能就是把m个盘子从A移动到C { if(m==1) move(a,c);//跳过 else { hanoi(m-1,a,c,b);//步骤（1)先将1个盘从A放到B,实参为a,c,b,传过去的数据顺序实际为A,C,B move(a,c); // 步骤(2)再把A的一个盘放到C haoni(m-1,b,a,c);// 步骤(3)最后把B的盘放到C,实参为b,a,c,传过去的数据顺序实际为B,A,C } } //进一步分析 //步骤（1） hanoi(int m,char a,char b,char c)//m=1,由于传来的数据顺序为，A,C,B,因此这里的a=A,b=C,c=B { if(m=1) move(a,c);//打印的结果为 A->B //后面的函数没有用到就不多余写了 } //步骤（2） void move(char x,char y)//move的参数是（a,c）,a='A',b='B',c='C', { printf("%c->%c\n");//结果：A->C } //步骤（3） hanoi(int m,char a,char b,char c)//m=1,由于传来的数据顺序为，A,C,B,因此这里的a=B,b=A,c=C { if(m=1) move(a,c);//打印的结果为 B->C //后面的函数没有用到就不多余写了 }
函数move的解析
void move(char x,char y) { printf("%c->%c\n"); } void haoni(int m,char a,char b,char c) { if(m==1) move(a,c); } //因为函数move的实参是a,c,其实move打印的都是传过来的形参顺序的第一个和第三个 //void haoni(int m,char a,char b,char c)， 1.如果传给函数haoni的参数是，'A','B','C' move打印的就是A->C 2.如果传给函数haoni的参数是，'A','C','B' move打印的就是A->B 3.如果传给函数haoni的参数是，'B','A','C' move打印的就是B->C
当 m=3 时
递归就是从结果递推回去，将步骤简化，难的步骤就用递归分解
我们建立函数hanoi( m,'A','B','C'),函数的作用就是把a座上的m个盘子移到c座上
（1）将A座上2个盘子一道B座上（借助C座）//需要用到递归分解
（2）将A座上1个盘子一道C座上，
（3）将B座上2个盘子一道C座上（借助A座）//需要用到递归分解
分析步骤（1）（3）递归
分解（1）（3）步骤中将2个盘子从一个柱子移到另一个柱子。
（1）将两个盘子从A移到B，是不是和m=2时（将2个盘子从A移到C的原理是一样的），只不过这里是从A移动到B，通过改变'A','B','C'传过去的顺序，我们就可以实现从A移动到B。
（3）（c）->（d）我们要解决的是如何将两个盘子从B移到C，其实和（1）本质上是一样的，都是将m-1个盘子从一个柱子转移到另一个柱子上，我们都可以通过hanoi函数完成。
int main() { hanoi(m,'A','B','C');//这里简洁写，是为了方便理解。m=3 } void haoni(int m,char a,char b,char c)//m=3进入函数 { if(m==1) move(a,c);//跳过 else { hanoi(m-1,a,c,b);//步骤（1）m-1=2,这里的a='A',b='B',c='C',所以传过去的是'A','C','B' move(a,c); haoni(m-1,b,a,c);//步骤（3）m-1=2,这里的a='A',b='B',c='C',所以传过去的是'B','A','C' } }
步骤（1）的递归分解
//步骤（1） hanoi(int m,char a,char b,char c)//由于传来的数据顺序为，A,C,B,因此这里的a=A,b=C,c=B //这里的m=2 { if(m=1) move(a,c);//跳过 else { hanoi(m-1,a,c,b);//步骤（1.1）m-1=1，a=A,b=C,c=B,那么我们传过去的是'A','B','C' move(a,c); haoni(m-1,b,a,c);//步骤（1.3）m-1=1，a=A,b=C,c=B,那么我们传过去的是'C','A','B' } } //步骤（1.1） hanoi(int m,char a,char b,char c)//m=1,由于传来的数据顺序为，A,B,C,因此这里的a=A,b=B,c=C { if(m=1) move(a,c);//打印的结果为 A->C //后面的函数没有用到就不多余写了 } //步骤（1.2） void move(char x,char y)//move的参数是（a,c）,a='A',b='C',c='B', { printf("%c->%c\n");//结果：A->B } //步骤（1.3） hanoi(int m,char a,char b,char c)//m=1,由于传来的数据顺序为，C,A,B,因此这里的a=C,b=A,c=B { if(m=1) move(a,c);//打印的结果为 C->B //后面的函数没有用到就不多余写了 }
步骤（2）
//步骤（2） void move(char x,char y)//move的参数是（a,c）,a='A',b='B',c='C', { printf("%c->%c\n");//结果：A->C }
步骤（3）的递归分解
//步骤（3） hanoi(int m,char a,char b,char c)//由于传来的数据顺序为，B,A,C,因此这里的a=B,b=A,c=C //这里的m=2 { if(m=1) move(a,c);//跳过 else { hanoi(m-1,a,c,b);//步骤（3.1）m-1=1，a=B,b=A,c=C,那么我们传过去的是'B','C','A' move(a,c); haoni(m-1,b,a,c);//步骤（3.3）m-1=1，a=B,b=A,c=C,那么我们传过去的是'A','B','C' } } //步骤（3.1） hanoi(int m,char a,char b,char c)//m=1由于传来的数据顺序为，B,C,A,因此这里的a=B,b=C,c=A { if(m=1) move(a,c);//打印的结果为 B->A //后面的函数没有用到就不多余写了 } //步骤（3.2） void move(char x,char y)//move的参数是（a,c）,a='B',b='A',c='C', { printf("%c->%c\n");//结果：B->C } //步骤（3.3） hanoi(1,char a,char b,char c)//m=1,由于传来的数据顺序为，A,B,C,因此这里的a=A,b=B,c=C { if(m=1) move(a,c);//打印的结果为 A->C //后面的函数没有用到就不多余写了 }
大数值m=64
大数值的代码，也只是m的数值发生改变，通过下面的代码依旧可以运行。
完整代码
#include<stdio.h> void move(char x,char y) { printf("%c->%c\n"); } void haoni(int m,char a,char b,char c) { if(m==1) move(a,c); else { hanoi(m-1,a,c,b); move(a,c); haoni(m-1,b,a,c); } } int main() { int m=0; printf("请输入盘子的数量:")' scanf("%d",&m) printf("移动 %d 盘子的步骤:\n",m); haoni(m,'A','B','C'); return 0； }
