用栈来求解汉诺塔问题

时间：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中查看

标签：

相关文章