资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

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 lS = new Stack();
    Stack mS = new Stack();
    Stack 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.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 fStack,Stack 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编程用栈来求解汉诺塔问题的代码实例(非递归)-创新互联
网页地址:http://www.cdkjz.cn/article/ddpsph.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220