python - Python 中的正相异求和

Question

此代码为 n=2 提供了错误的输出，而且速度非常慢。

我怎样才能使这段代码更有效地找到尽可能多的正的不同被加数？

TASK- 将给定的正整数 n 表示为尽可能多的成对的总和尽可能不同的正整数。

OUTPUT:第一行包含一个整数 k。第二行包含 k 个不同的正加数，总和为 n.

示例输入:

8

输出:

3

1 2 5

n=int(input())
p=[]
i=1
while(i<=n):
      if (n-i) not in p:
          p.append(i)
      n-=i
      i+=1
print(len(p))
print(*p)

Answer 1

你可以分析地解决问题。如果您要调用的号码是 N ，那么答案永远是

1+2+3+ ... +n + r = N

哪里n是满足 n < r 的最大可能数.例如，取 N=8 ，并考虑 n 的可能值

n   sum(1..n)  r
0       0      8
1       1      7
2     1+2=3    5
3    1+2+3=6   2    // too high, n is not less than r

因此，当N是 8，n是 2 和 r是 5，给出 1+2+5 的答案。

所以问题就变成了，给定 N 的值, 我们如何计算 n .第一步是注意 1 到 n 的总和由等式给出

1+2+3+ ... +n = n(n+1)/2

将其代入第一个等式

n(n+1)/2 + r = N

利用 n < r 的事实，我们可以将其重写为

n(n+1)/2 + n < N

这就是您需要实现的答案。例如，如果 N是 2，则公式为 n < 1这意味着 n是 0 和 r是 2。如果 N是 8，那么 n < 2.77 ，这意味着 n是 2 和 r是 5.