首页 > 代码库 > 汉诺塔问题（递归、栈）
汉诺塔问题（递归、栈）
修改一下汉诺塔的游戏规则，现在不能直接从左边走到右边，也不能直接右边走到左边。
方法一：递归实现
现在分析一下，比如左边有1~n，那么移动最后一个的情况，就是：
1.1-n-1从左边移动到右边
2.n从左边移动到中间
3.1-n-1从右边移动到左边
4.n从中间移动到右边
5.1-n-1从左边移动到右边
那么，假如我有这样一个f(range,from,to)那么我需要求解的就是f(n,lrft,right),原子情况就是从只有一个数的时候，直接左边中间右边即可。
1 public static int process(int num, String from, String to) { 2 if (num == 1) { 3 System.out.println("move 1 from " + from +" to middle"); 4 System.out.println("move 1 from middle to " + to); 5 return 2; 6 } 7 else { 8 int p1 = process(num - 1, from, to); 9 System.out.println("move "+ num + " from " + from +" to middle");10 int p2 = process(num - 1, to, from);11 System.out.println("move "+ num + " from middle to " + to);12 int p3 = process(num - 1, from, to);13 return p1 + p2 + p3 +2;14 }15 }
方法二：使用栈来实现
这样思考，一共有的动作一共就四种：L2M M2L M2R R2M
在任何一个时刻，要想最少移动次数，并且满足小压大原则，则只有一种情况能够得到满足。
证明如下：
假如上一个动作是L2M,那么不可能L2M(小压大),也不可能M2L(最优)，那么剩下M2R和R2M，就一定有一种情况会得到满足。其他情况同理。
所以使用三个栈分别记录左中右的数，然后每次检测出满足条件的那个来继续即可。由于每个都会去除每个栈的栈顶元素来进行比较，所以为了避免判断是否为空，就首先在每个栈的栈顶压入最大值以最为保障。结束的条件就是最右边的栈中元素个数为总的元素个数。
1 public static enum Action { 2 No,L2M, M2L,M2R,R2M 3 } 4 public static int hanoiProblem2(int num) { 5 Stack<Integer> ls = new Stack<Integer>(); 6 Stack<Integer> ms = new Stack<Integer>(); 7 Stack<Integer> rs = new Stack<Integer>(); 8 ls.push(Integer.MAX_VALUE); 9 ms.push(Integer.MAX_VALUE);10 rs.push(Integer.MAX_VALUE);11 for (int i = num; i > 0; i--) {12 ls.push(i);13 }14 Action[] preAction = {Action.No};15 int step = 0;16 while (rs.size() != num + 1) {17 step += fStack2Stack(preAction,Action.M2L,Action.L2M,ls,ms);18 step += fStack2Stack(preAction,Action.L2M,Action.M2L,ms,ls);19 step += fStack2Stack(preAction,Action.R2M,Action.M2R,ms,rs);20 step += fStack2Stack(preAction,Action.M2R,Action.R2M,rs,ms);21 }22 return step;23 }24 public static int fStack2Stack(Action[] preAction, Action noAction, Action curAction,25 Stack<Integer> fStack, Stack<Integer> tStack) {26 if (preAction[0] == noAction || fStack.peek() >= tStack.peek()) {27 return 0;28 }29 preAction[0] = curAction;30 tStack.push(fStack.pop());31 return 1;32 }
汉诺塔问题（递归、栈）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。