黑马程序员技术交流社区
标题:
汉诺塔问题
[打印本页]
作者:
王振宇351x
时间:
2014-9-2 20:54
标题:
汉诺塔问题
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
要求,有三个柱子,,a,b,c,.a柱子从上到下依次有从小到大的5个圆盘,依次编号1-5,
b,c柱子没有圆盘.
要求,将5个圆盘移动到C,并且符合上面的规则.
要求输出,每一次移动的圆盘编号和从哪根柱子移动到哪根柱子..
作者:
SailY
时间:
2014-9-3 17:46
《算法程序与设计》里好像有这个程序，记得用得是递归，你可以找找
作者:
fantacyleo
时间:
2014-9-4 00:38
貌似是基础测试or入学测试题？老规矩，只给思路不给代码。
这道题是非常典型的递归，但不复杂，很直观。
比如要把5个盘子从1号柱子移动到3号柱子，步骤是：
把1－4号共4个盘子移到2号柱子
把5号共1个盘子移到3号柱子
把1－4号共4个盘子移到3号柱子
显然，如果把“从m号柱子按从小到大顺序移动k个盘子到n号柱子，p号柱子作为备用”定义为一个函数move(k,m,n,p)，那么move(5,1,3,2)函数中就要依次递归调用move(4,1,2,3) move(1,1,3,2) move(4,2,3,1)
化为一般形式，也就是在move(k,m,n,p)函数体中要依次递归调用move(k-1,m,p,n) move(1,m,n,p) move(k-1,p,n,m)
递归函数还必须有一个base case，也就是不再依赖递归的情形，本题中，显然“从m号柱子按从小到大顺序移动1个盘子到n号柱子，p号柱子作为备用”是base case，因为只要移动一个盘子，直接打印出来将盘子从m移动到n即可
完毕
作者:
星河鹭起
时间:
2014-9-4 13:49
递归问题。。楼主可以想想
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2