0

x, y ∈ N であるすべてのペア (x,y) のリストを返す関数を作成する必要があります。

  • x は 2 つの自然数の積 (x = a • b、ここで a, b ∈ N)であり、
  • x は 5 より大きいが 500より小さい
  • y は平方数 (y = c² ここで c ∈ N) であり、1000 以下であり、かつ
  • x は y の約数です。

私の試み：

listPairs :: [(Int, Int)] 
listPairs = [(a*b, y) | y <- [0..], a <- [0..], b <- [0..], 
                        (a*b) > 5, (a*b) < 500, (y*y) < 1001, 
                        mod y (a*b) == 0]

しかし、それは何も返さず、コンピューターはそれに対して多くの作業を行います。

ただし、たとえば の範囲を小さくするaと、b最大1 分かかりますが、正しい結果が返されます。y[0..400]

では、どうすればパフォーマンスの問題を解決できますか?

4

1 に答える 1

1

したがって、もちろん、無限リストのネストされたリスト内包表記は終了しません。

幸いなことに、リストは無限ではありません。限界があります。の場合、それはとx = a*b < 500でなければならないことがわかります。また、ちょうどです。そう、a < 500b < 500c = y*y < 1001y < 32

listPairs :: [(Int, Int)] 
listPairs = 
    [(x, c*c) | c <- [1..31], a <- [1..499],    -- a*b < 500 ==> b<500/a ,
                b <- [a..min 499 (div 500 a)],  -- a*b==b*a  ==> b >= a
                let x = a*b, x > 5,  
                -- (a*b) < 500, (c*c) < 1001,   -- no need to test this
                rem (c*c) x == 0]

mod 0 n == 0自明なので、ここでは「自然数」から 0 を除いています。

いくつかの表現 (例: ) を持つことができるため、b値をb >= ainに制限しましたが、ここではまだいくつかの重複が生成されます。x=a*bx1*6 == 2*3

Data.List.nubそれらを取り除くために使用できます。

于 2013-05-21T15:32:34.707 に答える