可以用递归实现,递归算法:
A source tower,B buffer tower ,C destination tower
1. Move the subtree consisting of the top n-1 disks from A to B.
2. Move the remaining (largest) disk from A to C.
3. Move the subtree from B to C.
Base Case:How do you move a subtree of two disks from A to C? Move the subtree consisting of only one disk (1) from A to B. This is the base case: When you’re moving only one disk, you just move it; there’s nothing else to do. Then move the larger disk (2)
from A to C, and replace the subtree (disk 1) on it.
从A移动到C的过程如下:
柱子数据结构:用栈实现
class Tower{ pirvate Stack diskStack; private int index; //the current tower's index in the Towers arrary public Tower(i){ diskStack=new Stack(); index=i; } public void add(int d){ if(!diskStack.isEmpty() && diskStack.peek()<=d){ System.out.println("Error placing disk " +d); } else diskStack.push(d); }//end add public int getIndex(){ return index; }//end getIndex() }//end class Tower
汉诺塔代码
public static void main(String[] args){ int diskNumber=5; //disks number int towerNumber=3; //tower number Tower[] towers=new Tower[3]; //initial tower's index in the towers' array for(int i=0;i<3;i++) towers[i]=new Tower(i); //initial towers[0] for(int i=diskNumber-1;i>=0;i--) towers[0].add(i); //move disk from 0 to 2 moveDisks(n,towers[0],towers[1],towers[2]); }//end main public static moveDisks(int n,Tower from,Tower buffer,Tower to){ if(n==1) //base case moveTop(from,to); else{ moveDisks(n-1,from,to,buffer); //from A to B moveTop(from,to);//from A to C moveDisks(n-1,buffer,from,to);//from B to C }//end else }//end moveDisks() private static moveTop(Tower from,Tower to){ int top=from.pop(); to.add(top); System.out.println("Move disk "+top+" from "+ from.getIndex()+" to "+ to.getIndex() ); }//end moveTop()