題目

在漢諾塔規(guī)則的基礎(chǔ)上，限制不能從最左的塔移動(dòng)到最右的塔上，必須經(jīng)過中間的塔，移動(dòng)的跨度只能是一個(gè)塔。當(dāng)塔有N層的時(shí)候，打印最優(yōu)移動(dòng)過程和最優(yōu)移動(dòng)步數(shù)。

要求

• 方法一：使用遞歸的方法進(jìn)行移動(dòng)
• 方法二：使用棧進(jìn)行移動(dòng)

解答思路

方法一：

無論多少層，都看作有兩層，最大的一層(命名為X)、(N-1)層合并起來的作為一層(命名為Y)，目標(biāo)是將X移動(dòng)到最右側(cè)，然后再把Y移動(dòng)到最右側(cè)。

漢諾塔

遞歸的移動(dòng)方式：

• Y從A塔移動(dòng)到B塔
• Y從B塔移動(dòng)到C塔
• X從A塔移動(dòng)到B塔
• Y從C塔移動(dòng)到B塔
• Y從B塔移動(dòng)到A塔
• X從B塔移動(dòng)到C塔
• 將Y看做X，繼續(xù)遞歸移動(dòng)

實(shí)現(xiàn)代碼：

import java.util.Stack;

/**
 * 每次移動(dòng)只能移動(dòng)一個(gè)柱子,不能跨柱子移動(dòng)
 * @author zhanyongzhi
 */
public class HannoiOneStep {
    public void startMove(int count){
        move(count, "A", "B", "C");
    }

    private void move(int item, String from, String buffer, String to){
        //
        if(1 == item){
            System.out.println(String.format("move %d from %s to %s", item, from, buffer));
            System.out.println(String.format("move %d from %s to %s", item, buffer, to));
            return;
        }

        //general situation
        move(item - 1, from, buffer, to);
        System.out.println(String.format("move %d from %s to %s", item, from, buffer));
        move(item - 1, to, buffer, from);
        System.out.println(String.format("move %d from %s to %s", item, buffer, to));

        move(item - 1, from, buffer, to);
    }
}

方法二：

使用棧而不使用遞歸的方式進(jìn)行移動(dòng)，使用3個(gè)棧模擬3個(gè)塔，每一步的移動(dòng)，都按照真實(shí)情況進(jìn)行。
??按照規(guī)則，可能的移動(dòng)動(dòng)作限定為L(zhǎng)M、ML、MR、RM四種步驟（L、M、R分布表示左中右），通過引入逆反原則和小壓大原則，可以得出每次移動(dòng)，只有一種可行步驟。

逆反原則

當(dāng)執(zhí)行了LM，如果此時(shí)下一步執(zhí)行ML，叫做逆反操作，這樣會(huì)使得漢諾塔還原為上一步的形狀，白走多一步，這樣明顯不是最優(yōu)的方法，所以不能夠執(zhí)行逆反操作，叫逆反原則。

小壓大原則

當(dāng)移動(dòng)時(shí)，小的塊總是在大塊之上，叫小壓大原則。

限制分析

當(dāng)上一步為：LM，下一步的情況分析：

• 執(zhí)行LM，違反小壓大原則
• 執(zhí)行ML，違反逆反原則
• 執(zhí)行MR還是RM，按照小壓大原則，這兩種情況是互斥的，只能按條件二選一

其他分析類似，省略...

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

package com.github.zhanyongzhi.interview.algorithm.stacklist;

import java.util.Stack;

/**
 * 使用棧模擬漢諾塔移動(dòng),將towerA全部層移動(dòng)到towerC
 * @author zhanyongzhi
 */
public class HannoiStack {
    private Stack<Integer> towerA = new Stack<>();
    private Stack<Integer> towerB = new Stack<>();
    private Stack<Integer> towerC = new Stack<>();

    private MoveType preMoveType = MoveType.LM;

    enum MoveType{
        LM("Move From Left to Middle"),
        MR("Move From Middle to Right"),
        RM("Move From Right to Middle"),
        ML("Move From Middle to Left");

        private final String name;

        MoveType(String s) {
            name = s;
        }

        public boolean equalsName(String otherName) {
            return (otherName == null) ? false : name.equals(otherName);
        }

        public String toString() {
            return name;
        }
    }

    public void init(int size){
        for(int i=size; 0 < i; i--){
            towerA.push(i);
        }
    }

    public void startMove(){
        int layerSize = towerA.size();

        while(layerSize != towerC.size()){
            moveStack(MoveType.LM, MoveType.ML, towerA, towerB);
            moveStack(MoveType.MR, MoveType.RM, towerB, towerC);
            moveStack(MoveType.RM, MoveType.MR, towerC, towerB);
            moveStack(MoveType.ML, MoveType.LM, towerB, towerA);
        }
    }

    private void moveStack(MoveType tryMove, MoveType preventMove, final Stack<Integer> towerFrom, final Stack<Integer> towerTo){
        if(preMoveType == preventMove)
            return;

        if(towerFrom.empty())
            return;

        Integer sElement = towerFrom.peek();

        if(!towerTo.empty()){
            Integer dElement = towerTo.peek();

            if(sElement > dElement)
                return;
        }

        preMoveType = tryMove;

        System.out.println(tryMove);
        towerFrom.pop();
        towerTo.push(sElement);
    }
}

在github中查看