快捷導(dǎo)航

Java編程用棧來求解漢諾塔問題的代碼實(shí)例（非遞歸）

更新時間：2017年10月11日 09:43:27 作者：凌風(fēng)暨

這篇文章主要介紹了Java編程用棧來求解漢諾塔問題的代碼實(shí)例（非遞歸），具有一定參考價值，這里給大家分享下，供朋友們參考。

【題目】

　　漢諾塔問題比較經(jīng)典，這里修改一下游戲規(guī)則：現(xiàn)在限制不能從最左側(cè)的塔直接移動到最右側(cè)，也不能從最右側(cè)直接移動到最左側(cè)，而是必須經(jīng)過中間。求當(dāng)塔有N層的時候，打印最優(yōu)移動過程和最優(yōu)移動總步數(shù)。

【解答】

　　上一篇用的是遞歸的方法解決這個問題，這里我們用棧來模擬漢諾塔的三個塔，也就是不用遞歸的方法

　　原理是這樣的：修改后的漢諾塔問題不能讓任何塔從左直接移動到右，也不能從右直接移動到左，而是要經(jīng)過中間，也就是說，實(shí)際上能做的動作，只有四個：左->中，中->左，中->右，右->中

　　用棧來模擬漢諾塔的移動，其實(shí)就是某一個棧彈出棧頂元素，壓入到另一個棧中，作為另一個棧的棧頂，理解了這個就好說了，對于這個問題，有兩個原則：

　　一：小壓大原則，也就是，要壓入的元素值不能大于要壓入的棧的棧頂?shù)脑刂?，這也是漢諾塔的基本規(guī)則

　　二：相鄰不可逆原則，也就是，我上一步的操作如果是左->中，那么下一步的操作一定不是中->左，否則就相當(dāng)于是移過去又移回來

　　有了這兩個原則，就可以推導(dǎo)出兩個非常有用的結(jié)論：

　　1、游戲的第一個動作一定是L->M

　　2、在走出最小步數(shù)過程中的任何時刻，四個動作中只有一個動作不違反小壓大和相鄰不可逆原則，另外三個動作一定都會違反

【代碼實(shí)現(xiàn)】

import java.util.Stack;
class Demo{
  public enum Action{
    No,LToM,MToL,MToR,RToM
  }

  //num是盤子的數(shù)量，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是與現(xiàn)在所要進(jìn)行的動作相反的動作，nowAct是現(xiàn)在所要進(jìn)行的動作
  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 + "步");
  }
}

總結(jié)

以上就是本文關(guān)于Java編程用棧來求解漢諾塔問題的代碼實(shí)例（非遞歸）的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以參閱：Java 蒙特卡洛算法求圓周率近似值實(shí)例詳解、Java遺傳算法之沖出迷宮、Java實(shí)現(xiàn)四則混合運(yùn)算代碼示例等，有什么問題可以隨時留言，歡迎大家交流討論。

您可能感興趣的文章: