4

:: [(Integer, Integer)]の形式のペアを含む無限のリストペアを作成します(m,n)。ここで、mとnのそれぞれはのメンバーです[0 ..]。追加の要件は、(m,n) がリストの正当なメンバーである場合、有限時間(elem (m,n) pairs)で戻る必要があるということです。Trueこの要件に違反するペアの実装は、非解決策と見なされます。

****新鮮な編集コメントありがとうございます、私がいくつかの進歩を遂げることができるかどうか見てみましょう****

    pairs :: [(Integer, Integer)]
    pairs = [(m,n) | t <- [0..], m <- [0..], n <-[0..], m+n == t]

このようなもの？有限時間でTrueがどこに戻るのかわかりません。

質問の言い方は、私の答えの一部である必要はないと思います。あなたが呼ぶだけ(elem (m,n) pairs)でそれはtrueを返すはずです。聞こえますか？

4

4 に答える 4

8

メソッドを無視するhelperと、リスト内包表記ですべてのペアがリストされますが、要素の順序に問題があります。のような無限に多くのペアがあり、その後にのような無限に多くのペアが(0, m)続きます(1, m)。もちろん、到達しないすべてのペアなどelemを永久に繰り返します。(0, m)(1, m)(2, m)

なぜこのメソッドを使用しているのかわかりません。このメソッドを使用すると、でフィルタリングしたため、helperのようにペアのリストを作成するだけです。それは要件の一部でしたか？[(0,0), (1,1), (2,2), ...]m = n

@hammarが提案したように、最初に0 = m + nペア（m、n）をリストします。次に、ペア（m、n）をリストします。ここで1 = m + n。そうすると、リストはのようになります[(0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...]。

于 2013-03-23T06:58:42.013 に答える
1

ヘルパー関数は、ペアがフォームのリストであることを確認し[ (0,0) , (1,1) , (2,2) ... ]ます。

したがって、elem ( m , n )ペアは次のように実装できます。

elem (m , n) _ |  m == n    = True
               |  otherwise = False

これは定数時間の実装です。

于 2013-03-23T06:32:12.653 に答える
1

私が最初に投稿した

Prelude> let pairs = [(m, n) | t <- [0..]
                     , let m = head $ take 1 $ drop t [0..] 
                     , let n = head $ take 1 $ drop (t + 1) [0..]]

それは、教授が設定した3つの条件に答えたと思います。しかし、hammarは、このリストを答えとして選択した場合、つまり（t、t + 1）の形式のペアのリストを選択した場合は、リストを選択した方がよいと指摘しました。

repeat [(0,0)]

[0..]と[0..]のすべての組み合わせをリストに含める必要があるという言及がないように思われることを考えると、これらは両方とも教授の質問に答えているようです。

それはさておき、hammerは、すべての組み合わせをリストする方法を理解するのに役立ち、有限リストから無限リストを作成することで、有限時間でのelemの評価を容易にしました。[0..]と[0..]のすべての組み合わせを構築しているように見える、他の2つの有限リスト（Hammarの対角線の提案よりも簡潔ではありません）を次に示します。

edges = concat [concat [[(m,n),(n,m)] | let m = t, n <- take m [0..]] ++ [(t,t)] 
      | t <- [0..]]


*Main> take 9 edges
[(0,0),(1,0),(0,1),(1,1),(2,0),(0,2),(2,1),(1,2),(2,2)]

エッジ（t、0..t）（0..t、t）を構成し、

oddSpirals size = concat [spiral m size' | m <- n] where
  size' = if size < 3 then 3 else if even size then size - 1 else size
  n = map (\y -> (fst y * size' + div size' 2, snd y * size' + div size' 2)) 
          [(x, t-x) | let size' = 5, t <- [0..], x <- [0..t]]
  spiral seed size = spiral' (size - 1) "-" 1 [seed]
  spiral' limit op count result
    | count == limit =
       let op' = if op == "-" then (-) else (+)
           m = foldl (\a b -> a ++ [(op' (fst $ last a) b, snd $ last a)]) result (replicate count 1)
           nextOp = if op == "-" then "+" else "-"
           nextOp' = if op == "-" then (+) else (-)
           n = foldl (\a b -> a ++ [(fst $ last a, nextOp' (snd $ last a) b)]) m (replicate count 1)
           n' = foldl (\a b -> a ++ [(nextOp' (fst $ last a) b, snd $ last a)]) n (replicate count 1)
       in n'
    | otherwise      =
        let op' = if op == "-" then (-) else (+)
            m = foldl (\a b -> a ++ [(op' (fst $ last a) b, snd $ last a)]) result (replicate count 1)
            nextOp = if op == "-" then "+" else "-"
            nextOp' = if op == "-" then (+) else (-)
            n = foldl (\a b -> a ++ [(fst $ last a, nextOp' (snd $ last a) b)]) m (replicate count 1)
        in spiral' limit nextOp (count + 1) n


*Main> take 9 $ oddSpirals 3
[(1,1),(0,1),(0,2),(1,2),(2,2),(2,1),(2,0),(1,0),(0,0)]

これは、長さ「サイズ」の2乗の時計回りのスパイラルを構築し、ハンマーの対角線アルゴリズムに重ね合わせます。

于 2013-03-23T12:45:53.090 に答える
0

私はあなたの仕事の解決策は次のとおりだと信じています：

pairs = [(x,y) | u <- [0..], x <- [0..u], y <-[0..u] , u == x+y]

于 2020-05-22T18:10:02.263 に答える