作者isaac410 (愛薩克)
看板C_and_CPP
標題[問題] 河內塔照順序問題
時間Sun Mar 28 23:35:53 2021
各位版友好
小弟最近剛學到遞迴，學到最經典的河內塔問題
照正常思維去想應該沒啥問題
http://i.imgur.com/alglNEd.jpg
這是小弟的想法
http://i.imgur.com/PiVbR0F.jpg
用n=3個去想
但是如果要寫成只能照順序移動(A～B～C～A)
這是小弟一樣用n=3去想
http://i.imgur.com/cLS8JUl.jpg
想是想得出來
但是遇到遞迴裡面就卡住不知道如何下手
能請各位大大指點迷津嗎
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.122.68 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1616945755.A.C65.html
※ 編輯: isaac410 (101.137.122.68 臺灣), 03/28/2021 23:37:21
1F：推 LPH66: 你知道為什麼原版能用遞迴嗎? 03/29 01:13
2F：→ ck574b027: 我在想作為新手入門，為何教學自己就在用ABC做不良示範 03/29 13:48
3F：→ ck574b027: 改成 char start, char store, char goal 不好嗎 03/29 13:49
4F：推 kaneson: 新手不太鍵議用河內塔學遞迴 03/29 14:06
5F：推 MartinJ40: 河內塔學遞迴超好吧 很明顯n+1解含n解的子結構阿 03/29 14:20
6F：推 LPH66: 用河內塔我也覺得沒問題+1, 問題在教的人有沒有把這題目中 03/29 18:13
7F：→ LPH66: 類似於數學歸納法的結構給指出來 03/29 18:13
8F：→ LPH66: 原 PO 看起來就完全沒 get 到這件事 03/29 18:14
9F：→ LPH66: 所以他自己的「想法」裡一丁點遞迴或子問題的影子都沒有 03/29 18:14
10F：→ LPH66: 所以我上來第一句就問原 PO 知不知道為什麼原題能用遞迴 03/29 18:15
所以L大的意思是從數學歸納法找出來嗎～我試試看
※ 編輯: isaac410 (101.137.32.198 臺灣), 03/30/2021 00:19:50
11F：推 LPH66: 是用跟數學歸納法類似的概念, 這正是五樓提的「子結構」 03/30 02:37
12F：→ LPH66: 所要講的意思: 大問題的解題步驟中包含了完整小問題的步驟 03/30 02:37
13F：→ LPH66: 這就跟數學歸納法證大問題時用小問題已成立來推論類似 03/30 02:38
我重新推了我的想法，找出一點規律，但寫code還不是很順
※ 編輯: isaac410 (101.137.32.198 臺灣), 03/30/2021 02:40:29
14F：推 alan23273850: 學遞迴用階乘或費式數列都很棒啊 03/30 10:14
15F：推 tsoahans: 你要把K個盤子(K>1)從A移到C 你必須先把上面K-1個盤子從 03/30 11:00
16F：→ tsoahans: A移到B 再把最底層的盤子從A移到C 最後再把K-1個盤子從B 03/30 11:00
17F：→ tsoahans: 移到C 03/30 11:00
18F：→ tsoahans: 你會注意到"把K-1個盤子從A移到B"這件事情和"把K個盤子 03/30 11:00
19F：→ tsoahans: 從A移到C"做的事情是一樣的 03/30 11:00
20F：→ tsoahans: 差別只有在目的地和數量不同(演算法一樣但輸入參數不同) 03/30 11:01
21F：推 vup4jp6: 從頭到尾都只有兩個盤子在移動 沒有ABC柱子的區分 04/08 10:00
22F：→ vup4jp6: 只有目標位置 跟 暫放 04/08 10:00