程式員代碼面試指南刷題--第一章.用棧來求解漢諾塔問題

題目描述

漢諾塔問題比較經典，這裡修改一下遊戲規則：現在限制不能從最左側的塔直接移動到最右側，也不能從最右側直接移動到最左側，而是必須經過中間。求當塔有n層的時候，列印最優移動過程和最優移動總步數。

輸入描述:

輸入一個數n，表示塔層數

輸出描述:

按樣例格式輸出最優移動過程和最優移動總步數

示例1
輸入

2

輸出

Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move 8 steps.
           

說明

解法一：遞歸

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine().trim());
        int res = H(num,"left","right","mid");
        System.out.println("It will move "+res+" steps.");
    }
    public static int H(int n,String from,String to,String mid){
        if(n==1){
            if(from.equals("mid")||to.equals("mid")){
                System.out.println("Move 1 from "+from+" to "+to);
                return 1;
            }else{
                System.out.println("Move 1 from "+from+" to "+mid);
                System.out.println("Move 1 from "+mid+" to "+to);
                return 2;
            }
        }
        if(from.equals("mid")||to.equals("mid")){
            int p1 = H(n-1,from,mid,to);
            System.out.println("Move "+n+" from "+from+" to "+to);
            int p2 = H(n-1,mid,to,from);
            return p1+1+p2;
        }else{
            int p1 = H(n-1,from,to,mid);
            System.out.println("Move "+n+" from "+from+" to "+mid);
            int p2 = H(n-1,to,from,mid);
            System.out.println("Move "+n+" from "+mid+" to "+to);
            int p3 = H(n-1,from,to,mid);
            return p1+p2+p3+2;
        }
    }
}
           

解法二：非遞歸

import java.io.*;
import java.util.*;
public class Main{
    public static Action record = Action.no;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine().trim());
        int res = H(num,"left","right","mid");
        System.out.println("It will move "+res+" steps.");
    }
    public static int H(int n,String left,String right,String mid){
        Stack<Integer> l = new Stack<>();
        Stack<Integer> m = new Stack<>();
        Stack<Integer> r = new Stack<>();
        l.push(Integer.MAX_VALUE);
        m.push(Integer.MAX_VALUE);
        r.push(Integer.MAX_VALUE);
        for(int i=n;i>0;i--){
            l.push(i);
        }
        int step = 0;
        while(r.size()!=n+1){
            //隻有一個能執行
            step += fsTots(Action.mtr,Action.rtm,r,m,right,mid);
            step += fsTots(Action.rtm,Action.mtr,m,r,mid,right);
            step += fsTots(Action.mtl,Action.ltm,l,m,left,mid);
            step += fsTots(Action.ltm,Action.mtl,m,l,mid,left);
        }
        return step;
    }
    public static int fsTots(Action preno,Action now,Stack<Integer> fs,Stack<Integer> ts,String from,String to){
        if(record!=preno&&fs.peek()<ts.peek()){
            record = now;
            ts.push(fs.pop());
            System.out.println("Move "+ts.peek()+" from "+from+" to "+to);
            return 1;
        }    
        return 0;
    }
    enum Action{
        no,ltm,mtl,rtm,mtr
    }
}