hanoi递归算法

hanoi递归算法 递归的算法 用子树的概念可以递归地表示出汉诺塔难题的解决。 假设想要把所有的盘子从源塔座(称为S)上移动到目标塔座上(称为D)。有一个可以使用的中介塔座(称为I)。假定在塔座S上有N 个盘子。算法如下: 1、 从塔座S移动包含上面的N-1个盘子的子树到塔座I上。 2、 从塔座S移动剩余的盘子(最大的盘子)到塔座D上。 从塔座I移动子树到塔座D。 3、 当开始的时候，源塔座是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 main(String[] args) { doTowers(nDisks,'A','B','C'); System.exit(0); }//......................... public static void doTowers(int topN,char from,char inter,char to) { if(topN==1) System.out.println("盘子 1 从 "+from+" 到"+to); else { doTowers(topN-1,from,to,inter); System.out.println("盘子 "+topN+" 从 "+from+" 到"+to); doTowers(topN-1,inter,from,to); } } } doTowers()的参数是要移动的盘子的数目，以及会使用到的源塔座(from)、中介塔座(inter)和目标塔座(to)。盘子数随着方法每调用一次就递减1。源塔座、中介塔座和目标塔座也就发生变化