我想計算A = [2, 1, 1, 4]總和為的陣列子集的數量2。有 2 種方式：(A[0])和(A[1], A[2])。我的計算代碼是：
def W(number, index):
A = [2, 1, 1, 4]
if number < 0 or index < 0:
return 0
elif number==0:
return 1
else:
return W(number, index-1) W(number - A[index], index)
現在，當我用 呼叫函式時W(2,3)，得到4的是 2 而不是 2。我的問題是我的代碼還計算了(A[1], A[1])和的可能性(A[2], A[2])。有沒有辦法在仍然使用遞回的同時修復它？
uj5u.com熱心網友回復：
呼叫W(number - A[index], index)應該是W(number - A[index], index - 1)；否則，您允許在子集總和中重復計算一個元素。
這是解決此問題的代碼片段。對于每個元素，我們決定是否將其添加到我們的總和中。如果元素允許我們的 target 到達0，我們將添加1到我們的可能性總數中，然后遞回查看是否有任何其他方法可以在不添加我們當前正在檢查的元素的情況下到達目標：
A = [2, 1, 1, 4]
def W(number, index):
if number < 0 or index < 0 :
return 0
elif number - A[index] == 0:
return 1 W(number, index - 1)
else:
return W(number, index - 1) W(number - A[index], index - 1)
print(W(1, 3)) # Prints 2
uj5u.com熱心網友回復：
此代碼似乎適用于總和為 1..8 的情況：
A = [2, 1, 1, 4]
def W(number, index):
if number == 0:
return 1
elif number < 0 or index < 0:
return 0
else:
return W(number, index-1) W(number - A[index], index - 1)
測驗用例：
print(W(1, 3))
print(W(2, 3))
print(W(3, 3))
print(W(4, 3))
print(W(5, 3))
print(W(6, 3))
print(W(7, 3))
print(W(8, 3))
輸出
2
2
2
2
2
2
2
1
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/431326.html
上一篇：記憶遞回呼叫時的巨大效率差異
下一篇：在javascript中使用filter()來實作curriable()是可行的，但是，uisngmap()是可行的，為什么？