用栈来求解汉诺塔问题

时间:2021-05-23 11:08:49

题目

  在汉诺塔规则的基础上,限制不能从最左的塔移动到最右的塔上,必须经过中间的塔,移动的跨度只能是一个塔。当塔有N层的时候,打印最优移动过程和最优移动步数。

要求

  • 方法一:使用递归的方法进行移动
  • 方法二:使用栈进行移动

解答思路

方法一:

  无论多少层,都看作有两层,最大的一层(命名为X)、(N-1)层合并起来的作为一层(命名为Y),目标是将X移动到最右侧,然后再把Y移动到最右侧。

用栈来求解汉诺塔问题

递归的移动方式:
  • Y从A塔移动到B塔
  • Y从B塔移动到C塔
  • X从A塔移动到B塔
  • Y从C塔移动到B塔
  • Y从B塔移动到A塔
  • X从B塔移动到C塔
  • 将Y看做X,继续递归移动
实现代码:
import java.util.Stack;

/**
 * 每次移动只能移动一个柱子,不能跨柱子移动
 * @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);
    }
}

方法二:

  使用栈而不使用递归的方式进行移动,使用3个栈模拟3个塔,每一步的移动,都按照真实情况进行。
  按照规则,可能的移动动作限定为LM、ML、MR、RM四种步骤(L、M、R分布表示左中右),通过引入逆反原则和小压大原则,可以得出每次移动,只有一种可行步骤。

逆反原则

  当执行了LM,如果此时下一步执行ML,叫做逆反操作,这样会使得汉诺塔还原为上一步的形状,白走多一步,这样明显不是最优的方法,所以不能够执行逆反操作,叫逆反原则。

小压大原则

  当移动时,小的块总是在大块之上,叫小压大原则。

限制分析

当上一步为:LM,下一步的情况分析:

  • 执行LM,违反小压大原则
  • 执行ML,违反逆反原则
  • 执行MR还是RM,按照小压大原则,这两种情况是互斥的,只能按条件二选一

其他分析类似,省略...

实现代码

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

import java.util.Stack;

/**
 * 使用栈模拟汉诺塔移动,将towerA全部层移动到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中查看