Python中積極不同的命令

Question

此代碼給出錯誤的輸出n=2，它非常慢。

我怎樣才能讓這段代碼找到更多有效的不同的正確命令？

TASK - 表示給定的正整數作爲n許多成對 不同的正整數儘可能的總和。

輸出：第一個是包含一個整數k。第二行包含總結到nk正不同的正被加數。

Sample Input:

8

Output:

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

我不知道，如果你的代碼爲O雖然有缺陷，但我可以看到有類似於n = 2的測試用例會導致失敗（例如，我相信n = 9）。嘗試if ((n-i) not in p and n-i != i)。你失敗n = 2，因爲它看到i = 1不在p中，但你正準備投入。

Answer 2

你可以通過分析來解決問題。如果你想達到的數量爲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

Answer 3

一個找到序列方法是有兩個起點：N和M，其中N是我們試圖達到多少並且m從1開始。

接下來，我們將m加1，將它加到序列中並減少N.通過將N減小m並在N < = m * 2時停止達到解。

例如，如果我們試圖達到的數量爲3

N = 3 

然後，

s={} # array to store pairwise distinct positive integers 
k = 3 # k = N at the beginning 
m = 1 # always starts at 1 
m*2 = 2 

因爲

k is not <= m*2 

我們米添加到陣列，從01減去m k，add to m並再次重複相同的過程。

s = {1} 
k = k - m = 3 - 1 = 2 
m = 1 + m = 1 + 1 = 2 

現在，

m*2 = 4 

因爲

k <= m*2 

我們增加ķ我們的陣列，我們正在做。

s = {1, 2} 

這是python中的代碼，它做同樣的事情。

def optimal_summands(n): 

summands = [] # array to store pairwise distinct positive integers 
k = n # marked the upper part 
m = 1 # marked the lower part 

if n == 2 or n == 1: 
    summands.append(n) 
else: 
    for i in range(1,k): 
     if k <= 2*m: 
      summands.append(k) 
      break 
     else: 
      summands.append(m) 
      k = k - m 
      m = m + 1 

return summands