这是我写的计算毕达哥拉斯三胞胎的程序.当我运行程序时,由于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()
joe*_*ely 75
Pythagorean Triples为声称" 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
}
}
}
对于N1000,这比版本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快100多倍N,而且是二次方N,因此加速随着增长而N增加.
我经常遇到这种改进,经常不信任"计数循环",除了最琐碎的用途(例如遍历数组).
更新:显然我应该指出一些容易被忽视的关于V4的东西.
两者的的while圈由的值控制z(一个直接,其他间接地通过的平方z).内部while实际上正在加速外部while,而不是正交.查看循环正在做什么非常重要,而不仅仅是计算循环次数.
V4中的所有计算都是严格的整数运算.相比之下,转换到浮点或从浮点转换以及浮点计算都是昂贵的.
V4在常量内存中运行,只需要三个整数变量.没有要分配和初始化的数组或散列表(并且可能导致内存不足错误).
原来的问题让所有的x,y以及x在相同的范围内变化.V1..V4遵循该模式.
下面是一组不太科学的时序(在我的旧笔记本电脑上使用Eclipse,其他东西正在运行...),其中"使用x,y,z"是通过使用三个值实例化Triple对象来实现的并将其放在ArrayList中.(对于这些运行,N设置为10,000,在每种情况下产生12,471三倍.)
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源代码以供我定时的其他变体,以防我实施错误.
Kyl*_*ion 41
到目前为止,它比任何解决方案都要快得多.通过三元树找到三胞胎.
Wolfram说:
Hall(1970)和Roberts(1977)证明,这是一个原始的毕达哥拉斯三重奏,当且仅当
(a,b,c)=(3,4,5)M其中M是矩阵U,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))使用1980642元素(在3秒内几乎200万三倍)将上限设置为2.66秒内返回100万.list(gen_all_pyth_trips(10**7))随着列表变得如此之大,它耗尽了最后一点内存,让我的计算机瘫痪.做类似的事情sum(1 for _ in gen_all_pyth_trips(10**7))绕过那个限制并在30秒内返回23471475个元素.
有关所用算法的更多信息,请查看有关Wolfram和Wikipedia的文章.
sch*_*der 13
你应该定义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倍).
jas*_*son 11
先前列出的用于生成毕达哥拉斯三元组的算法是从基本关系派生的朴素方法的所有修改,a^2 + b^2 = c^2其中它(a, b, c)是正整数的三元组.事实证明,毕达哥拉斯三胞胎满足了一些相当显着的关系,可以用来生成所有毕达哥拉斯三胞胎.
欧几里得发现了第一个这样的关系.他确定,对于每个毕达哥拉斯三元组(a, b, c),可能在重新排序之后,a并且b存在相对的正整数m且n其中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)]
请注意,如果您要计算前十亿个三元组,那么由于内存不足错误,此算法在启动之前将崩溃.因此,对于高n值,ΤΖΩΤΖΙΟΥ的算法可能是更安全的选择.
顺便说一下,这是Tafkas的算法,为了我的性能测试而翻译成python.它的缺陷是需要3个循环而不是2个循环.
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倍(大约26%的CPU时间为N = 10000),因为它避免了很多不必要的计算:
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)]
请注意,此算法具有增加的z值.
如果算法被转换为C -where,更接近金属,乘法比加法需要更多的时间 - 考虑到连续正方形之间的步长是这样的事实,可以最小化必要的乘法:
(x + 1)² - x²=(x + 1)(x + 1) - x²=x²+ 2x + 1 - x²= 2x + 1
所以所有的内部x2= x*x和y2= y*y将被转换为加法和减法,如下所示:
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
当然,在Python中,与版本2相比,产生的额外字节码实际上减慢了算法的速度,但我敢打赌(不检查:) V.3在C中更快.
干杯大家:)