使用其中一个直角边小于某个限制条件生成勾股数三元组

Question

使用其中一个直角边小于某个限制条件生成勾股数三元组

3

现在我用以下方法计算（原始）勾股数

def generateTriples(limit):
    for n in xrange(1, limit):
        if (n**2 + (n+1)**2 > limit): 
            break
        for m in xrange(n+1, limit, 2):
            if (n**2 + m**2 > limit): 
                break
            if (gcd(n, m) > 1): 
                continue
            yield (m**2 - n**2, 2*m*n, m**2 + n**2)

但是这样的操作会输出所有三元组，其中所有的边长都小于等于限制。例如：

for triple in generateTriples(25):
    print triple
'''
(3, 4, 5)
(15, 8, 17)
(5, 12, 13)
(7, 24, 25)
'''

但我想做的是改变方式，只限制腿长。斜边可以无限大 - 我只想让min（leg1，leg2）小于或等于限制。

我也希望生成非原始值，这意味着在所有项上按k缩放（也使min（leg1，leg2）小于等于限制），但我担心这样会得到重复项。

任何建议将不胜感激。

- AOAOne

你应该看一下我的修改。原始版本无法找到所有的三元组；我包装了你的新版本，相当高效，并且可以找到所有的三元组。 - agf

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- agf · Accepted Answer

此函数确定与完美三元组中的一条腿配对的最大可能斜边，然后使用您的函数实际搜索三元组：

from fractions import gcd

def generateTriples(limit):
    for n in xrange(1, limit):
        if (n**2 + (n+1)**2 > limit):
            break
        for m in xrange(n+1, limit, 2):
            if (n**2 + m**2 > limit):
                break
            if (gcd(n, m) > 1):
                continue
            yield (m**2 - n**2, 2*m*n, m**2 + n**2)

def generate_triples_limit_leg(leg):
    limit = leg**2 / 2 + 1

    for triple in generateTriples(limit):
        if min(triple) <= leg:
            yield triple

print list(generate_triples_limit_leg(i))

这个版本不能找到所有的三元组，但是可以直接在最短边上操作：

def generate_triples(limit):
    # for each number up to the limit
    # Python ranges don't include the max number
    # start from 4 because 1 and 2 are invalid
    # and 3 and 4 give the same triplet
    for i in range(4, limit + 1):
        # if i is odd
        if i % 2:
            # the two larger legs are the integers
            # above and below half of the square of the smallest leg
            # // is floor division
            big = i**2 // 2
            yield i, big, big + 1
        else:
            # the two other legs are the integers
            # above and below half of the smallest leg squared
            big = (i // 2)**2
            yield i, big - 1, big + 1


print list(generate_triples(10))
# [(3, 4, 5), (5, 12, 13), (6, 8, 10),  (7, 24, 25), 
#             (8, 15, 17), (9, 40, 41), (10, 24, 26)]