3

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

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

2 回答 2

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

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

当接收到不匹配任何有定义方程的模式的参数时，会引发“非穷举模式”错误。修复它的唯一方法是为剩余模式提供方程。

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

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

意味着无论何时应用这种情况，结果都是相同的，无论是什么d和i是。当使用大于 2 的参数hanoi调用 from时，在某些时候原点变为空，并且由于调用链中的上面只有和，因此该常量结果会冒泡。你得到正确的结果(直接由第二个方程求解) 因为对then 的递归调用在原点上只有一个磁盘。chamahanoihanoiswapLOIn == 2n == 1hanoi

这种情况应该

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

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

你

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

你应该

  • 将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 步之后，原始目标 pin 成为要从其中移动磁盘（嗯，一个）的 pin o，但在这种情况下不应移动最低的那些。如果唯一的信息是每个引脚上有多少个磁盘，以及磁盘应该从哪里移动到哪里，那如何实现呢？

如果您将类型更改hanoi为

hanoi :: Int -> Log -> Log

并称之为

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

这很容易实现。

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

于 2012-10-06T14:17:35.487 回答
3

如果它对任何人有帮助，这里是另一个河内算法塔：

hanoi 0 _ _ _ = []
hanoi n a b c = hanoi (n-1) a c b ++ [(a,b)] ++ hanoi (n-1) c b a

例如，河内 2 "a" "b" "c" == [("a","c"), ("a","b"), ("c","b")]

于 2014-12-25T05:31:08.427 回答