我已经编写了这个代码,但它非常冗长:
for i in range(n + 1):
for j in range(n + 1):
for k in range(n + 1):
if i + j + k == n:
有没有一种聪明的方法使它运行更快?目前它是O(n^3),这相当不理想。
我已经编写了这个代码,但它非常冗长:
for i in range(n + 1):
for j in range(n + 1):
for k in range(n + 1):
if i + j + k == n:
有没有一种聪明的方法使它运行更快?目前它是O(n^3),这相当不理想。
有几种可能的解决方法 - 实际上不需要在所有解决方法中循环到N,而最后一个数字是完全免费的。
请记住,三元组中的所有数字必须为正数(否则答案为无限大)。
If permutations are not included (i.e. (1,2,3)
is the same triplet as (3,2,1)
), going from smallest to largest:
def iter_triplets(n):
# This is the smallest number, can't be more than 1/3 of n
for i in range(0, n//3 + 1):
sum_left = n-i
# This is the second smallest, can't be more than 1/2 of the sum_left or less than the first by definition
for j in range(i, sum_left//2 + 1):
yield (i, j, sum_left-j) # Last number is calculated.
>>> list(iter_triplets(6))
[(0, 0, 6), (0, 1, 5), (0, 2, 4), (0, 3, 3), (1, 1, 4), (1, 2, 3), (2, 2, 2)]
>>> list(iter_triplets(10))
[(0, 0, 10), (0, 1, 9), (0, 2, 8), (0, 3, 7), (0, 4, 6), (0, 5, 5), (1, 1, 8), (1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 2, 6), (2, 3, 5), (2, 4, 4), (3, 3, 4)]
If permutations are not included (i.e. (1,2,3)
is the same triplet as (3,2,1)
), going from largest to smallest:
import math
def iter_triplets(n):
# This is the biggest number, can't be less than 1/3 of n
for i in range(n, math.ceil(n/3) - 1, -1):
sum_left = n-i
# This is the second biggest number, can't be less than 1/2 of the sum_left and more than first number by definition.
# ceil to correct rounding errors.
for j in range(min(sum_left, i), math.ceil((sum_left)/2) - 1, -1):
yield (i, j, sum_left-j) # Last number is calculated.
>>> list(iter_triplets(10))
[(10, 0, 0), (9, 1, 0), (8, 2, 0), (8, 1, 1), (7, 3, 0), (7, 2, 1), (6, 4, 0), (6, 3, 1), (6, 2, 2), (5, 5, 0), (5, 4, 1), (5, 3, 2), (4, 4, 2), (4, 3, 3)]
If permutations are included (i.e. (1,2,3)
is a different triplet than (3,2,1)
), going from smallest to largest:
def iter_triplet_permutations(n):
for i in range(0, n+1):
sum_left = n-i
for j in range(0, sum_left+1):
yield (i, j, sum_left-j)
>>> list(iter_triplet_permutations(5))
[(0, 0, 5), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 4, 1), (0, 5, 0), (1, 0, 4), (1, 1, 3), (1, 2, 2), (1, 3, 1), (1, 4, 0), (2, 0, 3), (2, 1, 2), (2, 2, 1), (2, 3, 0), (3, 0, 2), (3, 1, 1), (3, 2, 0), (4, 0, 1), (4, 1, 0), (5, 0, 0)]
由于一旦你有了i
和j
,最内层循环似乎是多余的,因为k
是自带的:
for i in range(n + 1):
for j in range(n + 1):
if i+j <= n:
print((i, j, n-i-j))
n
,那么也许可以这样做:for i in range(n + 1):
for j in range(i, (n - i)//2 + 1):
out.append((i, j, n-i-j))
有几种方法可以让代码运行更快。
使用列表推导式。语法为[条件 循环返回值]
从上一个循环结束的地方开始下一个循环,以避免重复。
def MakeTriplet(n):
return [(i,j,k) for i in range(0,n+1) for j in range(i,n+1) for k in range(j,n+1) if (i+j+k)==n]
k=n-j-i
并去掉最内层循环,可以轻松将此算法优化到O(n^2)
。 - Nelewoutn
,因此,不,你不能对最坏情况运行时间做太多事情。 - chepner(n,j,-j)
是任何j
值的解),因此您不能指望明确找到它们所有。 - Stef