104 lines
3.0 KiB
Python
104 lines
3.0 KiB
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?
|
||
"""
|
||
|
||
import time
|
||
import math
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start_time = time.time()
|
||
result = func(*args, **kwargs)
|
||
end_time = time.time()
|
||
print(f"{func.__name__} took time: {end_time - start_time:.6f} seconds")
|
||
return result
|
||
return wrapper
|
||
|
||
|
||
def generate_pythagorean_triples(max_perimeter: int = 1000) :
|
||
"""
|
||
使用yield生成勾股三元组的m和n参数
|
||
|
||
参数:
|
||
max_perimeter: 三角形周长的最大值
|
||
|
||
生成:
|
||
(m, n) 元组，满足：
|
||
- m > n > 0
|
||
- m和n互质 (gcd(m, n) == 1)
|
||
- m和n一奇一偶
|
||
- 三角形周长 2*m*(m+n) < max_perimeter
|
||
"""
|
||
# 从m=2开始（因为m>n≥1）
|
||
m = 2
|
||
|
||
while True:
|
||
# 对于每个m，n从1到m-1
|
||
for n in range(1, m):
|
||
# 检查是否满足互质条件
|
||
if math.gcd(m, n) != 1:
|
||
continue
|
||
|
||
# 检查是否一奇一偶
|
||
if (m % 2) == (n % 2):
|
||
continue
|
||
|
||
# 计算对应三角形的周长
|
||
perimeter = 2 * m * (m + n)
|
||
|
||
# 如果周长超过限制，则停止生成
|
||
if perimeter >= max_perimeter:
|
||
# 对于当前m，如果最小周长（当n=1时）已经超过限制，
|
||
# 那么后续更大的m也会超过，所以完全停止
|
||
if n == 1:
|
||
return
|
||
|
||
# 如果周长在限制内，则yield当前(m, n)
|
||
if perimeter < max_perimeter:
|
||
yield (m, n)
|
||
|
||
m += 1
|
||
|
||
|
||
def triangle_length(m:int, n:int) -> int:
|
||
return 2 * m * (m + n)
|
||
|
||
def get_abc(m:int, n:int) -> tuple[int, int, int]:
|
||
a = m**2 - n**2
|
||
b = 2 * m * n
|
||
c = m**2 + n**2
|
||
return a, b, c
|
||
|
||
def primitive_triangles(limit: int = 1000) -> dict[int, list] :
|
||
triangle_lengths = {}
|
||
for m, n in generate_pythagorean_triples(limit):
|
||
length = triangle_length(m, n)
|
||
if length not in triangle_lengths:
|
||
triangle_lengths[length] = set()
|
||
a,b,c = get_abc(m, n)
|
||
triangle_lengths[length].add((a, b, c))
|
||
for k in range(2, limit // length + 1) :
|
||
lenp = k * (a + b + c)
|
||
if lenp not in triangle_lengths:
|
||
triangle_lengths[lenp] = set()
|
||
triangle_lengths[lenp].add((a*k, b*k, c*k))
|
||
return triangle_lengths
|
||
|
||
|
||
@timer
|
||
def main():
|
||
max_perimeter = 1000
|
||
triangle_lengths = primitive_triangles(max_perimeter)
|
||
print(triangle_lengths)
|
||
max_length = max(triangle_lengths, key=lambda x: len(triangle_lengths[x]))
|
||
print(f"Max length: {max_length}, Count: {len(triangle_lengths[max_length])}")
|
||
|
||
if __name__ == "__main__":
|
||
main()
|