各位前輩,
小弟了解河內塔的運作方式,
將n-1盤子 ⇒ 由來源木棒(A)移到輔助木棒(B)
將最大盤子 ⇒ 由來源木棒(A)移到目的木棒(C)
將n-1盤子 ⇒ 由新的來源木棒(B)透過新的輔助木棒(A)移到目的木棒(C)
程式碼如下:
private static void hanoi(int n, char sour, char aux, char dest){
if(n == 1){
System.out.printf("Move disk %d from %c to %c\n", n, sour, dest);
System.out.println("n = 1");
}
else{
//將A上n-1個盤子借助C移到B
hanoi(n-1, sour, dest, aux);
System.out.printf("Move disk %d from %c to %c\n", n, sour, dest);
System.out.println("print");
//將B上n-1個盤子借助A移到C
hanoi(n-1, aux, sour, dest);
}
}
想很久(想破頭了)還是想不通他的執行順序和結果為什麼是這樣?
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
問題一: 遞迴不是"先進後出"嗎? 請教一下哪裡想錯了?
第一次hanoi呼叫
n=3,hanoi(2, A, C, B),結果Move disk 2 from A to B
n=2,hanoi(1, A, C, B),結果Move disk 1 from A to B
n=1,結果Move disk 1 from A to C
輸出把順序顛倒
n=1,結果Move disk 1 from A to C
n=2,hanoi(1, A, C, B),結果Move disk 1 from A to B
n=3,hanoi(2, A, C, B),結果Move disk 2 from A to B
中間輸出Move disk 3 from A to C
第二次hanoi呼叫
n=3,hanoi(2, B, A, C),結果Move disk 2 from B to C
n=2,hanoi(1, B, A, C),結果Move disk 1 from B to C
n=1,結果Move disk 1 from A to C
輸出把順序顛倒
n=1,結果Move disk 1 from A to C
n=2,hanoi(2, B, A, C),結果Move disk 1 from B to C
n=3,hanoi(1, B, A, C),結果Move disk 2 from B to C
問題二: 每呼叫一次方法,都會執行到print,那方法裡面不是有兩個hanoi,hanoi也會被呼叫兩次? |