生成唯一的、有序的勾股三元组 [英] Generating unique, ordered Pythagorean triplets

查看：32
本文介绍了生成唯一的、有序的勾股三元组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

这是我写的一个计算勾股三元组的程序.当我运行程序时，由于 if 语句，它会将每组三元组打印两次.有什么办法可以告诉程序只打印一组新的三元组吗?谢谢.

导入数学定义主():对于范围 (1, 1000) 中的 x:对于范围 (1, 1000) 中的 y:对于范围内的 z (1, 1000):如果 x*x == y*y + z*z:打印 y, z, x打印-"*50如果 __name__ == '__main__':主要的()

解决方案

Pythagorean Triples 是声称for 循环被认为有害"的一个很好的例子，因为 for 循环诱使我们考虑计数，这通常是任务中最不相关的部分.

(我将坚持使用伪代码以避免语言偏见，并保持伪代码精简，我不会优化去除例如 x * x 和 <代码>y * y.)

版本 1:

for x in 1..N {对于 1..N 中的 y {对于 1..N 中的 z {如果 x * x + y * y == z * z 那么 {//使用 x, y, z}}}}

是最糟糕的解决方案.它生成重复项，并遍历无用的部分空间(例如，每当 z 时).它的时间复杂度是 N 上的三次方.

第 2 版，第一个改进，来自要求 x <y＜z 保持，如:

for x in 1..N {对于 y 在 x+1..N {对于 z 在 y+1..N {如果 x * x + y * y == z * z 那么 {//使用 x, y, z}}}}

这减少了运行时间并消除了重复的解决方案.但是，它在 N 上仍然是三次方；改进只是降低了 N-cubed 的系数.

在z * z <之后继续检查z的递增值是没有意义的.x * x + y * y 不再成立.这一事实推动了 第 3 版，这是远离对 z 进行暴力迭代的第一步:

for x in 1..N {对于 y 在 x+1..N {z = y + 1而 z * z

对于 1000 的 N，这比版本 2 快约 5 倍，但它在 N 上仍然三次.

下一个见解是 x 和 y 是唯一的自变量；z 取决于它们的值，并且为 y 的前一个值考虑的最后一个 z 值是一个很好的开始y 的下一个值的搜索值.这导致了第 4 版:

for x in 1..N {y = x+1z = y+1而 z <= N {而 z * z

允许 y 和 z 只扫描"x 上面的值一次.N 为 1000 时，它不仅快了 100 多倍，而且在 N 上是二次的，所以加速随着 N 的增长而增加.>

我经常遇到这种改进，以至于我对计数循环"不信任，除了最琐碎的用途(例如遍历数组).

更新:显然我应该指出一些关于 V4 的容易被忽视的事情.

  1. while 循环的两个都由 z 的值控制(一个直接，另一个通过平方的间接z).内部 while 实际上是在加速外部 while，而不是与其正交.重要的是查看循环正在做什么，而不仅仅是计算有多少循环.

  2. V4 中的所有计算都是严格的整数运算.相比之下，与浮点之间的转换以及浮点计算的成本很高.

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

  4. 原始问题允许所有 x、y 和 x 在同一范围内变化.V1..V4 遵循该模式.

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

第 4 版:46 秒.使用平方根:134 秒.数组和地图:400 秒.

数组和映射"算法本质上:

squares = 数组 i*i for i in 1 .. N根 = i*i 的映射 ->i for i in 1 .. N对于 x in 1 .. N对于 y 在 x+1 .. Nz = 根[平方[x] + 平方[y]]如果 z 存在使用 x, y, z

使用平方根"算法本质上:

for x in 1 .. N对于 y 在 x+1 .. Nz = (int) sqrt(x * x + y * y)如果 z * z == x * x + y * y 然后使用 x, y, z

V4 的实际代码是:

公共收藏byBetterWhileLoop() {集合<三重>结果 = 新的 ArrayList(限制)；for (int x = 1; x

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

我很乐意应要求为我计时的其他变体提供 Java 源代码，以防我执行错误.

This is a program I wrote to calculate Pythagorean triplets. When I run the program it prints each set of triplets twice because of the if statement. Is there any way I can tell the program to only print a new set of triplets once? Thanks.

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()

解决方案

Pythagorean Triples make a good example for claiming "for loops considered harmful", because for loops seduce us into thinking about counting, often the most irrelevant part of a task.

(I'm going to stick with pseudo-code to avoid language biases, and to keep the pseudo-code streamlined, I'll not optimize away multiple calculations of e.g. x * x and y * y.)

Version 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
            }
        }
    }
}

is the worst solution. It generates duplicates, and traverses parts of the space that aren't useful (e.g. whenever z < y). Its time complexity is cubic on N.

Version 2, the first improvement, comes from requiring x < y < z to hold, as in:

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
            }
        }
    }
}

which reduces run time and eliminates duplicated solutions. However, it is still cubic on N; the improvement is just a reduction of the co-efficient of N-cubed.

It is pointless to continue examining increasing values of z after z * z < x * x + y * y no longer holds. That fact motivates Version 3, the first step away from brute-force iteration over 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
        }
    }
}

For N of 1000, this is about 5 times faster than Version 2, but it is still cubic on N.

The next insight is that x and y are the only independent variables; z depends on their values, and the last z value considered for the previous value of y is a good starting search value for the next value of y. That leads to Version 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
    }
}

which allows y and z to "sweep" the values above x only once. Not only is it over 100 times faster for N of 1000, it is quadratic on N, so the speedup increases as N grows.

I've encountered this kind of improvement often enough to be mistrustful of "counting loops" for any but the most trivial uses (e.g. traversing an array).

Update: Apparently I should have pointed out a few things about V4 that are easy to overlook.

  1. Both of the while loops are controlled by the value of z (one directly, the other indirectly through the square of z). The inner while is actually speeding up the outer while, rather than being orthogonal to it. It's important to look at what the loops are doing, not merely to count how many loops there are.

  2. All of the calculations in V4 are strictly integer arithmetic. Conversion to/from floating-point, as well as floating-point calculations, are costly by comparison.

  3. V4 runs in constant memory, requiring only three integer variables. There are no arrays or hash tables to allocate and initialize (and, potentially, to cause an out-of-memory error).

  4. The original question allowed all of x, y, and x to vary over the same range. V1..V4 followed that pattern.

Below is a not-very-scientific set of timings (using Java under Eclipse on my older laptop with other stuff running...), where the "use x, y, z" was implemented by instantiating a Triple object with the three values and putting it in an ArrayList. (For these runs, N was set to 10,000, which produced 12,471 triples in each case.)

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

The "array and map" algorithm is essentially:

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

The "using square root" algorithm is essentially:

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

The actual code for V4 is:

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;
}

Note that x * x is calculated in the outer loop (although I didn't bother to cache z * z); similar optimizations are done in the other variations.

I'll be glad to provide the Java source code on request for the other variations I timed, in case I've mis-implemented anything.

这篇关于生成唯一的、有序的勾股三元组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
Python最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆