[問題] 新手提問有關河內塔的遞迴理解

看板java作者ciakkk040156 (險峻的海峽)時間8年前 (2016/10/14 20:49)推噓7(7推 0噓 14→)

留言21則, 7人參與討論串1/1

各位前輩好,這是我在ppt第一次發文,因在河內塔題目有所誤解, 只好硬著頭皮請教各位前輩... 可悲的是我已經google過一些文章後答案竟然也看不懂, 懇請大大們賜教: import java.io.*; public class Hanoi { public static void main(String args[]) throws IOException { int n; BufferedReader buf; buf = new BufferedReader(new InputStreamReader(System.in)); System.out.print("請輸入盤數："); n = Integer.parseInt(buf.readLine()); Hanoi hanoi = new Hanoi(); hanoi.move(n, 'A', 'B', 'C'); } public void move(int n, char a, char b, char c) { if(n == 1) System.out.println("盤" + n + "由" + a + "移至" + c); else { move(n - 1, a, c, b); System.out.println("盤" + n + "由" + a + "移至" + c); move(n - 1, b, a, c); } } 當輸入n=2時會跑出： (1)盤 1 由 A 移至 B (2)盤 2 由 A 移至 C (3)盤 1 由 B 移至 C 對於以上程式碼我的理解是當n=2 即從else開始 move(2-1,a,c,b) 又等於 (1,a,c,b) 所以此時會印出盤1由A移至B 我的疑問在(2)不理解,為什麼此時不是跑回n=1 if條件句且應該要印出盤1由A移至C呢？這是我在網路上找到的解答： n=2 Step1: move(n - 1, a, c, b); 等於是 move(1, a, c(相當於b), b(相當於c)); System.out.println("盤 " + n + " 由 " + a + " 移至 " + c); 等於 System.out.println("盤 1 由 a 移至 b); Step2: System.out.println("盤 " + n + "由 " + a + " 移至 " + c) 等於 System.out.println("盤 2 由 a 移至 c) Step3: move(n - 1, b, a, c); 等於是 move(1, b(相當於a), a(相當於b), c); System.out.println("盤 " + n + " 由 " + a + " 移至 " + c); 等於 System.out.println("盤 1 由 b 移至 c); 1.究竟Step2是怎麼生成的？（我有嘗試使用eclipse中的debug但失敗了可能是方法有錯）謝謝大家的耐心回應,很不好意思但透過大家的幫忙我已經理解了！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.240.146.213 ※ 文章網址: https://www.ptt.cc/bbs/java/M.1476449346.A.BC1.html

→

nodoors

10/14 21:32, , 1^F

10/14 21:32, 1^F

→

pttworld

10/14 21:39, , 2^F

10/14 21:39, 2^F

謝謝大大,我已經學會如何debug了! 但若n=3時,執行到else後此時值為move(2,a,c,b),接著並非往下執行第二行System.out.print(), 後程式跳回if(n==1),再跳回move(n - 1, a, c, b)此時n=1,a=A,b=B,c=C 這是為什麼呢？ ※ 編輯: ciakkk040156 (123.240.146.213), 10/14/2016 23:43:28

推

maxsho

10/14 23:36, , 3^F

10/14 23:36, 3^F

推

maxsho

10/14 23:40, , 4^F

10/14 23:40, 4^F

推

maxsho

10/14 23:45, , 5^F

10/14 23:45, 5^F