这是我编写的计算毕达哥拉斯三元组的程序。运行程序时，由于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上为立方级别。
Version 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的立方系数。
在z * z < x * x + y * y不再成立后，继续检查增加的z值是没有意义的。这个事实促使版本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
}
}
}
对于1000个数据，版本4比版本2快了约5倍，但它仍然是关于 N 的立方阶。
下一个见解是 x 和 y 是唯一的自变量；z 取决于它们的值，上一个考虑过的 y 值的最后一个 z 值是下一个 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以上的值一次。当N为1000时，它不仅比"计数循环"快100倍以上，而且在N上是二次的，因此随着N增加，速度提升更大。
我遇到了这种改进的情况足够多，以至于对于任何非微不足道的用途（例如遍历数组），我都会对"计数循环"持怀疑态度。
更新：显然，我应该指出V4中一些容易忽略的事情。
两个while循环都由z的值控制（一个直接，另一个通过z的平方间接控制）。内部的while实际上加速了外部的while，而不是与其正交。重要的是要看看循环在做什么，而不仅仅是计算有多少个循环。
V4中的所有计算都是严格的整数算术。与之相比，转换为/从浮点数，以及浮点数计算是很昂贵的。
V4在常量内存中运行，仅需要三个整数变量。没有需要分配和初始化的数组或哈希表（潜在地会导致内存不足错误）。
最初的问题允许所有x、y和z在相同的范围内变化。V1..V4遵循这种模式。
下面是一组不太科学的计时结果（在我的旧笔记本电脑上使用Eclipse的Java和其他东西运行...），其中"使用x,y,z"是通过实例化一个具有三个值的Triple对象并将其放入ArrayList中实现的。（对于这些运行，N被设置为10000，在每种情况下产生了12471个三元组。）
Version 4: 46 sec.
using square root: 134 sec.
array and map: 400 sec.
"数组和映射"算法基本上是:
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源代码，以防我实现有误。
比目前任何解决方案都要快得多。通过三叉树找到三元组。
Wolfram表示：
Hall (1970) and Roberts (1977) prove that
(a, b, c)is a primitive Pythagorean triple if and only if(a,b,c)=(3,4,5)Mwhere
Mis a finite product of the matricesU,A,D.
这里有一个生成每个原始三元组的公式。
在上述公式中，斜边不断增长，所以很容易检查最大长度。
在Python中：
import numpy as np
def gen_prim_pyth_trips(limit=None):
u = np.mat(' 1 2 2; -2 -1 -2; 2 2 3')
a = np.mat(' 1 2 2; 2 1 2; 2 2 3')
d = np.mat('-1 -2 -2; 2 1 2; 2 2 3')
uad = np.array([u, a, d])
m = np.array([3, 4, 5])
while m.size:
m = m.reshape(-1, 3)
if limit:
m = m[m[:, 2] <= limit]
yield from m
m = np.dot(m, uad)
def gen_all_pyth_trips(limit):
for prim in gen_prim_pyth_trips(limit):
i = prim
for _ in range(limit//prim[2]):
yield i
i = i + prim
list(gen_prim_pyth_trips(10**4))花费2.81毫秒返回了1593个元素，而list(gen_all_pyth_trips(10**4))花费19.8毫秒返回了12471个元素。
参考资料，Python中的 被接受的答案对于12471个元素需要38秒。
只是为了好玩，将上限设置为一百万，list(gen_all_pyth_trips(10**6))在2.66秒内返回1980642个元素（在3秒内几乎有两百万个三元组）。list(gen_all_pyth_trips(10**7))会使我的计算机崩溃，因为列表变得如此之大，它消耗了所有的RAM。做类似sum(1 for _ in gen_all_pyth_trips(10**7))的操作可以避免这种限制，并在30秒内返回23471475个元素。
你应该定义 x < y < z。
for x in range (1, 1000):
for y in range (x + 1, 1000):
for z in range(y + 1, 1000):
另一个好的优化方法是仅使用x和y，并计算zsqr = x * x + y * y。如果zsqr是一个完全平方数（或者z = sqrt（zsqr）是一个整数），那么它就是三元组，否则不是。这样，您只需要两个循环而不是三个循环（对于您的示例，快约1000倍）。
a^2 + b^2 = c^2（其中(a, b, c)是三个正整数的三元组）的朴素方法的修改。事实证明，勾股数满足一些相当显著的关系，可以用来生成所有的勾股数。
欧几里得发现了第一个这样的关系。他确定了每个勾股数(a, b, c)，在可能重新排序a和b之后，都有相对质的正整数m和n，其中至少一个是偶数，以及一个正整数k，使得：a = k (2mn)
b = k (m^2 - n^2)
c = k (m^2 + n^2)
要生成勾股数三元组，需要生成两个不同奇偶性的互质正整数 m 和 n，以及一个正整数 k 并应用上述公式。
struct PythagoreanTriple {
public int a { get; private set; }
public int b { get; private set; }
public int c { get; private set; }
public PythagoreanTriple(int a, int b, int c) : this() {
this.a = a < b ? a : b;
this.b = b < a ? a : b;
this.c = c;
}
public override string ToString() {
return String.Format("a = {0}, b = {1}, c = {2}", a, b, c);
}
public static IEnumerable<PythagoreanTriple> GenerateTriples(int max) {
var triples = new List<PythagoreanTriple>();
for (int m = 1; m <= max / 2; m++) {
for (int n = 1 + (m % 2); n < m; n += 2) {
if (m.IsRelativelyPrimeTo(n)) {
for (int k = 1; k <= max / (m * m + n * n); k++) {
triples.Add(EuclidTriple(m, n, k));
}
}
}
}
return triples;
}
private static PythagoreanTriple EuclidTriple(int m, int n, int k) {
int msquared = m * m;
int nsquared = n * n;
return new PythagoreanTriple(k * 2 * m * n, k * (msquared - nsquared), k * (msquared + nsquared));
}
}
public static class IntegerExtensions {
private static int GreatestCommonDivisor(int m, int n) {
return (n == 0 ? m : GreatestCommonDivisor(n, m % n));
}
public static bool IsRelativelyPrimeTo(this int m, int n) {
return GreatestCommonDivisor(m, n) == 1;
}
}
class Program {
static void Main(string[] args) {
PythagoreanTriple.GenerateTriples(1000).ToList().ForEach(t => Console.WriteLine(t));
}
}
生成勾股三元组的公式的维基百科文章中包含其他类似的公式。
算法可以针对速度、内存使用、简单性和其他方面进行调整。
这里有一个针对速度进行调整的pythagore_triplets算法，但代价是内存使用和简单性。如果你只关心速度，这可能是一种选择。
在我的电脑上，计算list(pythagore_triplets(10000))需要40秒，而ΤΖΩΤΖΙΟΥ的算法需要63秒，而Tafkas的算法（以及所有使用3个嵌套循环而不仅仅是2个循环的其他算法）可能需要数天的计算时间。
def pythagore_triplets(n=1000):
maxn=int(n*(2**0.5))+1 # max int whose square may be the sum of two squares
squares=[x*x for x in xrange(maxn+1)] # calculate all the squares once
reverse_squares=dict([(squares[i],i) for i in xrange(maxn+1)]) # x*x=>x
for x in xrange(1,n):
x2 = squares[x]
for y in xrange(x,n+1):
y2 = squares[y]
z = reverse_squares.get(x2+y2)
if z != None:
yield x,y,z
>>> print list(pythagore_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]
def gcd(a, b):
while b != 0:
t = b
b = a%b
a = t
return a
def find_triple(upper_boundary=1000):
for c in xrange(5,upper_boundary+1):
for b in xrange(4,c):
for a in xrange(3,b):
if (a*a + b*b == c*c and gcd(a,b) == 1):
yield a,b,c
def pyth_triplets(n=1000):
"Version 1"
for x in xrange(1, n):
x2= x*x # time saver
for y in xrange(x+1, n): # y > x
z2= x2 + y*y
zs= int(z2**.5)
if zs*zs == z2:
yield x, y, zs
>>> print list(pyth_triplets(20))
[(3, 4, 5), (5, 12, 13), (6, 8, 10), (8, 15, 17), (9, 12, 15), (12, 16, 20)]
V.1算法具有单调递增的x值。
看来这个问题还没有解决 :)
自从我回来并重新审视了代码后，我尝试了第二种方法，它几乎比我的先前建议快4倍（对于N = 10000，大约占CPU时间的26％），因为它避免了许多不必要的计算：
def pyth_triplets(n=1000):
"Version 2"
for z in xrange(5, n+1):
z2= z*z # time saver
x= x2= 1
y= z - 1; y2= y*y
while x < y:
x2_y2= x2 + y2
if x2_y2 == z2:
yield x, y, z
x+= 1; x2= x*x
y-= 1; y2= y*y
elif x2_y2 < z2:
x+= 1; x2= x*x
else:
y-= 1; y2= y*y
>>> print list(pyth_triplets(20))
[(3, 4, 5), (6, 8, 10), (5, 12, 13), (9, 12, 15), (8, 15, 17), (12, 16, 20)]
def pyth_triplets(n=1000):
"Version 3"
for z in xrange(5, n+1):
z2= z*z # time saver
x= x2= 1; xstep= 3
y= z - 1; y2= y*y; ystep= 2*y - 1
while x < y:
x2_y2= x2 + y2
if x2_y2 == z2:
yield x, y, z
x+= 1; x2+= xstep; xstep+= 2
y-= 1; y2-= ystep; ystep-= 2
elif x2_y2 < z2:
x+= 1; x2+= xstep; xstep+= 2
else:
y-= 1; y2-= ystep; ystep-= 2
我只是扩展了Kyle Gullion的答案，使三元组按照斜边和最长边的顺序排序。
它不使用numpy，但需要一个SortedCollection（或SortedList），例如this one。
def primitive_triples():
""" generates primitive Pythagorean triplets x<y<z
sorted by hypotenuse z, then longest side y
through Berggren's matrices and breadth first traversal of ternary tree
:see: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples
"""
key=lambda x:(x[2],x[1])
triples=SortedCollection(key=key)
triples.insert([3,4,5])
A = [[ 1,-2, 2], [ 2,-1, 2], [ 2,-2, 3]]
B = [[ 1, 2, 2], [ 2, 1, 2], [ 2, 2, 3]]
C = [[-1, 2, 2], [-2, 1, 2], [-2, 2, 3]]
while triples:
(a,b,c) = triples.pop(0)
yield (a,b,c)
# expand this triple to 3 new triples using Berggren's matrices
for X in [A,B,C]:
triple=[sum(x*y for (x,y) in zip([a,b,c],X[i])) for i in range(3)]
if triple[0]>triple[1]: # ensure x<y<z
triple[0],triple[1]=triple[1],triple[0]
triples.insert(triple)
def triples():
""" generates all Pythagorean triplets triplets x<y<z
sorted by hypotenuse z, then longest side y
"""
prim=[] #list of primitive triples up to now
key=lambda x:(x[2],x[1])
samez=SortedCollection(key=key) # temp triplets with same z
buffer=SortedCollection(key=key) # temp for triplets with smaller z
for pt in primitive_triples():
z=pt[2]
if samez and z!=samez[0][2]: #flush samez
while samez:
yield samez.pop(0)
samez.insert(pt)
#build buffer of smaller multiples of the primitives already found
for i,pm in enumerate(prim):
p,m=pm[0:2]
while True:
mz=m*p[2]
if mz < z:
buffer.insert(tuple(m*x for x in p))
elif mz == z:
# we need another buffer because next pt might have
# the same z as the previous one, but a smaller y than
# a multiple of a previous pt ...
samez.insert(tuple(m*x for x in p))
else:
break
m+=1
prim[i][1]=m #update multiplier for next loops
while buffer: #flush buffer
yield buffer.pop(0)
prim.append([pt,2]) #add primitive to the list
if x*x == y*y + z*z && gcd(y,z) == 1:
接下来，您需要实现一个方法，返回两个给定数字的最大公约数（gcd）。再次以Ruby为例：
def gcd(a, b)
while b != 0
t = b
b = a%b
a = t
end
return a
end
def find_triple(upper_boundary)
(5..upper_boundary).each {|c|
(4..c-1).each {|b|
(3..b-1).each {|a|
if (a*a + b*b == c*c && gcd(a,b) == 1)
puts "#{a} \t #{b} \t #{c}"
end
}
}
}
end
虽然这是一个老问题，但我仍然想分享一下我的看法。有两种通用方法可以生成唯一的勾股数三元组。一种是通过缩放，另一种是使用这个古老的公式。
所谓缩放，就是取一个常数 n，然后将基本三元组（例如 3、4、5）分别乘以 n。以 n=2 为例，我们得到下一个三元组 6、8、10。
缩放
def pythagoreanScaled(n):
triplelist = []
for x in range(n):
one = 3*x
two = 4*x
three = 5*x
triple = (one,two,three)
triplelist.append(triple)
return triplelist
公式方法利用了这样一个事实：如果我们取一个数x，计算2m、m^2+1和m^2-1，那么这三个数总是构成一个勾股三元组。
公式
def pythagoreantriple(n):
triplelist = []
for x in range(2,n):
double = x*2
minus = x**2-1
plus = x**2+1
triple = (double,minus,plus)
triplelist.append(triple)
return triplelist
from math import sqrt
from itertools import combinations
#Pythagorean triplet - a^2 + b^2 = c^2 for (a,b) <= (1999,1999)
def gen_pyth(n):
if n >= 2000 :
return
ELEM = [ [ i,j,i*i + j*j ] for i , j in list(combinations(range(1, n + 1 ), 2)) if sqrt(i*i + j*j).is_integer() ]
print (*ELEM , sep = "\n")
gen_pyth(200)