急求Java 汉诺塔 编程!!

来源:百度知道 编辑:UC知道 时间:2024/06/28 14:57:12
假设汉诺塔中A和C柱不能直通,需要经过B柱才行,共需移动多少次?

递归的算法
用子树的概念可以递归地表示出汉诺塔难题的解决办法。假设想要把所有的盘子从源塔座(称为S)上移动到目标塔座上(称为D)。有一个可以使用的中介塔座(称为I)。假定在塔座S上有N 个盘子。算法如下:
1、 从塔座S移动包含上面的N-1个盘子的子树到塔座I上。
2、 从塔座S移动剩余的盘子(最大的盘子)到塔座D上。
3、 从塔座I移动子树到塔座D。
当开始的时候,源塔座是A,中介塔座是B,目标塔座是C。A上面有四个盘子。
首先,包括盘子1、2和3的子树被移动到中介塔座B上。于是,最大的盘子4,移动到塔座C上。然后子树从塔座B移动到塔座C上。
当然,这个方法没有解决如何把包括盘子1、2和3的子树移动到塔座B上的问题,因为不能一次性的移动一颗子树;每次只能移到一个盘子。移动三个盘子的子树不是那么容易的。但是,这比移动4个盘子要容易。
从塔座A上移动三个盘子到目标塔座B可以通过像移动四个盘子时一样的三个步骤来完成。那也就是说,从塔座A上移动包括最上面的两个盘子的子树到中介塔座C上;接着从A上移动盘子3到塔座B上。然后把子树从塔座C移回塔座B。
如何把一棵有两个盘子的子树从塔座A上移动到塔座C上呢?从塔座A上移动只有一个盘子的子树到塔座B上。这是基值条件:当移动一个盘子的时候,只要移动它就可以了:没有其他的事情要做。然后从塔座A移动更大的盘子到塔座C,并且把这棵子树重新放置在这个更大的盘子上。

towers.java程序使用递归的办法解决了汉诺塔难题。这个程序通过显示来报告所发生的移动:这个递归算法比显示汉诺塔的比码要少得多。这个算法适合于人来读这个程序清单,然后实际执行这些移动。
这个程序的代码极为简单。Main()方法调用了递归方法doTowers()。然后doTower()方法递归的调用自己,直到解决这个难题。初始时只有三个盘子,但是可以用任何盘子数来重新编译这个程序。
public class TowersApp {
static int nDisks=3;
public static void ma