我正在嘗試用禁止的動作解決河內難題。我有 3 個桿，一個左桿，一個中桿和一個右桿。在左邊的桿子上，我有 2 個盤子（最小的在頂部，最大的在底部），想把它們放到右邊的桿子上。您一次只能移動一個盤子。但這里有個問題：你不能把一個更大的盤子放在一個小的盤子上，然后把一個盤子從左邊的桿子移到中間的桿子上，然后從中間的桿子移到右邊的桿子上。
我有以下演算法：
type HanoiMovement = (Integer , Char , Char)
hanoi :: Integer -> [HanoiMovement]
hanoi n = hanoi_gen 'l' 'r' 'm' n
where
hanoi_gen s z aux 0 = []
hanoi_gen s z aux n = hanoi_gen s aux z (n-1) [(n,s,z)] hanoi_gen aux z s (n-1)
它確實生成了關于如何移動板的解決方案，但它忽略了禁止移動 [('l','m'), ('m','r')]。如何將它們實作到演算法中？
先感謝您
uj5u.com熱心網友回復：
好吧，您當前對“標準”河內拼圖的解決方案利用了這樣一個事實，例如，使用中間 ( hanoi 'l' 'r' 'm' 3) 從左到右移動 3 個圓盤可以遞回表示為使用右 ( ) 從左到中間移動 2 個圓盤hanoi 'l' 'm' 'r' 2，然后'3'從左向右移動光碟，然后使用左 ( ) 從中間向右移動 2 個光碟hanoi 'm' 'r' 'l' 2。
為了實作修改后的 Hanoi 謎題，您需要修改遞回以考慮禁止移動。由于禁止移動破壞了極點的對稱性，您將無法定義一個適用于 、 和 的所有值的單個s遞回z步驟aux。
相反，您需要處理每種情況：
data Pole = L | M | R deriving (Show)
要在不使用禁止移動的情況下將n圓盤從移動L到，您應該像往常一樣將圓盤從移動到，然后將圓盤從移動到，然后將圓盤從移動到。換句話說：Rn-1LMnLRn-1MR
hanoi L R M n
= hanoi L M R (n-1) [(n,L,R)] hanoi M R L (n-1)
但是，要在不使用禁止移動的情況下將n光碟從移動L到M，您不能使用相同的模式，因為它會使用禁止移動(n,L,M)，而是需要先將n-1光碟從L移動M，然后將光碟n從移動L到R，這是允許的，然后將n-1圓盤從M移至L，將圓盤n從R后移至M（也允許），最后將n-1圓盤從L移至M。作為代碼：
hanoi L M R n
= hanoi L M R (n-1) [(n,L,R)] hanoi M L R (n-1)
[(n,R,M)] hanoi L M R (n-1)
如果您為極點的所有排列定義類似的模式并使用通常的基本情況。那應該給你你的解決方案。
劇透跟隨....
.
.
.
.
剩下的模式是：
hanoi R L M n
= hanoi R M L (n-1) [(n,R,L)] hanoi M L R (n-1)
hanoi R M L n
= hanoi R L M (n-1) [(n,R,M)] hanoi L M R (n-1)
hanoi M R L n
= hanoi M R L (n-1) [(n,M,L)] hanoi R M L (n-1)
[(n,L,R)] hanoi M R L (n-1)
hanoi M L R n
= hanoi M R L (n-1) [(n,M,L)] hanoi R L M (n-1)
如果需要，可以使用幫助程式對它們進行一些簡化，如下所示，但如果不先詳細寫出它們，就很難看到這種模式：
hanoi :: Pole -> Pole -> Pole -> Int -> [(Int,Pole,Pole)]
hanoi _ _ _ 0 = []
-- handle the "hard" cases with a helper:
hanoi L M R n = hanoi' L M R n
hanoi M R L n = hanoi' M R L n
-- the rest are straightforward
hanoi s z aux n = hanoi s aux z (n-1) [(n,s,z)] hanoi aux z s (n-1)
hanoi' s z aux n
= hanoi s z aux (n-1) [(n,s,aux)] hanoi z s aux (n-1)
[(n,aux,z)] hanoi s z aux (n-1)
完整的可運行示例：
data Pole = L | M | R deriving (Show)
hanoi :: Pole -> Pole -> Pole -> Int -> [(Int,Pole,Pole)]
hanoi _ _ _ 0 = []
-- handle the "hard" cases with a helper:
hanoi L M R n = hanoi' L M R n
hanoi M R L n = hanoi' M R L n
-- the rest are straightforward
hanoi s z aux n = hanoi s aux z (n-1) [(n,s,z)] hanoi aux z s (n-1)
hanoi' s z aux n
= hanoi s z aux (n-1) [(n,s,aux)] hanoi z s aux (n-1)
[(n,aux,z)] hanoi s z aux (n-1)
main = do
print $ hanoi L R M 2
print $ hanoi L R M 3
它為 2 和 3 光碟提供了解決方案：
[(1,L,R),(1,R,M),(2,L,R),(1,M,L),(1,L,R)]
[(1,L,R),(1,R,M),(2,L,R),(1,M,L),(2,R,M),(1,L,R),(1,R,M),(3,L,R),
(1,M,L),(1,L,R),(2,M,L),(1,R,M),(2,L,R),(1,M,L),(1,L,R)]
這些似乎是正確的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532379.html
標籤：算法哈斯克尔河内塔