Python程序：计算指定范围内的勾股三元组

您所在的位置：网站首页 › python计算勾股定理 › Python程序：计算指定范围内的勾股三元组

Python程序：计算指定范围内的勾股三元组

2024-07-15 17:39| 来源: 网络整理| 查看: 265

勾股数是指满足勾股定理 a^2 + b^2 = c^2 的三个正整数 (a, b, c)。其中 a、b、c 两两互质，又称原始勾股数。

在自然数 N 的范围内，找出所有满足勾股定理的三元组 (a, b, c)，即 a^2 + b^2 = c^2，且 a, b, c 均为自然数，并且 a≤b≤c≤N。

思路分析

Python语言编写代码来计算指定范围内的勾股三元组步骤如下：

输入自然数 N 的值。枚举每一个可能的三元组 (a,b,c)，并判断其是否满足勾股定理。输出所有满足勾股定理的三元组 (a,b,c)。基本实现

我们可以根据上述思路基本实现一个 Python 程序，如下所示：

# 输入自然数 N N = int(input()) # 枚举所有可能的三元组 for a in range(1, N+1): for b in range(a, N+1): for c in range(b, N+1): if a * a + b * b == c * c: print(a, b, c)

上面代码使用了三个 for 循环，依次枚举出所有可能的三元组 (a,b,c)，然后判断其是否为勾股数，如果是，则输出其三个正整数 a, b, c 的值。

剪枝优化

在基本实现中，我们使用了三层循环枚举每一个可能的三元组，但是这样做效率比较低。因为大部分枚举都是不必要的，例如当 a = 1 时，枚举 b 的范围应该是 [2,N]，而不是 [1,N]，因为当 b = 1 时，a^2 + b^2 = 1^2 + 1^2，显然不满足勾股定理。

因此，我们可以通过一些剪枝技巧，来减少不必要的枚举。比如，我们可以根据勾股定理，把 c 的上限缩小为 c，即 a^2 + b^2。又由于 a≤b≤c，因此我们可以进一步缩小 a 和 b 的范围，将 b 的上限降到 b，将 a 的上限降到 a。

更新后的 Python 程序如下：

# 输入自然数 N N = int(input()) # 枚举所有可能的三元组 for a in range(1, int((2**0.5)*N)+1): for b in range(a, int((2**0.5)*N)+1): c2 = a*a + b*b c = int(c2**0.5) if c*c == c2 and c n，那么 (a,b,c) 就是勾股数。因此，我们可以在枚举 a,b 时，根据 a=k m^2，b=k n^2，求解出 c 的值，然后再检查 c 是否为正整数，并且是否满足 a, b, c 两两互质。

更新后的 Python 程序如下：

# 输入自然数 N N = int(input()) # 枚举所有可能的三元组 for m in range(2, int((2**0.5)*N)+1): for n in range(1, m): if (m - n) % 2 == 1 and math.gcd(m, n) == 1: k = 1 while k*(m**2+n**2)

【本文地址】

Python程序：计算指定范围内的勾股三元组

Python程序：计算指定范围内的勾股三元组

今日新闻

推荐新闻