5

我正在尝试编写一个递归函数，它将一个包含整数列表的列表作为输入并返回一个类型为 ([Int],Int) 的元组。（[整数]，整数）

这是为您提供棋盘的“棋盘游戏”：

 [[5,4,3,8,6],
  [0,2,1,0,7],
  [0,1,9,4,3],
  [2,3,4,0,9]]

这将是一个有 4 行 5 列的板。列表中的数字是“硬币值”。这个棋盘游戏的目标是从列表的顶部到底部收集硬币。您可以从顶行的任何位置开始向下移动，您可以直接向下，或斜向左或向右。你会想要一条能给你最大总硬币值的路径。

我创建了第一个函数，您可以在其中输入路径列表 [([Int],Int)] 并返回具有最大硬币值的路径 ([Int],Int)。

现在我需要创建一个函数来实际生成我将输入到第一个函数中的路径列表。

我知道我将不得不使用递归。我将输入棋盘（如上图）和起始栏。我将不得不获取列号，然后创建所有可能路径的列表。如果我从列号开始，我下一个可能的步骤是位置（在下一行）- 相同的列号，列 num -1 和列 num +1。我需要递归调用它，直到我到达底部。

我如何能够存储这些路径步骤，然后存储所有可能路径的最终列表？

([Int],Int) - [Int] 是列表/列号或行中的位置，Int 是硬币值。

我是 haskell 的新手，虽然我明白我必须做什么，但编写代码真的很困难。

4

3 回答 3

1

您不会在惯用的功能代码中的某些变量中“存储”中间值。相反，您将它们保留为累积参数，您可以使用诸如 foldr 之类的函数传递该参数。

http://hackage.haskell.org/packages/archive/base/latest/doc/html/Prelude.html#v:foldr

于 2013-02-05T01:17:07.937 回答
0

我想我现在可以（轻松地）将我对另一个问题的回答调整为这个问题。我列出了允许的索引组合并将板映射到它们。（pat 的评论帮助我改进 index_combinations）

*Main> :load "new1.hs"
[1 of 1] 编译 Main（new1.hs，解释）
好的，加载的模块：Main。
*Main> 结果
([8,7,4,9],28)
*Main> 路径
[3,4,3,4]

import Data.List
import Data.Ord
import Data.Maybe

r = [[5,4,3,8,6],
     [0,2,1,0,7],
     [0,1,9,4,3],
     [2,3,4,0,9]]

r1 = r !! 0
r2 = r !! 1
r3 = r !! 2
r4 = r !! 3

index_combinations = 
  [[a,b,c,d] | a <- [0..4], b <- [max 0 (a-1)..min 4 (a+1)], 
   c <- [max 0 (b-1)..min 4 (b+1)], d <- [max 0 (c-1)..min 4 (c+1)]]  

mapR xs = [r1 !! (xs !! 0), r2 !! (xs !! 1), 
           r3 !! (xs !! 2), r4 !! (xs !! 3)]

r_combinations = map mapR index_combinations
r_combinations_summed = zip r_combinations $ map (foldr (+) 0) r_combinations

result = maximumBy (comparing snd) r_combinations_summed
path = index_combinations !! fromJust (elemIndex result r_combinations_summed)
于 2013-02-07T03:21:24.243 回答
0

如果您有兴趣在此处使用我的包网格 （用户指南） 作为示例来帮助您入门。（如果您不想使用它，您可能会发现一些源代码很有帮助。）

创建一个 4 行 5 列的网格。

λ> :m + Math.Geometry.Grid
λ> let g = rectSquareGrid 4 5
λ> indices g
[(0,0),(0,1),(0,2),(0,3),(1,0),(1,1),(1,2),(1,3),(2,0),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(3,3),(4,0),(4,1),(4,2),(4,3)]

我们希望能够将“硬币值”映射到网格位置，因此我们将创建一个 GridMap。

λ> :m + Math.Geometry.GridMap
λ> let m = lazyGridMap g [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9]
λ> m
lazyGridMap (rectSquareGrid 4 5) [5,4,3,8,6,0,2,1,0,7,0,1,9,4,3,2,3,4,0,9]
λ> toList m
[((0,0),5),((0,1),4),((0,2),3),((0,3),8),((1,0),6),((1,1),0),((1,2),2),((1,3),1),((2,0),0),((2,1),7),((2,2),0),((2,3),1),((3,0),9),((3,1),4),((3,2),3),((3,3),2),((4,0),3),((4,1),4),((4,2),0),((4,3),9)]

我们可以找出网格中任何单元格的邻居，但是对于您的应用程序，我们遇到了一点问题：我的 RectSquareGrid 类型不允许对角线移动。

λ> neighbours (1,2) m
[(0,2),(1,3),(2,2),(1,1)]

现在，我很乐意创建一种Grid可以满足您需求的新型。或者，您可以编写自己的函数，其中包括对角线邻居：

λ> let neighbours2 (x, y) g = filter (`inGrid` g) [(x-1,y-1), (x-1,y), (x-1,y+1), (x,y-1), (x,y+1), (x+1,y-1), (x+1,y), (x+1,y+1)]
λ> neighbours2 (1,2) m
[(0,1),(0,2),(0,3),(1,1),(1,3),(2,1),(2,2),(2,3)]

但是您只对允许向下移动感兴趣，无论是直线向下还是对角线，所以这里有一个更有用的函数：

λ> let allowedMoves (x, y) g = filter (`inGrid` g) [(x+1,y-1), (x+1,y), (x+1,y+1)]
λ> allowedMoves (1,2) m
[(2,1),(2,2),(2,3)]

所以现在我们可以编写一个函数，为您提供从给定索引到网格底行的所有可能路径。

allPathsFrom a g | fst a == fst (size g) = [[a]]
                 | otherwise             = Prelude.map (a:) xs
  where xs = concatMap (\x -> allPathsFrom x g) ys
        ys = allowedMoves a g

例如：

λ> allPathsFrom (0,1) m
[[(0,1),(1,0),(2,0),(3,0),(4,0)],[(0,1),(1,0),(2,0),(3,0),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,0)],[(0,1),(1,0),(2,0),(3,1),(4,1)],[(0,1),(1,0),(2,0),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,0),(4,0)],[(0,1),(1,0),(2,1),(3,0),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,0)],[(0,1),(1,0),(2,1),(3,1),(4,1)],[(0,1),(1,0),(2,1),(3,1),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,1)],[(0,1),(1,0),(2,1),(3,2),(4,2)],[(0,1),(1,0),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,0),(3,0),(4,0)],[(0,1),(1,1),(2,0),(3,0),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,0)],[(0,1),(1,1),(2,0),(3,1),(4,1)],[(0,1),(1,1),(2,0),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,0),(4,0)],[(0,1),(1,1),(2,1),(3,0),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,0)],[(0,1),(1,1),(2,1),(3,1),(4,1)],[(0,1),(1,1),(2,1),(3,1),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,1)],[(0,1),(1,1),(2,1),(3,2),(4,2)],[(0,1),(1,1),(2,1),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,1),(4,0)],[(0,1),(1,1),(2,2),(3,1),(4,1)],[(0,1),(1,1),(2,2),(3,1),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,1)],[(0,1),(1,1),(2,2),(3,2),(4,2)],[(0,1),(1,1),(2,2),(3,2),(4,3)],[(0,1),(1,1),(2,2),(3,3),(4,2)],[(0,1),(1,1),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,1),(3,0),(4,0)],[(0,1),(1,2),(2,1),(3,0),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,0)],[(0,1),(1,2),(2,1),(3,1),(4,1)],[(0,1),(1,2),(2,1),(3,1),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,1)],[(0,1),(1,2),(2,1),(3,2),(4,2)],[(0,1),(1,2),(2,1),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,1),(4,0)],[(0,1),(1,2),(2,2),(3,1),(4,1)],[(0,1),(1,2),(2,2),(3,1),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,1)],[(0,1),(1,2),(2,2),(3,2),(4,2)],[(0,1),(1,2),(2,2),(3,2),(4,3)],[(0,1),(1,2),(2,2),(3,3),(4,2)],[(0,1),(1,2),(2,2),(3,3),(4,3)],[(0,1),(1,2),(2,3),(3,2),(4,1)],[(0,1),(1,2),(2,3),(3,2),(4,2)],[(0,1),(1,2),(2,3),(3,2),(4,3)],[(0,1),(1,2),(2,3),(3,3),(4,2)],[(0,1),(1,2),(2,3),(3,3),(4,3)]]

请注意，由于GridMaps 也是s，我们可以在orGrid上调用上述所有函数。mg

λ> allPathsFrom (0,1) m

grid 如果您希望我添加一个允许对角线移动到我的包裹的网格，请告诉我（amy at nualeargais dot ie） 。

于 2013-02-07T10:37:02.893 回答