top

河內塔程式執行步驟

各位前輩,

小弟了解河內塔的運作方式,
將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也會被呼叫兩次?

一、因為它將輸出直接寫在方法裏了,就變成先遇到先輸出了。
二、是的。

TOP

本帖最後由 allenbrian 於 2015-6-30 10:33 編輯

謝謝版主回覆,

問題一還是不了解他的執行跟輸出的順序間的關係,
煩請再說明詳細一點,感謝!

問題二它將輸出直接寫在方法裏了,就變成先遇到先輸出了。
可以說明一下它遇到的過程嗎? 感謝!

TOP

建議你動手在紙上一個步驟一個步驟畫畫看,或者是開Debugger來逐步查看各變數狀況,這會是最清楚的。

TOP

回復 4# codedata

我實際有用紙筆算過了,只是不了解程式執行的步驟,
謝謝版大提醒要用debug,第一次用debug,超強大的!
終於了解程式怎麼執行的了,謝謝版大!

TOP