[問題] 河內塔照順序問題

[isaac410 (愛薩克)]

各位版友好

小弟最近剛學到遞迴，學到最經典的河內塔問題

照正常思維去想應該沒啥問題

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://www.ptt.cc/bbs/C_and_CPP/M.1616945755.A.C65.html
※ 編輯: isaac410 (101.137.122.68 臺灣), 03/28/2021 23:37:21
推 LPH66: 你知道為什麼原版能用遞迴嗎?
→ ck574b027: 我在想作為新手入門，為何教學自己就在用ABC做不良示範
→ ck574b027: 改成 char start, char store, char goal 不好嗎
推 kaneson: 新手不太鍵議用河內塔學遞迴
推 MartinJ40: 河內塔學遞迴超好吧 很明顯n+1解含n解的子結構阿
推 LPH66: 用河內塔我也覺得沒問題+1, 問題在教的人有沒有把這題目中
→ LPH66: 類似於數學歸納法的結構給指出來
→ LPH66: 原 PO 看起來就完全沒 get 到這件事
→ LPH66: 所以他自己的「想法」裡一丁點遞迴或子問題的影子都沒有
→ LPH66: 所以我上來第一句就問原 PO 知不知道為什麼原題能用遞迴
所以L大的意思是從數學歸納法找出來嗎～我試試看
※ 編輯: isaac410 (101.137.32.198 臺灣), 03/30/2021 00:19:50
推 LPH66: 是用跟數學歸納法類似的概念, 這正是五樓提的「子結構」
→ LPH66: 所要講的意思: 大問題的解題步驟中包含了完整小問題的步驟
→ LPH66: 這就跟數學歸納法證大問題時用小問題已成立來推論類似
我重新推了我的想法，找出一點規律，但寫code還不是很順
※ 編輯: isaac410 (101.137.32.198 臺灣), 03/30/2021 02:40:29
推 alan23273850: 學遞迴用階乘或費式數列都很棒啊
推 tsoahans: 你要把K個盤子(K>1)從A移到C 你必須先把上面K-1個盤子從
→ tsoahans: A移到B 再把最底層的盤子從A移到C 最後再把K-1個盤子從B
→ tsoahans: 移到C
→ tsoahans: 你會注意到"把K-1個盤子從A移到B"這件事情和"把K個盤子
→ tsoahans: 從A移到C"做的事情是一樣的
→ tsoahans: 差別只有在目的地和數量不同(演算法一樣但輸入參數不同)
推 vup4jp6: 從頭到尾都只有兩個盤子在移動 沒有ABC柱子的區分
→ vup4jp6: 只有目標位置  跟  暫放