[理工] 離散 遞迴 98中正

[ahahahahah (Kaneshiro Takeshi)]

16題b小題：
https://i.imgur.com/xsNR6Q2.jpg

這題河內塔的問題
改成A Mid B三根柱子，但是A無法直接到B
一定要經過Mid，問遞迴需要幾步？
解答拆成5個步驟，如下：
https://i.imgur.com/HBTrh27.jpg

我則是把它拆成8個步驟
我的想法是因為題目說一定要從Mid才能到A或B
https://i.imgur.com/saFuUDZ.jpg

請問我這個遞迴想法錯在哪了？


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.105.145
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1509330834.A.D4B.html
※ 編輯: ahahahahah (49.158.105.145), 10/30/2017 10:34:59
→ JKLee: 你不能一次移動n-1個盤子
→ JKLee: 一次只能移動一個
請問什麼意思？
這樣問好了！詳解遞迴Sn-1步從A到B
我遞迴an-1步從A到Mid 再an-1步從Mid到B
這樣子錯在哪？
※ 編輯: ahahahahah (49.158.105.145), 10/30/2017 10:47:45
→ JKLee: 你只知道移動一個盤子時要怎麼移。
→ JKLee: 你並不知道一次移動n-1個盤子時，裡面的細節要怎麼做。
→ JKLee: 你也不需要知道一次移動n-1盤子的詳細步驟要怎麼做。
→ JKLee: 你只要把移動n個盤子的步驟拆開成移動1個與n-1個。
→ JKLee: 因為n-1個你不知道怎麼搬動，所以只要令n-1=n'。
→ JKLee: 因為你已經知道如何將搬動n個盤子的步驟拆開，所以也可以
→ JKLee: 用同樣的方法對付n'個盤子。
推 awilliea: 你的an是假設n個盤子由A到B且中間經過MID，所以你的an-1
→ awilliea: 是n-1個盤子由A到B且中間經過MID，經過中間的過程本身就
→ awilliea: 包含在裡面了，你這樣子反而會多算3次。
哦哦哦好！感謝樓上兩位的解釋~~~
※ 編輯: ahahahahah (49.158.105.145), 10/30/2017 11:03:30
→ JKLee: "我遞迴an-1步從A到Mid 再an-1步從Mid到B
→ JKLee: 這樣子錯在哪？"
→ JKLee: a_n代表從起點柱子移動n個盤子到終點柱的次數，
→ JKLee: 而且每個盤子移動中途必經過第三柱。
→ JKLee: 你令an-1步從A到Mid，代表n-1個盤子中，每個盤子移動中途
→ JKLee: 必經過第三柱，也就是B柱
→ JKLee: 我Lag了