Java编程用栈来求解汉诺塔问题的代码实例（非递归）-编程学习网

【题目】

　　汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有N层的时候，打印最优移动过程和最优移动总步数。

【解答】

　　上一篇用的是递归的方法解决这个问题，这里我们用栈来模拟汉诺塔的三个塔，也就是不用递归的方法

　　原理是这样的：修改后的汉诺塔问题不能让任何塔从左直接移动到右，也不能从右直接移动到左，而是要经过中间，也就是说，实际上能做的动作，只有四个：左->中，中->左，中->右，右->中

　　用栈来模拟汉诺塔的移动，其实就是某一个栈弹出栈顶元素，压入到另一个栈中，作为另一个栈的栈顶，理解了这个就好说了，对于这个问题，有两个原则：

　　一：小压大原则，也就是，要压入的元素值不能大于要压入的栈的栈顶的元素值，这也是汉诺塔的基本规则

　　二：相邻不可逆原则，也就是，我上一步的操作如果是左->中，那么下一步的操作一定不是中->左，否则就相当于是移过去又移回来

　　有了这两个原则，就可以推导出两个非常有用的结论：

　　1、游戏的第一个动作一定是L->M

　　2、在走出最小步数过程中的任何时刻，四个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反

【代码实现】

import java.util.Stack;class Demo{  public enum Action{    No,LToM,MToL,MToR,RToM  }  //num是盘子的数量，left，mid，right分别代表左中右三个柱子  public static int hanoi(int num,String left,String mid,String right){    //lS,mS,rS代表左中右三个栈（模拟柱子）    Stack<Integer> lS = new Stack<Integer>();    Stack<Integer> mS = new Stack<Integer>();    Stack<Integer> rS = new Stack<Integer>();    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.MToR,Action.RToM,rS,mS,right,mid);      step += fStackToStack(record,Action.RToM,Action.MToR,mS,rS,mid,right);    }    return step;  }  //preNoAct是与现在所要进行的动作相反的动作，nowAct是现在所要进行的动作  public static int fStackToStack(Action[] record,Action preNoAct,Action nowAct,Stack<Integer> fStack,Stack<Integer> tStack,String from,String to){    if(record[0] != preNoAct && fStack.peek() < tStack.peek()){      tStack.push(fStack.pop());      System.out.println("Move " + tStack.peek() + " " + from + "->" + to);      record[0] = nowAct;      return 1;    }    return 0;  }  public static void main(String[] args){    int i = hanoi(3,"left","mid","right");    System.out.println("一共走了" + i + "步");  }}

阅读原文内容投诉

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341