0

我必须编写一个函数，它返回所有对 (x,y) 的列表，其中 x, y ∈ N和：

  • x 是两个自然数的乘积 (x = a • b, 其中 a, b ∈ N)并且
  • x 确实大于 5 但确实小于 500，并且
  • y 是一个不大于 1000 的平方数 (y = c² 其中 c ∈ N)，并且
  • 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和yeg选择较小的范围[0..400]，则最多需要一分钟，但它会返回正确的结果。

那么我该如何解决性能问题呢？

4

1 回答 1

1

因此，无限列表上的嵌套列表推导当然不会终止。

幸运的是，您的列表不是无限的。有个限度。如果x = a*b < 500，那么我们知道它一定是a < 500和b < 500。此外，c = y*y < 1001只是y < 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*b，因为x可以有多种表示形式（例如1*6 == 2*3）。

你可以Data.List.nub用来摆脱它们。

于 2013-05-21T15:32:34.707 回答