Re: [問題] 請教一個Hanoi的問題
※ 引述《Eureka7 (ξEureka seveN ξ)》之銘言：
: 先說這是一份作業
: 但我實在思考良久，遇到瓶頸了，不知道該怎麼克服，因此上來求教
: 題目是hanoi tower的小變化題型
: 設有1,2,3 三根柱子
: 目的是把1號柱的盤子全部移動到2號柱上
: 但有別於一般hanoi，稍微限制了盤子移動的路徑
: 限制如下:
: 1 -> 2 OK
: 2 -> 3 OK
: 3 -> 2 OK
: 2 -> 1 OK
: 但是
: 1 -> 3 NO
: 3 -> 1 NO
這個題目和河內塔有幾項不同：
a) 要將 1 號柱子上的盤子，移到 2 號 (而非 3 號)
b) 無法直接在 1 <-> 3 之間移動，只能採行 1 <-> 2 <-> 3 的模式
如果是要搬到 3 號柱子的話，這題顯然無解，
移動最大那塊盤子會需要做 1 -> 3 的運算，然而小盤子們都在 2 上
如果直接比照河內塔的解法，僅將所有 1 <-> 3 的運算都以
1 <-> 2 <-> 3 取代，又不能排除會出現上述的跳出（違規）運算
所以這題最後還是要回到「紙筆證明」
-------
符號定義：
- R1, R2, R3 表第 1, 2, 3 根柱子，圓盤原本都在 R1 上，目標是 R2
- D1, D2, D3 表第 1, 2, 3 塊盤子，其中數字越大就越大片
- SN 表示包含 D1, D2, ... ,DN 盤子的堆疊
- S(a, b) 表示包含 Da, Da+1, ..., Db 之堆疊
- R1: SN-1, DN 表示 R1 上有 SN-2, 其下壓著 DN (也就是 D1, D2, ... DN-2, DN)
運算定義：
- MN (M 表示 Medial 內側， MN 代表 1->2, 3->2 兩種運算)
由 R1: SN，轉換成 R2: SN 的搬移過程。
- LN (L 表示 lateran 外側，LN 代表 2->1, 2->3 兩種運算)
由 R2: SN 轉換成 R1:SN (或 R3: SN) 的搬移過程
- 上述兩種運算中，R1, R2, R3 可能都還有比 DN 更大的盤子，
但因不會在運算過程中移動，因此不干涉 MN/LN，而忽略不記
因此原命題轉化為：對所有自然數 N，證明 MN 運算之可行性
-------
證明過程：
1. 手算可知 M1, N1 均可行
2. 依序執行下列步驟，可為 Mk 之等效運算
a. Mk-1
b. Lk-1 (移到另一邊)
c. 將 Dk 移到中間
d. Mk-1 (移回中間)
3. 依序執行下列步驟，可為 Lk 之等效運算
a. Lk-1 (移到另一邊)
b. 將 Dk 移到旁邊 (目標位置)
c. Mk-1
d. Lk-1 (Dk 上面)
4. 由 2, 3 可知，若 Lk-1, Mk-1 均可行，則 Lk, Mk 亦可行
5. 由 1, 4, 及數學歸納法可知，對任意自然數 N, LN, MN 均可行，即原命題成立
-------
至於詳細怎麼搬，就自己照上面的演算法去展開吧 XD
把 L/M 寫成函數就解決囉，只是要判斷 Dk, Dk-1 在哪根柱子上，或該移到哪根柱子
--
鬼壓床怎麼辦
騎上去啊
Blog: http://clifflu.blogspot.com/ Since March, 2007
Photo Galelry: http://www.picasaweb.com/clifflu 沒有了 T_T
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.230.190
推
08/06 22:16, , 1F
08/06 22:16, 1F
推
08/06 22:16, , 2F
08/06 22:16, 2F
推
08/06 22:28, , 3F
08/06 22:28, 3F
推
08/06 22:36, , 4F
08/06 22:36, 4F
→
08/06 22:37, , 5F
08/06 22:37, 5F
推
08/08 00:52, , 6F
08/08 00:52, 6F
討論串 (同標題文章)