递归-汉诺塔

2019年04月10日 ⁄ 综合 ⁄ 共 1516字 ⁄ 字号 评论关闭

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.

```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()```