python - 给定总和的毕达哥拉斯三元组
问题描述
如果它等于输入,则以下代码打印毕达哥拉斯三元组,但问题是像 90,000 这样的大数需要很长时间才能回答。我可以做些什么来优化以下代码?1 ≤ n ≤ 90 000
def pythagoreanTriplet(n):
# Considering triplets in
# sorted order. The value
# of first element in sorted
# triplet can be at-most n/3.
for i in range(1, int(n / 3) + 1):
# The value of second element
# must be less than equal to n/2
for j in range(i + 1,
int(n / 2) + 1):
k = n - i - j
if (i * i + j * j == k * k):
print(i, ", ", j, ", ",
k, sep="")
return
print("Impossible")
# Driver Code
vorodi = int(input())
pythagoreanTriplet(vorodi)
解决方案
您的源代码对解决方案进行了蛮力搜索,因此速度很慢。
更快的代码
def solve_pythagorean_triplets(n):
" Solves for triplets whose sum equals n "
solutions = []
for a in range(1, n):
denom = 2*(n-a)
num = 2*a**2 + n**2 - 2*n*a
if denom > 0 and num % denom == 0:
c = num // denom
b = n - a - c
if b > a:
solutions.append((a, b, c))
return solutions
操作码
修改了 OP 代码,因此它返回所有解决方案,而不是打印第一个找到的解决方案来比较性能
def pythagoreanTriplet(n):
# Considering triplets in
# sorted order. The value
# of first element in sorted
# triplet can be at-most n/3.
results = []
for i in range(1, int(n / 3) + 1):
# The value of second element
# must be less than equal to n/2
for j in range(i + 1,
int(n / 2) + 1):
k = n - i - j
if (i * i + j * j == k * k):
results.append((i, j, k))
return results
定时
n pythagoreanTriplet (OP Code) solve_pythagorean_triplets (new)
900 0.084 seconds 0.039 seconds
5000 3.130 seconds 0.012 seconds
90000 Timed out after several minutes 0.430 seconds
解释
函数solve_pythagorean_triplets
是 O(n) 算法,其工作原理如下。
正在寻找:
a^2 + b^2 = c^2 (triplet) a + b + c = n (sum equals input)
通过搜索 a 来求解(即迭代的固定值)。有了固定值,我们有两个方程和两个未知数 (b, c):
b + c = n - a c^2 - b^2 = a^2
解决方案是:
denom = 2*(n-a) num = 2*a**2 + n**2 - 2*n*a if denom > 0 and num % denom == 0: c = num // denom b = n - a - c if b > a: (a, b, c) # is a solution
迭代 range(1, n) 以获得不同的解决方案
推荐阅读
- java - Java 序列化对象为空
- c# - 编译的绑定 (x:Bind) 是否需要 ViewModel 从 DependencyObject 派生?
- r - 在 R 中的聚类分析中过滤变量
- python-3.x - Imageio 无法以正确的帧速率读取网络摄像头
- apache-nifi - NiFi中触发了FetchFolder?
- r - r - calculate using next non-na value in data frame column
- php - 如何从数组中删除特定值的多个实例
- jquery - 当我在 MVC 应用程序中请求 ajax 数据时,为什么我的模态部分视图为空?
- dart - 如何向 TabBar 添加缺口以在其中放置 FloatingActionButton
- java - 从 Hibernate 捕获生成的 SQL