记得大一上C语言课程的时候我还刚刚会用迅雷下载电影，听不懂，也没认真听过，匆匆几个星期上完了考试。关于“汉诺塔”这样的字眼，也是仅仅记得是在那个书里面出现过而已。最近偶然拿起C语言的书，再次看到了“汉诺塔”递归算法的例子，转好几圈，终于搞明白了。现在花点时间重新这里下思路，一则方便自己以后回忆，二则希望能给和我一样菜的新手们提供参考，三则希望有高人出现对文中不足的地方加以斧正！
关于“汉诺塔”这个古老的益智游戏如果不清楚的，到百度百科一下！
为了方便理解，这里首先创造三个概念：源，踏板，目标。
如果任务是：将A上的圆盘移动至C，我们称A为源，B为踏板，C为目标。
思路：1 要是源上只有一个圆盘，只直接将圆盘移动至目标。（无需借助踏板过渡）
2 要是源上有n（n>1）个圆盘，则分为下面三个步骤完成。（借助踏板）
A先将前n-1个移动到踏板上（由上至下的顺序） 先移动到踏板上。（任务细分，重复1，2两个步骤）
B 再将最后(第n个)一个移动至目标。
C 最后在将踏板上的全部移动至目标。（任务细分，重复1，2两个步骤）
就上图一我们按照上面的思路递归一下整个过程：
第一层：进栈
任务：A （源） 移动3 C（目标） ，n=3>1，所以借助B(踏板)，先将 前两个先
移动至B，再将最后一个移动至C，最后将踏板上的移动至C。
第二层：进栈
任务：A （源）移动2 B（目标） ，n=2>1，所以借助C(踏板)，先将前 一个先
移动C,再将当前任务的最后一个移动至B，最后将踏板C上的移动至B。
第三层：进栈
任务：A （源） 移动1 C（目标） ，n=1=1，直接将A上最上面一个移动至C；
出栈。
回溯到第二层：
将当前任务的最后一个移动至B。
|
|
|||||
|
踏板C上的移动至目标B
出栈。
回溯到第一层: 现在已经完成了将A上的上面两个移动至踏板B上，现在还剩下两个步骤： 将A上的一个移动到C上，将踏板B上的两个移动到C上。 1将A上的移动到C上。
2 将B的两个移动到C 上。分两步进行： 第二层：进栈 借助A为踏板，先将B得上一个移动到A上。
将B上的最底下一个移动至目标C
踏板A上的移动至目标C
出栈 出栈 自此，整个任务完成！
C/C++代码： int main() { void hanoi(int n,char origin,char bridge,char destination); // 对hanoi函数的声明 intm; printf("input the number of diskes:"); scanf("%d",&m); printf("The step to move %d diskes:\n",m); hanoi(m,'A','B','C'); return 0; }
void hanoi(int n,char origin,charbridge,char destination) // 定义hanoi函数 // 将n个盘从origin座借助bridge座,移到 destination座 { void move(char x,char y); //对move函数的声明 if(n==1) move(origin,destination); else { hanoi(n-1,origin,destination,bridge); move(origin,destination); hanoi(n-1,bridge,origin,destination); } }
voidmove(char x,char y) // 定义move函数 { printf("%c-->%c\n",x,y); }
|
|||||