Re: [問題] 請教一個Hanoi的問題

[yauhh (喲)]

※ 引述《Eureka7 (ξEureka seveN ξ)》之銘言：
: 先說這是一份作業
: 但我實在思考良久，遇到瓶頸了，不知道該怎麼克服，因此上來求教
: 題目是hanoi tower的小變化題型
: 設有1,2,3 三根柱子
: 目的是把1號柱的盤子全部移動到2號柱上
: 但有別於一般hanoi，稍微限制了盤子移動的路徑

: 1 -> 3  NO
: 3 -> 1  NO

原問題1->2拆解成二個子問題:1->3,3->2.
而第一個子問題是原問題的另一種格式:
        全部由1->3,但不可以有任何一步是1->3或3->1.
如此拆到最後有六種單步動作:
1->2
1->3
2->1
2->3
3->1
3->2
以二個碟子來看:
1. 全部1->2 => 1->3,1->2,3->2; 而1->3必須繞路走:1->2,2->3,1->2,3->2.
   前面的1->3是末端的子問題,所以自己拆解沒關係.
2. 全部1->3 => 1->2,1->3,2->3; 1->3繞路走:1->2,2->3,1->2,3->2,2->1,3->1,
   1->2,2->3. 中間的1->3要再拆子問題,顯然是以整落為單位,先想整落1->2,
   再整落2->3.

套上原本最自由的from-to-by模式:
move(N, 1, 3, 2) -> move(N, 1, 2, 3) and then move(N, 2, 3, 1)
move(N, 1, 2, 3) -> move(N-1, 1, 3, 2), move(1, 1, 2, 3), and then
                    move(N-1, 3, 2, 1)
move(N, 2, 3, 1) -> move(N-1, 2, 1, 3), move(1, 2, 3, 1), and then
                    move(N-1, 1, 3, 2)
move(N, 3, 2, 1) -> move(N-1, 3, 1, 2), move(1, 3, 2, 1), and then
                    move(N-1, 1, 2, 3)
move(N, 3, 1, 2) -> move(N, 3, 2, 1) and then move(N, 2, 1, 3)
move(N, 2, 1, 3) -> move(N-1, 2, 3, 1), move(1, 2, 1, 3), and then
                    move(N-1, 3, 1, 2)


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.160.209.29
→ yauhh:簡單說就是遇到任何1->3的子問題,直接換成1->2和2->3.
→ loveme00835:push , 這個 notation 比較看得懂
推 loveme00835:補推
推 Eureka7:推