这是我编写的用于计算勾股三胞胎的程序。当我运行该程序时,由于使用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()
最佳答案
毕达哥拉斯三元组是声称“ 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
的速度,而不是与之正交。重要的是要查看循环的作用,而不仅仅是计算有多少个循环。 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源代码,以提供我选择的其他版本,以防万一我没有正确实现任何东西。
关于python - 生成独特的,有序的勾股三胞胎,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/575117/