我如何将此代码优化为运行以获得更大的值？

Question

我正在编写一个 python 函数，该函数将 3 到 200 之间的整数值作为输入，使用等于该数字的唯一非零数字计算总和数并打印输出。例如;将 3 作为输入 1 将被打印，因为只有 1 + 2 会给出 3，将 6 作为输入 3 将被打印，因为 1+2+3、1+5 和 2+4 等于 6。我的代码仅适用于小于 30 的数字，之后它开始变慢。对于 3 到 200 之间的所有输入，如何有效地将我的代码优化为运行。

from itertools import combinations

def solution(n):
    count = 0
    
    max_terms = 0
    num = 0
    for i in range(1,n):
        if num + i <= n:
            max_terms += 1
            num = num + i

    for terms in range(2,max_terms + 1):
        for sample in list(combinations(list(range(1,n)),terms)):
            if sum(sample) == n:
                count += 1

    print(count)

Answer 1

你的问题不够清楚。所以，我在做一些假设...

所以，你想要的是输入一个数字。说 4，然后计算出两个不同数字加起来等于该数字的总组合。如果那是你想要的，那么答案很简单。

对于 4，我们将其视为 'n'。 'n' 有组合 1+3,2+2.

n 为 6，组合为 - 1+5,2+4,3+3。

您可能发现了一个规律。（4 和 6 有一半的组合）同样，对于奇数，它们的组合是之前偶数的一半。即 - 5 有 (4/2)=2 连击。即 1+4,2+3 所以...

获取组合数的公式为 -

(n)/2 - 这是如果你想包括相同数量的组合，如 2+2 为 4，但排除组合为 0。即 0+4 为 4
(n+1)/2 - 如果您想排除带有 0 的组合，即 0+4 代表 4，或者具有相同数字的组合，即 2+2 代表 4。
(n-1)/2 - 此处排除了相同数量的组合。即 2+2 不会算作 n 作为 4 的组合。此外，0 组合，即 0+4 为 4 被排除在外。

n为主号。在这些示例中，它是“4”。仅当 n 是整数并且计算后的这些值存储为整数时，这才有效。 3个数字组合是完全不同的。我敢肯定也有一个公式。

Answer 2

生成所有组合确实不是很有效，因为大多数组合不会加起来 n。

相反，你可以使用一个递归函数，它可以在去掉一个分区（即和的一项）后调用，并将解决剩余数量的问题，给出一个额外的指示，未来的分区应该比刚拍的要大

为了进一步提高效率，可以使用memoization（动态规划）来避免多次解决同一个子问题。

这是代码：

def solution(n, least=1, memo={}):
    if n < least:
        return 0
    key = (n, least)
    if key in memo:  # Use memoization
        return memo[key]
    # Counting the case where n is not partitioned
    #    (But do not count it when it is the original number itself)
    count = int(least > 1)
    # Counting the cases where n is partitioned
    for i in range(least, (n + 1) // 2):
        count += solution(n - i, i + 1)
    memo[key] = count
    return count

使用这些参数测试了代码。评论列出了计算的总和：

print(solution(1)) # none
print(solution(2)) # none
print(solution(3)) # 1+2
print(solution(4)) # 1+3
print(solution(5)) # 1+4, 2+3
print(solution(6)) # 1+2+3, 1+5, 2+4
print(solution(7)) # 1+2+4, 1+6, 2+5, 3+4
print(solution(8)) # 1+2+5, 1+3+4, 1+7, 2+6, 3+5
print(solution(9)) # 1+2+6, 1+3+5, 2+3+4, 1+8, 2+7, 3+6, 4+5
print(solution(10)) # 1+2+3+4, 1+2+7, 1+3+6, 1+4+5, 2+3+5, 1+9, 2+8, 3+7, 4+6

我如何将此代码优化为运行以获得更大的值？

How do i optimize this code to run for larger values?

python

algorithm

loops

itertools

data-structures

我如何将此代码优化为 运行 以获得更大的值？

How do i optimize this code to run for larger values?

python

algorithm

loops

itertools

data-structures

我如何将此代码优化为运行以获得更大的值？