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

看板C_and_CPP作者yauhh (喲)時間14年前 (2010/08/06 23:15)推噓2(2推 0噓 2→)

留言4則, 3人參與討論串3/4 (看更多)

※ 引述《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

08/06 23:17, , 1^F

08/06 23:17, 1^F

→

loveme00835

08/06 23:21, , 2^F

08/06 23:21, 2^F

推

loveme00835

08/07 09:10, , 3^F

08/07 09:10, 3^F