[理工] 離散遞迴 河內塔

看板Grad-ProbAsk作者 (ponny)時間9年前 (2016/12/08 13:40), 編輯推噓9(9推 0噓 12→)
留言21則, 4人參與, 最新討論串1/1
http://i.imgur.com/E02fEa3.jpg
這題我算出來 沒有答案符合 求大大解 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.194.203 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1481175614.A.F1F.html
推
12/08 14:22, , 1F
我沒很仔細看你的題目 不過河內塔a1=1不是嗎？
12/08 14:22, 1F
推
12/08 14:24, , 2F
一般河內塔遞迴關係式應該是a(n)=2*a(n-1)+1
12/08 14:24, 2F
推
12/08 14:29, , 3F
這題有一個限制是說disk一次移動只能移到隔壁的peg
12/08 14:29, 3F
→
12/08 14:29, , 4F
然後題目最後問的是移到another 所以我剛剛想了想是不是
12/08 14:29, 4F
→
12/08 14:29, , 5F
假設最初的disk都在中間的peg
12/08 14:29, 5F
→
12/08 14:31, , 6F
這樣一來我要移到左邊或右邊並且一次只能移動到隔壁peg
12/08 14:31, 6F
→
12/08 14:31, , 7F
的方法數
12/08 14:31, 7F
→
12/08 14:32, , 8F
我剛剛拿硬幣試了一下 3個的從中間移到左邊是13步XDDD
12/08 14:32, 8F
→
12/08 14:32, , 9F
答案我猜是BE
12/08 14:32, 9F
推
12/08 14:33, , 10F
真是抱歉 我沒仔細看題目
12/08 14:33, 10F
推
12/08 14:33, , 11F
不然題目應該是要改成 從A移動到B中間必須經過MID 才會
12/08 14:33, 11F
→
12/08 14:33, , 12F
符合你原本列的遞迴關係式
12/08 14:33, 12F
推
12/08 14:36, , 13F
剛剛又試了一下 應該說起始位置是哪都無所謂 他的重點是
12/08 14:36, 13F
→
12/08 14:36, , 14F
只要移動到另外兩根其中一根就好
12/08 14:36, 14F
→
12/08 14:36, , 15F
所以步驟數為1/2(3^n-1)
12/08 14:36, 15F
推
12/08 14:42, , 16F
如果起始在最左 移到中間peg是1/2(3^n-1) 移到右邊peg是(
12/08 14:42, 16F
→
12/08 14:42, , 17F
3^n-1)
12/08 14:42, 17F
推
12/08 14:43, , 18F
覺得是an=3(an-1)+1 一開始在哪都沒差
12/08 14:43, 18F
推
12/08 15:16, , 19F
所以這樣答案會分成 移到隔兩格的地方跟移到隔壁那格不同答
12/08 15:16, 19F
→
12/08 15:16, , 20F
案
12/08 15:16, 20F
→
12/08 15:18, , 21F
但可能題目只是要移到隨意一個就行 所以答案就BE
12/08 15:18, 21F
‣ 更多 boy00114 的文章
文章代碼(AID): #1OIF8-yV (Grad-ProbAsk)