題目
在漢諾塔規(guī)則的基礎(chǔ)上三椿，限制不能從最左的塔移動(dòng)到最右的塔上箩兽，必須經(jīng)過(guò)中間的塔绅项，移動(dòng)的跨度只能是一個(gè)塔。當(dāng)塔有N層的時(shí)候比肄，打印最優(yōu)移動(dòng)過(guò)程和最優(yōu)移動(dòng)步數(shù)。
要求
- 方法一：使用遞歸的方法進(jìn)行移動(dòng)
- 方法二：使用棧進(jìn)行移動(dòng)
解答思路
方法一：
無(wú)論多少層囊陡，都看作有兩層芳绩，最大的一層(命名為X)、(N-1)層合并起來(lái)的作為一層(命名為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分布表示左中右），通過(guò)引入逆反原則和小壓大原則咧擂，可以得出每次移動(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悉稠，按照小壓大原則，這兩種情況是互斥的艘包，只能按條件二選一
其他分析類(lèi)似的猛，省略...
實(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);
}
}
