推 h04mp6286: 我沒很仔細看你的題目 不過河內塔a1=1不是嗎？ 12/08 14:22
推 h04mp6286: 一般河內塔遞迴關係式應該是a(n)=2*a(n-1)+1 12/08 14:24
推 qq70200: 這題有一個限制是說disk一次移動只能移到隔壁的peg 12/08 14:29
→ qq70200: 然後題目最後問的是移到another 所以我剛剛想了想是不是 12/08 14:29
→ qq70200: 假設最初的disk都在中間的peg 12/08 14:29
→ qq70200: 這樣一來我要移到左邊或右邊並且一次只能移動到隔壁peg 12/08 14:31
→ qq70200: 的方法數 12/08 14:31
→ qq70200: 我剛剛拿硬幣試了一下 3個的從中間移到左邊是13步XDDD 12/08 14:32
→ qq70200: 答案我猜是BE 12/08 14:32
推 h04mp6286: 真是抱歉 我沒仔細看題目 12/08 14:33
推 qq70200: 不然題目應該是要改成 從A移動到B中間必須經過MID 才會 12/08 14:33
→ qq70200: 符合你原本列的遞迴關係式 12/08 14:33
推 qq70200: 剛剛又試了一下 應該說起始位置是哪都無所謂 他的重點是 12/08 14:36
→ qq70200: 只要移動到另外兩根其中一根就好 12/08 14:36
→ qq70200: 所以步驟數為1/2(3^n-1) 12/08 14:36
推 qq70200: 如果起始在最左 移到中間peg是1/2(3^n-1) 移到右邊peg是( 12/08 14:42
→ qq70200: 3^n-1) 12/08 14:42
推 opu456: 覺得是an=3(an-1)+1 一開始在哪都沒差 12/08 14:43
推 mloop: 所以這樣答案會分成 移到隔兩格的地方跟移到隔壁那格不同答 12/08 15:16
→ mloop: 案 12/08 15:16
→ mloop: 但可能題目只是要移到隨意一個就行 所以答案就BE 12/08 15:18