作者ciakkk040156 (險峻的海峽)
看板java
標題[問題] 新手提問 有關河內塔的遞迴理解
時間Fri Oct 14 20:49:04 2016
各位前輩好,這是我在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://webptt.com/m.aspx?n=bbs/java/M.1476449346.A.BC1.html
1F：→ nodoors: step2是else裡第二行@@ 10/14 21:32
2F：→ pttworld: debug在move method下行斷點，watch到n=2後單步執行。 10/14 21:39
謝謝大大,我已經學會如何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
3F：推 maxsho: 先把if else敘述在做什麼先弄清楚 10/14 23:36
4F：推 maxsho: 當n不是1時，會執行else內的全部敘述 執行move(n-1,a,c,b) 10/14 23:40
5F：推 maxsho: 在執行else中的第二行 System.out.println最後執行 10/14 23:45
6F：→ maxsho: move(n-1,b,c,a) 10/14 23:46
※ 編輯: ciakkk040156 (123.240.146.213), 10/14/2016 23:48:46
7F：推 maxsho: 執行move(2,a,c,b)時因爲n!=1會在先執行一次else的所有敘 10/14 23:53
8F：→ maxsho: 所以才叫遞迴 10/14 23:53
9F：推 maxsho: 我覺得你先把程式是如何呼叫及執行先搞清楚在來提問比較好 10/14 23:55
m大謝謝你的回覆/解答,自己的確是不太清楚程式的呼叫與執行,
導致問問題也不夠精確,我會加油
10F：推 ilms49898723: 同樓上，我不懂你是不懂他遞迴的邏輯，還是你只是單 10/14 23:58
11F：→ ilms49898723: 純看不懂code 10/14 23:58
謝謝回覆,下次提問我會整理好思緒再提問
12F：→ ssccg: 如果你不懂method call stack的話，用debug一行一行跑反而 10/15 01:57
13F：→ ssccg: 會混亂以為都在哪幾行跳吧 10/15 01:57
14F：→ ssccg: 先試著自己把執行順序寫出來，把method inline展開來看 10/15 01:57
15F：→ ssccg: 遞迴可能不是很重要，但是一個method call是怎麼回事很重要 10/15 02:00
謝s大回覆,看debug然後專心逐行寫出寫執行順序出來讓我想通了。
我的問題在於誤解值傳遞的方式以及程式執行的步驟,茅塞頓開的感覺真好！
16F：→ pttworld: step into進入，step out跳出，step over躍往下一步。 10/15 02:47
17F：→ pttworld: 這三個基本的反覆單步執行理解遞迴原理。 10/15 02:48
感謝p大再度回應,透過你的解釋我有嘗試用此方法跑簡單的遞迴去理解
18F：推 gmoz: 1進入 2進入 3進入 滿足中斷 3跑完返回 2跑完返回 1跑完返回 10/15 10:25
19F：→ gmoz: 先拿簡單的例子弄清楚遞回的運作方式 10/15 10:25
謝謝回應,我會去試試看！
20F：→ adrianshum: 很久以前我在c_cpp 版有回答過河內塔的問題，看看能 10/15 16:55
21F：→ adrianshum: 不能理解？ 10/15 16:55
謝謝a大,我有去拜讀文章,很清楚的說明！
※ 編輯: ciakkk040156 (123.240.146.213), 10/15/2016 21:20:38