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 + "步");
  }
}

总结

以上就是本文关于java编程用栈来求解汉诺塔问题的代码实例（非递归）的全部内容，希望对大家有所帮助。感兴趣的朋友可以参阅：java 蒙特卡洛算法求圆周率近似值实例详解、java遗传算法之冲出迷宫、java实现四则混合运算代码示例等，有什么问题可以随时留言，欢迎大家交流讨论。