5

整数のリストを含むリストを入力として受け取り、([Int],Int) 型のタプルを返す再帰関数を作成しようとしています。([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) を最大のコイン値で返します。

ここで、最初の関数に入力するパスのリストを実際に生成する関数を作成する必要があります。

再帰を使用する必要があることはわかっています。ボード (上記のようなもの) と開始列を入力します。列番号を取得して、可能なすべてのパスのリストを作成する必要があります。列番号から始めた場合、次に考えられるステップは (次の行の) 位置です。同じ列番号、列番号 -1、列番号 +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

私のパッケージグリッド (ユーザー ガイド) をここで例として使用して開始することに興味がある場合。(また、使用したくない場合は、ソース コードの一部が役立つ場合があります。)

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 もGrids であるため、上記のすべての関数をmまたはで呼び出すことができることに注意してくださいg。

λ> allPathsFrom (0,1) m

パッケージに斜めの動きを可能にするグリッドを追加してほしい場合は、私に知らせてください (nualeargais dot ie の amy) grid 。

于 2013-02-07T10:37:02.893 に答える
0

私は今、別の質問に対する私の答えをこの質問に（簡単に）適応させる立場にあると思います。許可されているインデックスの組み合わせをリストし、ボードをそれらにマップしました。(パットのコメントは index_combinations の改善に役立ちました)

*Main> :load "new1.hs"
[1 of 1] Main をコンパイル中 ( new1.hs、解釈済み )
OK、ロードされたモジュール: Main。
*メイン> 結果
([8,7,4,9],28)
*メイン> パス
[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 に答える