找到所有三元組i,j,k使得i j k=n-有解無憂

我已經對此進行了編碼，但這很長：

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) ，這很可悲。

uj5u.com熱心網友回復：

有一些可能的解決方案 - 你實際上不需要在所有這些中回圈直到 N ，最后一個數字完全免費。

請記住，三元組中的所有數字都必須是正數（否則答案是無限的）。

如果不包括排列（即(1,2,3)與相同的三元組(3,2,1)），則從最小到最大：

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)]

如果不包括排列（即(1,2,3)與相同的三元組(3,2,1)），則從最大到最小：

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)]

如果包括排列（即(1,2,3)與不同的三元組(3,2,1)），則從最小到最大：

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)]

uj5u.com熱心網友回復：

最里面的回圈似乎是多余的，因為一旦你有了iand 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))

uj5u.com熱心網友回復：

有幾種方法可以使代碼運行得更快。

使用串列推導。語法 [ReturnThing ForLoops 條件]

從前一個回圈到達的位置開始每個回圈。這樣可以避免重復

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]

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/421564.html

標籤：

上一篇：使用np.linalg.solve在numpy中求解具有2個未知數和3個方程的線性方程

下一篇：嫌 OSS 查詢太慢？看我們如何將速度提升 10 倍！