haskell : Solving Towers of Hanoi

Question

下面的代码解决了 hanoi 使用预定义函数 moveLOD、swapLOI 和 swapLID 返回 Action 列表的问题。

MoveLOD:将 1 个圆盘从第一个位置移动到三元组第三个位置中的第三个销钉。此外，包含有关运动信息的字符串会堆积在字符串列表中。

type Pin = (Char, Int)        -- Represents a rod, named for a character and the number of disks in it.
type Plate = (Pin, Pin, Pin)  -- Represents the configuration of the three rods.(Origin,Intermediate,Destination
type Log = (Plate, [String])  -- Represents a state formed by the configuration of rods and a list of strings that will record the movements made by the algorithm.


moveLOD :: Log -> Log
moveLOD (((o,n), i ,(d,k)),s) = (((o,n-1), i ,(d,k+1)), (o:" -> " ++ [d]):s)

-- swapLOI: Change the positions of the origin rods and intermediate rods.
swapLOI:: Log->Log
swapLOI ((o,i,d),s) = ((i,o,d),s) 

-- swapoLID : Change the positions of the intermediate rods and destination rods.
swapLID:: Log->Log
swapLID ((o,i,d),s) = ((o,d,i),s)

hanoi :: Log -> Log
hanoi:: Int->Log->[String]
hanoi 1 log = transformaLista(moveLOD log)
hanoi n log = hanoi (n-1) (swapLID log) ++ hanoi 1 log ++ hanoi (n-1) (swapLOI(log))

changeToList::Log->[String]
changeToList(p,s) = s

callHanoi:: Int->[String]
callHanoi n = hanoi n ((('O',n),('I',0),('D',0)),[])

Answer 1

hanoi :: Log -> Log
hanoi ((('o',0),i,d),s) = ((('o',0),('i',0),('d',0)), [])
hanoi ((('o',1),i,d),s) = moveLOD((('o',1),i,d),s)
hanoi ((('o',n),i,d),s)= hanoi(swapLOI(hanoi(swapLOI(swapLID(moveLOD(swapLID((('o',n),i,d),s)))))))

仅定义参数的函数，其中 Plate 的第一个 Pin 中的 Char 为 'o'，当角色是其他东西时，您还需要提供方程。

当接收到的参数与任何有定义方程的模式不匹配时，会出现“非穷举模式”错误。解决这个问题的唯一方法是提供其余模式的方程。

在你修改后的代码中，首先，你对origin pin为空的情况的处理是不正确的，

hanoi (((o,0),i,d),s) = ((('o',0),('i',0),('d',0)),[])

意味着无论何时应用这种情况，无论d和i是什么，结果都是相同的。当从 chamahanoi 调用 hanoi 并使用大于 2 的参数时，有时原点会变空，并且由于调用链中只有 hanoi 和 swapLOI，恒定的结果会冒泡。由于递归调用 hanoi，您会得到 n == 2 的正确结果(n == 1 由第二个方程直接求解)那么两者的原极上都只有一个圆盘。

这种情况应该是

hanoi (((o,0),i,d),s) = (((o,0),i,d),s)

这仍然不会产生正确的结果(错误的移动顺序)，因为一般情况下的递归是错误的。

你

• 将顶部圆盘移动到中间销钉(swapLID . moveLOD . swapLID)；
• 然后将剩余的圆盘移动到目的地(河内)，但这是不允许的，因为最小的圆盘位于中间销上，因此不能放置其他圆盘；
• 最后，使用原点引脚(现在为空)作为中间，将磁盘从中间引脚移动到目的地。

你应该

• 将 n-1 个圆盘从原点移动到中间销，
• 然后将底部(最大)的磁盘移动到目的地，
• 最后，将 n-1 个磁盘从中间位置移动到目标位置。

如果没有额外的参数来跟踪要移动的磁盘数量，我看不出有什么简单的方法可以做到这一点。考虑一个四盘游戏。首先，将顶部的三个圆盘移动到中间销，然后将底部的圆盘移动到目标销。现在的任务是使用原始引脚作为辅助，将三个圆盘从中间引脚移动到目标引脚。

正确的做法是顺序

1. i -> d (([],[1,2,3],[4]) -> ([],[2,3],[1,4 ]))
2. i -> o (([],[2,3],[1,4]) -> ([2],[3],[1,4] ))
3. d -> o (([2],[3],[1,4]) -> ([1,2],[3],[4]) )
4. i -> d (([1,2],[3],[4]) -> ([1,2],[],[3,4] ))
5. o -> i (([1,2],[],[3,4]) -> ([2],[1],[3,4] ))
6. o -> d (([2],[1],[3,4]) -> ([],[1],[2,3,4] ))
7. i -> d (([],[1],[2,3,4]) -> ([],[],[1,2,3, 4]))

在第 2 步之后，原始目标引脚将成为要将磁盘(好吧，一个)移动到 o 的引脚，但在这种情况下不应移动磁盘中最低的一个。如果唯一的信息是每个引脚上有多少个磁盘以及磁盘应从何处移动到何处，如何实现这一点？

如果将 hanoi 类型更改为

hanoi :: Int -> Log -> Log

并调用它

chamahanoi n = hanoi n ((('o',n),('i',0),('d',0)),[])

很容易实现。

如果您不想这样做，或者不允许这样做，您可以跟踪每个引脚上的大小，并且只将磁盘移动到较大的引脚上，或者您可以在适当的位置偷偷地删除和添加磁盘引脚来模拟该限制，但如果没有适当的解释，很难将其与作弊区分开来。