Re: [問題] 河內塔的問題!!
其實遞迴的程式設計想法應該要先找出一個可歸納的規則,
然後你就可以根據你所想的規則,"直接"轉成程式碼
如果你知道把n-1盤子移到中間的柱子,再把底部那個移到右邊,
最後移動這n-1個盤子,這種策略是可行的
(你可以自己用紙畫畫看,先從n=2, 3 開始,如果看不出來,在試下一個)
你馬上就能將它轉成程式碼:
int Hanoi(char left, char middle, char right, int n)
{
/* 只有一個盤子 */
if(n == 1){
printf("%c => %c", left, right); /* 最簡單的case, 直接從左移到右 */
}
/* 盤子數 >= 2 */
else{
Hanoi(left,right,middle,n-1); /* 將n-1個盤子移到中間 */
printf("%c => %c", left, right); /* 將最大的盤子移到右邊 */
Hanoi(middle, left, right,n-1); /* 將中間n-1個盤子移到右邊 */
}
}
如果在main function 裡寫下: Hanoi('L','M','R', 3);
就會產生:
L => R
L => M Hanoi(left,right,middle,2)
R => M
L => R // printf("%c => %c", left, right);
M => L
M => R Hanoi(middle, left, right,2)
L => R
如我們的預期
而且我們並不需要去 trace 程式碼,我們只要檢驗我們的程式碼的格式
和我們要表達的是否一致,以及邏輯是否正確
( left表左邊的物件,middle表中間,right表右邊
移動: printf("%c => %c", left, right);
最簡單的情況(basis case): 如果只有一個盤子,則從左移到右
(printf("%c => %c", left, right);)
n表示目前操作的盤子數
char xxx => 哪一邊的盤子
中間的盤子只是輔助移動的進行,我們不要它輸出輸出
(雖然我們一直更改, left, middle, right 的內容)
)
這樣程式就會替你做好(一直trace遞迴程式碼,不容易看出它的運作,反而打亂思維)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.181.242
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：
問題
2
13