題目：
??漢諾塔問題比較經(jīng)典，現(xiàn)在修改一下游戲規(guī)則：現(xiàn)在限制不能從最左側(cè)的塔直接到移動(dòng)最右側(cè)，也不能直接從最右側(cè)直接移動(dòng)到最左側(cè)，而是必須經(jīng)過中間。求當(dāng)塔有N層的時(shí)候，打印最右移動(dòng)過程和最右移動(dòng)總步數(shù)。
例如, 當(dāng)塔樹為兩層時(shí)，最上層的塔記為1，最下層記為2，則打?。?/em>
Move 1 from left to mid
Move 1 from mid to right
Move 2 from left to mid
Move 1 from right to mid
Move 1 from mid to left
Move 2 from mid to right
Move 1 from left to mid
Move 1 from mid to right
It will move steps.
要求：
方法一：遞歸的方法
方法二：非遞歸的方法，用棧來模擬漢諾塔三個(gè)塔
思路：
方法一遞歸的方法
首先，如果只剩最上層的塔需要移動(dòng)，則如下處理：
- 如果希望從“左”移動(dòng)到“中”，打印“Move 1 from left to mid”
- 如果希望從“中”移動(dòng)到“左”，打印“Move 1 from mid to left”
- 如果希望從“中”移動(dòng)到“右”，打印“Move 1 from mid to right”
- 如果希望從“右”移動(dòng)到“中”，打印“Move 1 from right to mid”
- 如果希望從“左”移動(dòng)到“右”，打印“Move 1 from left to mid” 和 “Move 1 from mid to right”
- 如果希望從“右”移動(dòng)到“左”，打印“Move 1 from right to mid” 和 “Move 1 from mid to left”
此6條就是遞歸的終止條件，也就是只剩上層塔是打印過程
如果剩下N層塔，從最上到最小依次1~N，則如下判斷：
1.如果剩下的N層塔都在最“左”，希望全部移動(dòng)到“中”，則如下三步
①. 將1~N-1層塔全部從“左”移到“右”，明顯交給遞歸過程
②. 將第N層塔從“左”移到“中”
③. 再將1~N-1層塔全部從“右”移到“中”，明顯交給遞歸
2.如果剩下的N層塔從“中”移到“左”，從“左”移到“右”，從“右”移到“中”，過程與情況1同理，一樣分為三步。
3.如果剩下的N層都在最“左”希望移到“右”，則分為五步
①. 將1~N-1層塔先全部從“左”移到“右”，明顯交給遞歸過程。
②. 將第N層塔從“左”移到“中”
③. 將1~N-1層塔全部從“右”移到“左”，明顯交給遞歸過程
④. 將第N層塔從“中”移到“右”
⑤. 將1~N-1層塔全部從“左”移到“右”，明顯交給遞歸過程
4.如果剩下的N層塔都在“右”，希望全部移到“左”，過程和情況3同理，同樣分為5步。
代碼演示
package com.itz.zcy.stackAndQueue;
/**
* 漢若塔問題
*/
public class Hanoi {
public int hanoiProbleml(int num, String left, String mid, String right) {
if (num < 1) {
return 0;
}
return process(num, left, mid, right, left, right);
}
public int process(int num, String left, String mid, String right, String form, String to) {
if (num == 1) {
if (form.equals(mid) || to.equals(mid)) {
System.out.println("Move 1 from" + form + "to" + mid);
return 1;
} else {
System.out.println("Move 1 from" + form + "to" + mid);
System.out.println("Move 1 from" + mid + "to" + to);
return 2;
}
}
if (form.equals(mid) || to.equals(mid)) {
String another = (form.equals(left) || to.equals(left)) ? right : left;
int part1 = process(num - 1, left, mid, right, form, another);
int part2 = 1;
System.out.println("Move" + num + "form" + form + "to" + to);
int part3 = process(num - 1, left, mid, right, another, to);
return part1 + part2 + part3;
} else {
int part1 = process(num - 1, left, mid, right, form, to);
int part2 = 1;
System.out.println("Move" + num + "form" + form + "to" + mid);
int part3 = process(num - 1, left, mid, right, to, form);
int part4 = 1;
System.out.println("Move" + num + "form" + mid + "to" + to);
int part5 = process(num - 1, left, mid, right, form, to);
return part1 + part2 + part3 + part4 + part5;
}
}
}
方法二：非遞歸的方法——用棧來模擬整個(gè)過程
??修改后的的漢若塔問題不能在從“左”直接移到“右”，也不能直接“右”直接移到“右”，而是要經(jīng)過中間的過程。也就是說，實(shí)際只有4個(gè)動(dòng)作 “左”到“中”、“中”到“右”、“右”到“中”、“中”到“左”
?? 現(xiàn)在我們把左、中、右三個(gè)地點(diǎn)抽象成棧，依次記為L(zhǎng)S、MS和RS。最初所有的塔都在LS上。那么四個(gè)動(dòng)作就可以看作是：某一個(gè)棧（from）把棧頂元素彈出，然后壓入另一個(gè)棧里（to），作為這一個(gè)棧(to)是棧頂。
??例如，如果是7層塔，在最初時(shí)所有的塔都在LS上，LS從棧頂?shù)綏５拙鸵来?~7，如果現(xiàn)在發(fā)生了“左”到“中”的動(dòng)作，這個(gè)動(dòng)作對(duì)應(yīng)的操作是LS棧將棧頂元素1彈出，然后1壓入到MS棧中，成為MS的棧頂。其他操作同理。
??一個(gè)動(dòng)作能發(fā)生的先決條件是不違反小壓大的原則。
??from棧彈出的元素num如果想壓入到to棧中，那么num的值必須小于當(dāng)前to棧頂。
??還有一個(gè)原則不是很明顯，但也非常重要，叫相鄰不可逆原則，解釋如下：
?? 1. 我們把4個(gè)動(dòng)作依次定義為：L -> M，M -> L、M -> R和R -> M。
?? 2. 很明顯，L -> M和M -> L過程互為逆過程，M -> R和R -> M互為逆過程，
?? 3. 在修改后的漢若塔游戲中，如果想走出最少步數(shù)，那么如何兩個(gè)相鄰的動(dòng)作都不是互為逆的過程的。舉例：如果上一步的動(dòng)作是L -> M，那么這一步絕不是M -> L，直觀地解釋為：你在上一步把一個(gè)棧頂數(shù)從“左”移動(dòng)到“右”，這一步為什么又要移回去呢？這必然不是取得最小步數(shù)的作法。同理，M -> R動(dòng)作和R -> M動(dòng)作也不可能相鄰發(fā)生。
??有了小壓大和相鄰不可逆序原則后，可以推導(dǎo)出兩個(gè)十分有用的結(jié)論——非遞歸的方法核心結(jié)論：
???1.游戲的第一個(gè)動(dòng)作一定是L -> M，這顯而易見的。
???1.在走出最少步數(shù)過程中的任何時(shí)刻，4個(gè)動(dòng)作只有一個(gè)動(dòng)作不違反小壓大和相鄰不可逆原則，另外三個(gè)動(dòng)作一定都會(huì)違反。
??對(duì)于結(jié)論2，現(xiàn)在進(jìn)行簡(jiǎn)單的證明
??因?yàn)橛螒虻牡谝粋€(gè)動(dòng)作已經(jīng)確定是L -> M，則以后的每一步都會(huì)有前一步動(dòng)作。
??假設(shè)前一步的動(dòng)作是L -> M:
???1. 根據(jù)小壓大原則，L -> M的動(dòng)作不會(huì)重復(fù)發(fā)生
???2. 根據(jù)相鄰不可逆原則，M -> L的動(dòng)作也不該發(fā)生
???3. 根據(jù)小壓大原則，M -> R和R -> M只有一個(gè)達(dá)標(biāo)
??假設(shè)前一步的動(dòng)作是M -> L:
???1. 根據(jù)小壓大原則，M -> L的動(dòng)作不會(huì)重復(fù)發(fā)生
???2. 根據(jù)相鄰不可逆原則，L -> M的動(dòng)作也不該發(fā)生
???3. 根據(jù)小壓大原則，M -> R和R -> M只有一個(gè)達(dá)標(biāo)
??假設(shè)前一步的動(dòng)作是M -> R:
???1. 根據(jù)小壓大原則，M -> R的動(dòng)作不會(huì)重復(fù)發(fā)生
???2. 根據(jù)相鄰不可逆原則，R -> M的動(dòng)作也不該發(fā)生
???3. 根據(jù)小壓大原則，M -> L和L -> M只有一個(gè)達(dá)標(biāo)
??假設(shè)前一步的動(dòng)作是R -> M:
???1. 根據(jù)小壓大原則，R -> M的動(dòng)作不會(huì)重復(fù)發(fā)生
???2. 根據(jù)相鄰不可逆原則，M -> R的動(dòng)作也不該發(fā)生
???3. 根據(jù)小壓大原則，M -> L和L -> M只有一個(gè)達(dá)標(biāo)
??綜上所述，每一步只會(huì)有一個(gè)動(dòng)作達(dá)標(biāo)，那么只要每一步都根據(jù)這兩個(gè)原則考查所有的動(dòng)作就可以，那個(gè)動(dòng)作達(dá)標(biāo)就走哪一個(gè)動(dòng)作，反正每一次都只有一個(gè)動(dòng)作滿足要求，按順序走下來即可。
public class Hanoi {
public enum Action {
No, LToM, MToL, MToR, RToM
}
public int hanoiProblem2(int num, String left, String mid, String right) {
Stack<Integer> ls = new Stack<>();
Stack<Integer> ms = new Stack<>();
Stack<Integer> rs = new Stack<>();
ls.push(Integer.MAX_VALUE);
rs.push(Integer.MAX_VALUE);
ms.push(Integer.MAX_VALUE);
for (int i = num; i > 0; i--) {
ls.push(i);
}
Action[] record = {Action.No};
int step = 0;
while (rs.size() != num + 1) {
step += fStackToStack(record, Action.MToL, Action.LToM, ls, ms, left, mid);
step += fStackToStack(record, Action.LToM, Action.MToL, ms, ls, mid, left);
step += fStackToStack(record, Action.RToM, Action.MToR, ms, rs, mid, right);
step += fStackToStack(record, Action.MToR, Action.RToM, rs, ms, right, mid);
}
return step;
}
public static int fStackToStack(Action[] record, Action preNoAct, Action nowAct, Stack<Integer> fStack,
Stack<Integer> tStack, String from, String to) {
if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
tStack.push(fStack.pop());
System.out.println("Move" + tStack.peek() + "from" + from + "to" + to);
record[0] = nowAct;
return 1;
}
return 0;
}
}
總結(jié)
該題是一個(gè)漢諾塔的限條問題
文獻(xiàn)：左程云著 《程序員代碼面試指南IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》（第二版）
版權(quán)聲明：此文版權(quán)歸作者所有！
