HASKELL:解决河内的塔 [英] HASKELL : Solving Towers of Hanoi

问题描述

下面的代码使用预定义的函数moveLOD，swapLOI和swapLID解决了河内返回的移动列表的问题.

The code below solves hanoi returning a list of moves using predefined functions moveLOD,swapLOI and swapLID.

MoveLOD:将一张光盘从三联体的第三个位置的第一个位置移动到第三个销钉.另外，将包含有关运动信息的字符串堆积在字符串列表上.

MoveLOD: moves 1 disc from the first position to third the pin in the third position of the triplet. Additionally a string with information about the movement is piling on list of strings.

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)),[])

推荐答案

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'的自变量定义函数，还需要提供有关字符是否为其他字符的方程式.

only defines the function for arguments where the Char in the first Pin of the Plate is 'o', you also need to provide equations for when the character is something else.

当接收到不匹配存在定义方程式的任何模式的自变量时，会出现非穷举模式"错误.解决此问题的唯一方法是为其余模式提供方程式.

When an argument not matching any of the patterns for which there is a defining equation is received, a "Non-exhaustive pattern" error is raised. The only way to fix it is to provide equations for the remaining patterns.

在修改后的代码中，首先，您对原点引脚为空的情况的处理不正确，

In your revised code, first, your treatment of the case where the origin pin is empty is incorrect,

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

表示无论什么情况，无论d和i是什么，结果都是相同的.当从chamahanoi调用hanoi且其参数大于2时，原始极点变为空，并且由于在调用链中只有hanoi和swapLOI高于该极点，因此该常数结果会冒泡.您可以得到n == 2的正确结果(n == 1由第二个方程式直接求解)，因为对hanoi的递归调用然后都在原始极点上只有一个磁盘.

means that whenever this case applies the result is the same, regardless of what d and i are. When hanoi is called from chamahanoi with an argument greater than 2, at some time the origin pole becomes empty, and since above that in the call chain are only hanoi and swapLOI, that constant result bubbles up. You get the correct result for n == 2 (n == 1 is directly solved by the second equation) since the recursive calls to hanoi then both have only one disk on the origin pole.

这种情况应该是

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

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

That still doesn't produce correct results (wrong sequence of moves), since the recursion in the general case is wrong.

您

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

• move the top disk to the intermediate pin (swapLID . moveLOD . swapLID);
• then move the remaining disks to the destination (hanoi), but that isn't allowed since the smallest disk is on the intermediate pin and so no other disk may be placed there;
• finally, move the disk(s) from the intermediate pin to the destination using the (now empty) origin pin as intermediate.

您应该

• 将n-1磁盘从原点移动到中间引脚，
• 然后将底部(最大)磁盘移至目标位置，
• 最后，将n-1磁盘从中间磁盘移动到目标磁盘.

• move n-1 disks from the origin to the intermediate pin,
• then move the bottom (largest) disk to the destination,
• finally, move the n-1 disks from the intermediate to the destination.

如果没有额外的参数来跟踪要移动的磁盘数量，我看不到一种简单的方法.考虑一个四盘游戏.首先，将顶部的三个磁盘移至中间引脚，然后将底部的磁盘移至目标引脚.现在的任务是将三个磁盘从中间引脚移到目标引脚，并使用原始引脚作为助手.

I don't see an easy way to do that without an extra argument keeping track of how many disks to move. Consider a four-disk game. First, the top three disks are moved to the intermediate pin, then the bottom disk is moved to the destination pin. Now the task is to move the three disks from the intermediate pin to the destination pin, using the origin pin as helper.

正确的方法是顺序

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]))

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的引脚，但是在这种情况下，最低的那些引脚不得移动.如果唯一的信息是每个引脚上有多少个磁盘，以及磁盘应从何处移动到何处，该怎么办?

After step 2, the original destination pin becomes the pin from which disks (well, one) are to be moved to o, but the lowest of those shall not be moved in this situation. How could that be achieved if the only information is how many disks are on each pin, and from where to where disks shall be moved?

如果将hanoi的类型更改为

hanoi :: Int -> Log -> Log

并调用它

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

易于实现.

如果您不想这样做或不允许这样做，则可以跟踪每个引脚上的大小，然后仅将磁盘移动到更大的磁盘上，或者可以在适当的位置偷偷地删除和添加磁盘引脚来模仿这种限制，但是如果没有适当的解释，很难将其与作弊区别开来.

If you don't want to do that, or are not allowed to, you could either keep track of the sizes on each pin, and only move disks onto larger ones, or you could sneakily remove and add disks at the appropriate pins to emulate that restriction, but that would be hard to distinguish from cheating without proper explanation.

这篇关于HASKELL:解决河内的塔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！