[理工] [離散] 遞迴 河內塔

看板Grad-ProbAsk作者 (想)時間11年前 (2013/07/30 15:06), 編輯推噓3(3推 0噓 19→)
留言22則, 4人參與, 最新討論串1/1
是很久以前黃子嘉上課提到南師某年考的題目，但他沒有解 Ｑ: 每種大小的盤子都有三個，搬動規則同河內塔，想從A搬到C 且要按照123123排序 需要走幾次? 下面是圖示~ ---3 ---2 ---1 -----3 -----2 -----1 ---------3 ---------2 ---------1 __________A _________B __________C ↓ ---3 ---2 ---1 -----3 -----2 -----1 ---------3 ---------2 ---------1 ___________A ___________B __________C 我的想法是每種大小都要搬兩次才可以按照順序 依照普通河內塔的解法分成"上面的"n-1個跟最"下面的"一個 推一推發現 上面的 不可能只搬兩次就到C，但搬四次可以 得到以下遞迴式 T(3n)= 4T(3(n-1)) + 3*2 不知道這樣對不對 望請大家指教<(＿ ＿)> -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.119.146.110
推
07/30 18:19, , 1F
如果3個同大小的本身也須照順序，那就只是n=9的一般河內塔
07/30 18:19, 1F
→
07/30 18:20, , 2F
如果無關，那就是3乘上3格的河內塔
07/30 18:20, 2F
→
07/30 23:55, , 3F
是最後完成的順序要按照123，但中途可以是321、213之類的
07/30 23:55, 3F
推
07/31 00:05, , 4F
那就把每3個看成1整體,移動不改順序需5步,那就是5*3格河內塔
07/31 00:05, 4F
→
07/31 00:16, , 5F
請問怎麼移動不改順序可以是五步呢? 如果要移動3個同大小
07/31 00:16, 5F
→
07/31 00:17, , 6F
的盤子應該要六步@@?
07/31 00:17, 6F
→
07/31 00:18, , 7F
啊!!!! 是五步0.0!!!!! 了解了 謝謝>"<
07/31 00:18, 7F
→
07/31 00:41, , 8F
3格是指ABC共3格嗎? 但將"1整體"移動不一定每次都可以
07/31 00:41, 8F
→
07/31 00:43, , 9F
一次走五步，有時一定要分三步三步走的樣子@@?
07/31 00:43, 9F
→
07/31 00:44, , 10F
我是用六個盤子(三大三小)下去當例子發現不能一次走五步
07/31 00:44, 10F
→
07/31 00:45, , 11F
而且有時分開走反而省步數XD
07/31 00:45, 11F
→
07/31 00:54, , 12F
3x7=21次
07/31 00:54, 12F
→
07/31 08:17, , 13F
恩,要考慮的太多太複雜了,放棄
07/31 08:17, 13F
→
07/31 08:32, , 14F
樓上xdddd
07/31 08:32, 14F
→
07/31 08:33, , 15F
是說我好想知道我那樣設有什麼bug
07/31 08:33, 15F
推
08/01 08:06, , 16F
以下我的A(n)就是你的T(3n)
08/01 08:06, 16F
→
08/01 08:07, , 17F
首先A(1)=5用暴力法可得 順序是A>B A>B A>C B>C B>C
08/01 08:07, 17F
→
08/01 08:08, , 18F
再來是降階 降階的概念是若我們會A(n-1)要怎麼做A(n)
08/01 08:08, 18F
→
08/01 08:09, , 19F
那就是把A(n-1)當一個 也就是最底下三個一樣大的 上面放
08/01 08:09, 19F
→
08/01 08:09, , 20F
一個小的 然後去想最佳解法 順序應該是A>C A>B A>B C>B
08/01 08:09, 20F
→
08/01 08:10, , 21F
A>C B>A B>C B>C A>C 所以A(n)=4A(n-1)+5
08/01 08:10, 21F
→
08/01 09:03, , 22F
wow 受教了!!
08/01 09:03, 22F
‣ 更多 otomoyox 的文章
文章代碼(AID): #1HzsNjfp (Grad-ProbAsk)