我需要總和為 1000的三個正整數的每個組合。這是我的嘗試，但我不確定這是否正確，因為我無法驗證它。def getSum(): l = [] for x in range(1, 999): total = 1000-x for y in range(1, 999): total = total-y if total>0: l.append([x, y, total]) return lprint len(getSum())我得到 28776 種不同的組合。那是對的嗎？
3 回答
慕尼黑的夜晚無繁華
TA貢獻1864條經驗 獲得超6個贊
由于1+998+1和1+1+998是不一樣的東西，也有組合的一些不可思議的量：
這一行可以生成它們：
[(i, 1000-i-k, k) for i in range(1,999) for k in range(1,1000-i)]
結果：
[...
(1, 4, 995),
(1, 3, 996),
(1, 2, 997),
(1, 1, 998),
(2, 997, 1),
(2, 996, 2),
...]
這個列表的長度是：
498501
交互式愛情
TA貢獻1712條經驗 獲得超3個贊
不，那個數字不正確。您的代碼的問題是這一行：
total = total-y
在這里，您嘗試的total每個值都越來越小y，永遠不要將其重置為減去后的值x。要修復它，請創(chuàng)建一個新變量，例如total2，并在內部循環(huán)中使用它。
total2 = total-y
這樣，您就可以獲得498501組合。此外，您可以break盡快從內部循環(huán)total2 < 0。
如果您只需要組合的數量：請注意，存在將N-1兩個數字相加到的組合N，例如對于N==4: 1+3, 2+2, 3+1（假設您考慮1+3和3+1不同）。您可以將此擴展到三個數字的情況，將數字分成兩部分兩次。這樣，您只需要一個循環(huán)。這可以進一步簡化為 O(1) 公式。
示例，使用天真的方法product作為參考：
>>> N = 100 # to make reference faster
>>> sum(1 for t in product(range(1, N+1), repeat=3) if sum(t)==N)
4851
>>> sum(N-1-i for i in range(1, N-1))
4851
>>> ((N-2)*(N-1))//2
4851
當然，也適用于N = 1000（或更大，更大）：
>>> N = 1000
>>> sum(N-1-i for i in range(1, N-1))
498501
>>> ((N-2)*(N-1))//2
498501
qq_花開花謝_0
TA貢獻1835條經驗 獲得超7個贊
如果你處理 [1,1,998] 和 [1,998,1] 相同（沒有唯一的整數）：
def getSum():
l = []
for x in range(1, 999):
total = 1000-x
for y in range(1, 999):
total = total-y
if total>0:
z = [x, y, total]
z.sort()
if z not in l:
l.append(z)
return l
a = getSum()
print(len(a))
如果你想要 3 個唯一的整數：
def getSum():
l = []
for x in range(1, 999):
total = 1000-x
for y in range(1, 999):
total = total-y
if total>0:
z = [x, y, total]
z.sort()
if (z not in l) and (not((len(set(z)) < len(z)))):
l.append(z)
return l
a = getSum()
print(len(a))
否則你的代碼（在我的意義上）沒問題。我還沒有檢查你的答案...
編輯：我用野蠻的力量檢查過它。如果您以不同的方式處理 (1,1,998) 和 (998,1,1)，則正確答案實際上是 498501。目前不知道為什么...
添加回答
舉報
0/150
提交
取消