什么是产生勾股数的最好方法？ [英] What is the best way to generate Pythagorean triples?

问题描述

我与简单code试过，当你只是检查所有组合a和b，然后检查如果c的平方根是一个整数，但code是真的慢，然后我曾尝试与欧氏公式

I have tried with that simple code when you just check all the combinations for a and b and then check if square root of c is an integer, but that code is really slow, then I have tried with Euclid's formula

a = d*(n^2 - m^2)
b = 2*n*m*d
c = d*(n^2 + m^2)

和我写了一个code，你前n以

and I have written a code where you first find n with

trunc(sqrt(max_value))
//this is in pascal

然后检查0℃每个组合; M＆LT; n，而是我得到重复的结果，像如果n是7，m是5，d是1，n是6，m是1且d为2。在这两种情况下，你会得到24，70和7​​4。那么什么是计算数量勾股数，我似乎无法找到一种方法，另外，如果我所有的结果添加到一个数组，然后检查了良好的快速方式数组重复，它只是需要太多时间......如果有人能帮助我的code也可以是帕斯卡，C或Python，我能理解所有...

and then you check every combination of 0 < m < n but I get duplicate results, like if n is 7, m is 5 and d is 1, and n is 6, m is 1 and d is 2 . In both cases you get 24, 70 and 74. So what is a good fast way to calculate the number of Pythagorean triples, I can't seem to find a way, also if I add all results to an array, and then check the array for duplicates, it just takes too much time... If anyone can help me with the code it can be pascal, c or python, I can understand all...

推荐答案

我很好奇，所以我决定试试这个。我发现，<一个href=\"http://en.wikipedia.org/wiki/Formulas_for_generating_Pythagorean_triples#Progressions_of_whole_and_fractional_numbers\"相对=nofollow>这个算法是pretty容易在Python实现快速的工作pretty：

I was curious so I decided to try this. I found that this algorithm was pretty easy to implement in Python and works pretty fast:

import math                                                                 

def pythagorean_triples(n):                                                 
    a, b, c = 1, 3, 0                                                       
    while c < n:                                                            
        a_ = (a * b) + a                                                    
        c = math.sqrt(a_**2 + b**2)                                         
        if c == int(c):                                                     
            yield b, a_, int(c)                                             
        a += 1                                                              
        b += 2                                                              

if __name__ == '__main__':                                                  
    import sys                                                              
    for pt in pythagorean_triples(int(sys.argv[1])):                        
        print(pt)

通过复制该脚本到 pythagorean_triples.py 运行 python3 pythagorean_triples.pyñ，其中<$ C试试吧$ C> N 是你希望它产生最大 C 。 （你可以，如果你喜欢，以及以后使用Python2。）

Try it by copying that script into pythagorean_triples.py and running python3 pythagorean_triples.py n where n is the maximum c you want it to generate. (You can use later Python2 if you like as well.)

这篇关于什么是产生勾股数的最好方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！