经典递归 - 汉诺塔问题

最近，想复习一下C语言，所以笔者将会在掘金每天更新一篇关于C语言的文章！ 各位初学C语言的大一新生，以及想要复习C语言/C++知识的不要错过哦！ 夯实基础，慢下来就是快！

汉诺塔问题

百度百科

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

不管这个传说的可信度有多大，如果考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时，

假如每秒钟一次，共需多长时间呢？一个平年365天有31536000秒，闰年366天有31622400秒，平均每年31557600秒，计算一下：

18446744073709551615秒

问题分析

A上面放的盘子上面小下面大，借助B盘，将A中的盘子移动到C，移动时要保证B,C的盘子都是上面小下面大,要一个一个盘子移动

解决方法

解决方法:

1.把A中的n-1个盘子通过C移动到B

2.把A中的剩余的1个盘子移到C

3.把B中的n-1个盘子，通过A移到C 不断递归

代码分析

void move(char pos1, char pos2) { printf("%c->%c ", pos1, pos2); } /* n:要移动的盘子数， pos1：起始位置 pos2：中转位置 pos3：目的位置 */ void Hanoi(int n, char pos1, char pos2, char pos3) { if (n == 1) { move(pos1, pos3); //只有一个盘子，直接从pos1->pos3 } else { /*(1)以C盘为中介，从A杆将1至n - 1号盘移至B杆； (2)将A杆中剩下的第n号盘移至C杆； (3)以A杆为中介；从B杆将1至n - 1号盘移至C杆。*/ Hanoi(n - 1, pos1, pos3, pos2); //以C盘为中介，从A杆将1至n - 1号盘移至B杆 move(pos1, pos3);//将A杆中剩下的一个盘移至C杆； Hanoi(n - 1, pos2, pos1, pos3);//以A杆为中介；从B杆将1至n - 1号盘移至C杆。 } } int main() { Hanoi(3, 'A', 'B', 'C'); return 0; }

明天将会给大家带来经典下一个经典的递归问题-青蛙跳台阶问题！欢迎大家关注

今天就先到这吧~感谢你能看到这里！希望对你有所帮助！欢迎老铁们点个关注订阅这个专题！ 同时欢迎大佬们批评指正！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。