[理工] 離散 遞迴 98中正

看板Grad-ProbAsk作者 (Kaneshiro Takeshi)時間8年前 (2017/10/30 10:33), 8年前編輯推噓1(1推 0噓 18→)
留言19則, 2人參與, 8年前最新討論串1/1
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
→
10/30 10:42, 8年前 , 1F
你不能一次移動n-1個盤子
10/30 10:42, 1F
→
10/30 10:43, 8年前 , 2F
一次只能移動一個
10/30 10:43, 2F
請問什麼意思？ 這樣問好了！詳解遞迴Sn-1步從A到B 我遞迴an-1步從A到Mid 再an-1步從Mid到B 這樣子錯在哪？ ※ 編輯: ahahahahah (49.158.105.145), 10/30/2017 10:47:45
→
10/30 10:57, 8年前 , 3F
你只知道移動一個盤子時要怎麼移。
10/30 10:57, 3F
→
10/30 10:57, 8年前 , 4F
你並不知道一次移動n-1個盤子時，裡面的細節要怎麼做。
10/30 10:57, 4F
→
10/30 10:57, 8年前 , 5F
你也不需要知道一次移動n-1盤子的詳細步驟要怎麼做。
10/30 10:57, 5F
→
10/30 10:57, 8年前 , 6F
你只要把移動n個盤子的步驟拆開成移動1個與n-1個。
10/30 10:57, 6F
→
10/30 10:57, 8年前 , 7F
因為n-1個你不知道怎麼搬動，所以只要令n-1=n'。
10/30 10:57, 7F
→
10/30 10:57, 8年前 , 8F
因為你已經知道如何將搬動n個盤子的步驟拆開，所以也可以
10/30 10:57, 8F
→
10/30 10:57, 8年前 , 9F
用同樣的方法對付n'個盤子。
10/30 10:57, 9F
推
10/30 10:58, 8年前 , 10F
你的an是假設n個盤子由A到B且中間經過MID，所以你的an-1
10/30 10:58, 10F
→
10/30 10:59, 8年前 , 11F
是n-1個盤子由A到B且中間經過MID，經過中間的過程本身就
10/30 10:59, 11F
→
10/30 10:59, 8年前 , 12F
包含在裡面了，你這樣子反而會多算3次。
10/30 10:59, 12F
哦哦哦好！感謝樓上兩位的解釋~~~ ※ 編輯: ahahahahah (49.158.105.145), 10/30/2017 11:03:30
→
10/30 11:07, 8年前 , 13F
"我遞迴an-1步從A到Mid 再an-1步從Mid到B
10/30 11:07, 13F
→
10/30 11:07, 8年前 , 14F
這樣子錯在哪？"
10/30 11:07, 14F
→
10/30 11:07, 8年前 , 15F
a_n代表從起點柱子移動n個盤子到終點柱的次數，
10/30 11:07, 15F
→
10/30 11:07, 8年前 , 16F
而且每個盤子移動中途必經過第三柱。
10/30 11:07, 16F
→
10/30 11:07, 8年前 , 17F
你令an-1步從A到Mid，代表n-1個盤子中，每個盤子移動中途
10/30 11:07, 17F
→
10/30 11:07, 8年前 , 18F
必經過第三柱，也就是B柱
10/30 11:07, 18F
→
10/30 11:14, 8年前 , 19F
我Lag了
10/30 11:14, 19F
‣ 更多 ahahahahah 的文章
文章代碼(AID): #1Pze-IrB (Grad-ProbAsk)