python - 生成独特的，有序的勾股三胞胎

Question

这是我编写的用于计算勾股三胞胎的程序。当我运行该程序时，由于使用if语句，它会将每组三胞胎打印两次。有什么办法可以让我的程序只打印一组新的三胞胎一次？谢谢。

import math

def main():
    for x in range (1, 1000):
        for y in range (1, 1000):
            for z in range(1, 1000):
                if x*x == y*y + z*z:
                    print y, z, x
                    print '-'*50

if __name__ == '__main__':
    main()  

Answer 1

毕达哥拉斯三元组是声称“ for循环被认为是有害的”的一个很好的例子，因为for循环诱使我们考虑计数，这通常是任务中最不相关的部分。

(我将坚持使用伪代码以避免语言偏见，并简化伪代码，我不会优化x * x和y * y等多种计算方法。)

版本1 :

for x in 1..N {
    for y in 1..N {
        for z in 1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

是最糟糕的解决方案。它生成重复项，并遍历空间中无用的部分(例如，每当 z < y时)。它的时间复杂度取决于 N。

第2版(第一个改进)来自要求保留 x < y < z，如下所示:

for x in 1..N {
    for y in x+1..N {
        for z in y+1..N {
            if x * x + y * y == z * z then {
                // use x, y, z
            }
        }
    }
}

这样可以减少运行时间并消除重复的解决方案。但是，它在 N上仍然是立方的；改进只是减少了 N -cubed的系数。

在 z不再成立之后继续检查 z * z < x * x + y * y的增加值是没有意义的。这个事实激发了 版本3 ，这是通过 z进行暴力迭代的第一步:

for x in 1..N {
    for y in x+1..N {
        z = y + 1
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
    }
}

对于 N 1000，这比版本2快5倍，但是在 N上仍然是三次。

下一个见解是 x和 y是唯一的独立变量。 z取决于它们的值，并且考虑到 z的上一个值的最后一个 y值是 y的下一个值的良好起始搜索值。这导致 版本4 :

for x in 1..N {
    y = x+1
    z = y+1
    while z <= N {
        while z * z < x * x + y * y {
            z = z + 1
        }
        if z * z == x * x + y * y and z <= N then {
            // use x, y, z
        }
        y = y + 1
    }
}

这允许 y和 z仅“扫描”一次 x以上的值。对于1000的 N而言，它不仅速度快100倍以上，而且在 N上是平方的，因此，随着 N的增长，速度也随之提高。

我经常遇到这种改进，以至于对除最琐碎的用途(例如遍历数组)以外的任何用途的“计数循环”都不信任。

更新:显然，我应该指出一些有关V4的事情，这些事情很容易忽略。

while循环的两个都由z的值控制(一个直接，另一个通过z的平方间接地控制)。内部while实际上是在加快外部while的速度，而不是与之正交。重要的是要查看循环的作用，而不仅仅是计算有多少个循环。

V4中的所有计算都是严格的整数算术运算。通过比较，与浮点数之间的转换以及浮点数的计算成本很高。

V4在恒定内存中运行，仅需要三个整数变量。没有要分配和初始化(并且可能导致内存不足错误)的数组或哈希表。

最初的问题允许所有x，y和x在相同范围内变化。 V1..V4遵循该模式。

下面是一组不太科学的计时(在我的较旧笔记本电脑上使用Eclipse下的Java在运行其他东西的情况下...)，其中“使用x，y，z”是通过实例化具有三个值的Triple对象来实现的并将其放在ArrayList中。 (对于这些运行， N设置为10,000，在每种情况下均产生12,471个三元组。)

Version 4:           46 sec.
using square root:  134 sec.
array and map:      400 sec.

“数组和 map ”算法本质上是:

squares = array of i*i for i in 1 .. N
roots = map of i*i -> i for i in 1 .. N
for x in 1 .. N
    for y in x+1 .. N
        z = roots[squares[x] + squares[y]]
        if z exists use x, y, z

“使用平方根”算法本质上是:

for x in 1 .. N
    for y in x+1 .. N
        z = (int) sqrt(x * x + y * y)
        if z * z == x * x + y * y then use x, y, z

V4的实际代码是:

public Collection<Triple> byBetterWhileLoop() {
    Collection<Triple> result = new ArrayList<Triple>(limit);
    for (int x = 1; x < limit; ++x) {
        int xx = x * x;
        int y = x + 1;
        int z = y + 1;
        while (z <= limit) {
            int zz = xx + y * y;
            while (z * z < zz) {++z;}
            if (z * z == zz && z <= limit) {
                result.add(new Triple(x, y, z));
            }
            ++y;
        }
    }
    return result;
}

注意 x * x是在外部循环中计算的(尽管我没有费心去缓存 z * z)；在其他变体中进行了类似的优化。

我会很高兴按要求提供Java源代码，以提供我选择的其他版本，以防万一我没有正确实现任何东西。