读书笔记之汉诺塔变型题

读书笔记之汉诺塔变型题"/>

读书笔记之汉诺塔变型题

汉诺塔问题增加条件：左边的塔到达右边的塔必须要经过中间的塔才可以

解题思路：

1. 递归的方式 ：如果只有一层塔的情况 以及n层塔的情况
2. 使用堆栈的方式：考虑最佳的方式中 不能原路返回 以及上边的小于下边的要求

//使用栈的代码
package Charpter1;import java.util.Stack;public class hanoiProble2 {public static enum Action{No,LToM,MToL,MToR,RToM}public static int hanoiProble(int num,String left,String mid,String right){Stack<Integer> lS = new Stack<>();Stack<Integer> mS = new Stack<>();Stack<Integer> rS = new Stack<>();lS.push(Integer.MAX_VALUE);mS.push(Integer.MAX_VALUE);rS.push(Integer.MAX_VALUE);for (int i=num;i>0;i--){lS.push(i);}Action[] record ={Action.No};int step=0;while(rS.size() != num+1){step+=fStackToStack(record,Action.MToL,Action.LToM,lS,mS,left,mid);step+=fStackToStack(record,Action.LToM,Action.MToL,mS,lS,mid,left);step+=fStackToStack(record,Action.RToM,Action.MToR,mS,rS,mid,right);step+=fStackToStack(record,Action.MToR,Action.RToM,rS,mS,right,mid);}return step;}public static int fStackToStack(Action [] record,Action preNoAct,Action nowAct,Stack<Integer> fStack,Stack<Integer> tStack,String from,String to){if(record[0] !=preNoAct && tStack.peek()>fStack.peek()){tStack.push(fStack.pop());System.out.println("Move " + tStack.peek() + "from "+from +"to"+to);record[0]=nowAct;return 1;}return 0;}public static void main(String [] args){System.out.println(hanoiProble(2,"left","mid","rigth"));}
}