2

我编写了以下函数，它根据毕达哥拉斯三元组的定义返回一个无限的三元组成员列表 (a, b, c)：a^2 + b^2 = c^2。我需要能够检查给定的元组 (a, b, c) 是否是有效的毕达哥拉斯三元组。我这样做的方法是通过函数生成一个无限的元组列表，然后我将此列表elem与我要检查的 3 元组一起传递给。

但是，当它将我的 3 元组与无限列表的成员匹配时，这不会终止。

代码：

pythagoreanTriples::[(Integer, Integer, Integer)]
pythagoreanTriples = [(a, b, c) | a <- [2..], b <- [a+1..], 
                                  c <- [b+1..], a*a + b*b == c*c ]
main = do
print $ elem (30, 72, 78) (pythagoreanTriples)

我知道逻辑是正确的，因为我尝试修改上述函数以生成有限列表，并且逻辑运行得非常好：

pythagoreanTriples n = [(a, b, c) | a <- [2..n], b <- [a+1..n], 
                                    c <- [b+1..n], a*a + b*b == c*c ]

main = do
print $ elem (30, 72, 78) (pythagoreanTriples 100)

但是，必须使用无限列表来完成。请向我建议如何使它工作。谢谢。

4

3 回答 3

3

从你的有限代码开始，

pythagoreanTriples n = [(a, b, c) | a <- [2..n], b <- [a+1..n], 
                                    c <- [b+1..n], a*a + b*b == c*c ]

并简单地使其适用n于 1 及以上的任何一个：

pythagoreanTriples   = [(a, b, c) | n <- [1..],
                                    a <- [2..n], b <- [a+1..n], 
                                    c <- [b+1..n], a*a + b*b == c*c ]

（但这会产生很多重复）。我宁愿先确定最大的，c价值，然后找到a和b这样的，a < b < c条件成立：

                     = [(a, b, c) | n <- [1..],
                                    c <- [2..n], a <- [2..c-1], 
                                    b <- [a+1..c-1], a*a + b*b == c*c ]

但是我们现在需要它做什么n？我们不：

pythagoreanTriples = [(a, b, c) | c <- [2..], a <- [2..c-1], 
                                  b <- [a+1..c-1], a*a + b*b == c*c ]

以便

GHCi> 取 20 个 pythagoreanTriples

[(3,4,5),(6,8,10),(5,12,13)​​,(9,12,15),(8,15,17),(12,16 ,20),(7,24,25),(15,20,25),
(10,24,26),(20,21,29),(18,24,30),(16,30,34 ),(21,28,35),(12,35,37),(15,36,39),(24,32,40),
(9,40,41),(27,36,45), (14,48,50),(30,40,50)]

（这种情况a==b是不可能的，因为sqrt(2)是一个无理数）。

于 2014-11-16T18:41:12.477 回答
2

问题在于列表是如何生成的。让我们跳进 ghci 看看无限列表的样子：

ghci> [(a, b, c) | a <- [2..], b <- [a+1..], c <- [b+1..]]

我们得到如下所示的东西：

[(2,3,4),(2,3,5),(2,3,6),(2,3,7),(2,3,8),(2,3,9),(2,3,10),(2,3,11),(2,3,12),..]

因为您没有指定何时停止迭代c并转到b，所以上述序列将一直持续到永恒。

添加约束后，我们可以看到没有项目满足约束，因为 13 的平方根不是整数。

如果我们稍微调整一下条件，我们就有一个工作无限列表：

pythagoreanTriples = [(a, b, c) | b <- [3..], a <- [2..b-1], c <- [b+1..a^2+b^2], a^2+b^2 == c^2]

现在因为我们已经指定了何时停止遍历列表，所以在继续之前c会提前一次迭代。因为仅仅添加这个约束是行不通的，所以我们还必须添加一个到，否则我们会遇到和以前一样的问题。acca

因此，我们决定选择较长导管的长度和与较小导管的最大结合。基于这些约束，我们现在还可以在c.

如果我们决定直接计算 c 并检查它是否是正方形，我们可以更快地做到这一点。这看起来像这样：

pythagoreanTriples = [(a, b, c) | b <- [3..], a <- [2..b-1], let c = a^2 + b^2, isSquare c]
  where
    isSquare x = round x == (round $ sqrt x) ^ 2

请注意，由于浮点运算，这可能不准确。

你可以把这个列表推导想象成一个嵌套的 for 循环：

for (number a = 2; true; a++)
{
    for (number b = a+1; true; b++)
    {
        for (number c = b+1; true; c++)
        {
            if (a^2 + b^2 == c^2)
            {
                add (a, b, c) to a list;
            }
        }
    }
}
于 2014-11-16T11:04:12.550 回答
1

问题在于迭代的顺序。[(a, b) | a <- [1..100], b <- [1..100]]将首先遍历 all b，然后遍历 all a。

Prelude> [(a, b) | a <- [1..10], b <- [1..10]]
[(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(1,10),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(2,10),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(3,10),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(4,10),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(5,10),(6,1),(6,2),(6,3),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(6,10),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(7,10),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(8,10),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9),(9,10),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9),(10,10)]

如您所见，在增量b之前完全迭代。a但是，正如您所做的那样b <- [1..]，b永远不会完成迭代，并且永远a保持1不变。

于 2014-11-16T11:04:58.137 回答