此分配的目的是找到总和为n的最大数字数,以使这些数字唯一。例如,如果n = 8,我们从l = 1开始,然后从n减去1得到7,然后尝试l = 2,得出k = 5,但是随后我们停止了,因为该数字的某些明显的和是前一个的成员清单。因此,我正在尝试实现一种迭代方法。我已经尝试过递归方法,但是由于n
def optimalSummandsIter(n):
'''
The goal of this problem is to represent
a given positive integer n as a sum of as many pairwise
distinct positive integers as possible.
In the first line, output the maximum number k such that n can be represented as a sum
of k pairwise distinct positive integers.
In the second line, output k pairwise distinct positive integers
that sum up to n (if there are many such representations, output any of them).
Initially we have k = n and l = 1.
To solve a (k, l)-subproblem, we do the following.
If k ≤ 2l, we output just one summand k.
Otherwise we output l and then solve the subproblem (k − l, l + 1)
'''
summands = []
k = n
l = 1
m = sum(summands)
if k <= 2*l:
summands.append(k)
return summands
while k > 0:
if any(i in optimalSummandsIter(k) for i in summands):
summands.append(k)
return summands
else:
summands.append(l)
k -= l
l += 1
return summands
最佳答案
这应该可以解决问题:
def optimalSummandsIter(n):
summands = []
k = n
l = 1
while k > 0:
if k <= l*2:
summands.append(k)
return summands
summands.append(l)
k -= l
l += 1
optimalSummandsIter(8) --> [1,2,5]
optimalSummandsIter(85) --> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 19]