0

重複の可能性:
Haskell - リストの操作

行列m、開始位置p1、および最終点が与えられp2ます。目的は、最終的な行列 (p2=1 およびその他 =0) に到達する方法がいくつあるかを計算することです。このため、ある位置にスキップするたびに、1 ずつ減少します。ある位置から別の位置にスキップできるのは、最大で水平または垂直の 2 つの位置だけです。例えば：

   m =             p1=(3,1)  p2=(2,3)
   [0 0 0]
   [1 0 4]
   [2 0 4]

ポジションにスキップできます[(3,3),(2,1)]

ある位置からスキップすると、それを 1 つ減らして、すべてやり直します。リストの最初の要素にスキップしましょう。このような：

    m=              
    [0 0 0]
    [1 0 4]
    [1 0 4]

これで位置(3,3)が決まり、位置にスキップできます[(3,1),(2,3)]

そして、最終的な行列までそれを行います:

[0 0 0]
[0 0 0]
[1 0 0]

この場合、最終的な行列を取得するさまざまな方法の量は です20。以下の関数を作成しました。

import Data.List
type Pos = (Int,Int)
type Matrix = [[Int]]

s::Pos->Pos->Matrix->Int
s (i,j) fim mat = if (mat == (matrizFinal (tamanho mat) fim)) then 1 
                else if (possiveisMov (i,j) mat)/= [] then s (head(possiveisMov (i,j) mat)) fim (decrementaPosicao (i,j) mat)
                 else 0



matrizFinal:: Pos->Pos->Matrix
matrizFinal (m,n) p = [[if (y,x)==p then 1 else 0 | x<-[1..n]]| y<-[1..m]]

movimentos::Pos->[Pos]
movimentos (i,j)= [(i+1,j),(i+2,j),(i-1,j),(i-2,j),(i,j+1),(i,j+2),(i,j-1),(i,j-2)]

decrementaPosicao:: Pos->Matrix->Matrix
decrementaPosicao (1,c) (m:ms) = (decrementa c m):ms
decrementaPosicao (l,c) (m:ms) = m:(decrementaPosicao (l-1,c) ms)

decrementa:: Int->[Int]->[Int]
decrementa 1 (m:ms) = (m-1):ms
decrementa n (m:ms) = m:(decrementa (n-1) ms)

tamanho:: Matrix->Pos
tamanho m = (length m,length.head $ m)

possiveisMov:: Pos->Matrix->[Pos]
possiveisMov p mat = verifica0 ([(a,b)|a<-(dim m),b<-(dim n)]  `intersect` xs) mat
                          where xs = movimentos p
                            (m,n) = tamanho mat
dim:: Int->[Int]
dim 1 = [1]
dim n = n:dim (n-1)

verifica0::[Pos]->Matrix->[Pos]
verifica0 [] m =[]
verifica0 (p:ps) m = if ((pegaAltura m p) == 0) then verifica0 ps m
                                               else p:verifica0 ps m

pegaAltura:: Matrix->Pos->Int
pegaAltura x (i,j)= (x!!(i-1))!!(j-1)

s関数がこの問題を解決する方法の数を数えない理由を誰かが知っていますか? どうすればそれを修正できますか、またはs解決する関数を作成するためのより良い方法は?

4

1 に答える 1

0

プレイされているゲームが複数のトークン ビー玉であることに気付いた後、開始から終了までのパスの数をカウントするには、ゲーム ツリーを展開することによって行われ、見つかったボードが終了ボードである場合、それを他のパスとしてカウントすることを知りました。賢明ではありません。

それで、あなたの関数は、すべての可能な動きではなく、最初の可能な動きsでボードを拡張するだけであることがわかりました。正しいバージョンは、ボードが終了状態にあるかどうかをテストして 1 を返します。それ以外の場合は、すべての可能な移動に対するループの結果を合計し、その移動が有効でない場合は 0 になります。

于 2012-10-16T03:18:17.490 に答える