Problem 39 Integer right triangles

2016-10-20 13:50:00   技术   projecteulor python

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?


整数边长直角三角形

若三边长{a,b,c}均为整数的直角三角形周长为p,当p = 120时,恰好存在三个不同的解:

{20,48,52}, {24,45,51}, {30,40,50} 在所有的p ≤ 1000中,p取何值时有解的数目最多?

count = 0
v = 0
for p in range(3, 1001):
    table = []

    for a in range(1, p - 1):
        for b in range(1, p - 1 - a):
            c = p - a - b
            if a + b > c and b + c > a and a + c > b:
                result = [a, b, c]
                result = sorted(result)
                if not result in table and (result[0] * result[0] + result[1] * result[1] == result[2] * result[2]):
                    table.append(result)
    if table:
        if len(table) > count:
            v = p
            count = len(table)
            print p, table

print v, count

上面是愚蠢的暴力破解方法,然后算出答案之后,我开始扮演事后诸葛亮了,blabla,先算出最小边长比,然后算最小公倍数1000以内的就行了,blabla(piapia打回自己的脸)

numbers = []


def gcd(a, b):
    if a < b:
        a, b = b, a

    while b != 0:
        temp = a % b
        a = b
        b = temp

    return a


for c in range(1, 100):
    for b in range(1, c + 1):
        for a in range(1, b + 1):
            if a * a + b * b == c * c and a + b >= c and b + c >= a and a + c >= b and gcd(a, b) == 1 and gcd(c, b) == 1 and gcd(a, c) == 1 :
                    numbers.append(a + b + c)

large = 0
r = 0

for i in range(1, 1001):
    count = 0
for number in numbers:
    if i % number == 0:
        count += 1
if count > large:
    large = count
    r = i

print r
评论已关闭。
评论共