题目
在汉诺塔规则的基础上，限制不能从最左的塔移动到最右的塔上，必须经过中间的塔，移动的跨度只能是一个塔。当塔有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);
}
}
