这个赋值的目的是找出和一个数n之和的最大数,这样这些数是唯一的。例如,如果n=8,我们从l=1开始,然后从n中减去1得到7,然后尝试l=2给出k=5,但是我们停止了,因为这个数的一些不同的和是前一个列表的成员。所以我尝试实现一个迭代的方法。我已经尝试过递归方法,但它达到了最大递归深度,因为n<;=10^9。我实际上在这里尝试一种递归方法来检查k的不同和是否在列表summand中,但这不起作用。对于n=85的输入,其输出为[1,84],而正确的输出是[1,2,3,4,5,6,7,8,9,10,11,19]。我错过了什么?提前谢谢。在
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
这应该可以做到:
相关问题 更多 >
编程相关推荐