遞歸發生器代碼修正

首先，謝謝任何幫助。我有這個遞歸代碼來計算硬幣列表和給定數量的變化方式。我需要編寫一個遞歸生成器代碼，介紹每次更改金錢迭代的方式。例如，如果你得到的5量和[1,2,3]硬幣的列表，所以這將是輸出：遞歸發生器代碼修正

for e in change_gen(5,[1,2,3]): 
    print(e) 

[1, 1, 1, 1, 1] 
[1, 1, 1, 2] 
[1, 2, 2] 
[1, 1, 3] 
[2, 3]

這是我曾嘗試：了什麼問題？

使用類似於binom和帕斯卡{N \選擇k} =一個algoritem代碼{n-1個\選擇k-1} + {n-1個\選擇k}

def change_gen(amount, coins): 
    if amount == 0: 
     yield [] 
    elif not (amount < 0 or coins == []): 
     g = change_gen(amount, coins[:-1]) 
     f = change_gen(amount - coins[:-1],coins) 
     while True: 
      yield Next(g) 
     yield coins[:-1].extend(next2(f))

來源

2017-06-16 Avri Fridenson

'Next'和'next2'從哪裏來？還要注意'list.extend'返回'None' ...並且它有*是遞歸的嗎？這通常是一個非常適合動態/約束方法的問題。 –

next2是錯誤的。是的，這是一個以遞歸方式編寫的任務。解決方案應該如下所示：def change_gen（amount，coins）： if amount == 0： yield elif not（amount <0 or coins == []）： g = change_gen（amount，coins [： - 1 ]） –

仍然沒有解釋「Next」來自哪裏 - 你可以編輯你的問題以包含這些信息和更正 –

你的遞歸正確：減少硬幣和減少金額。這是一個更正的實現，添加了測試用例。

def change_gen(amount, coins): 
    if amount == 0: 
     yield [] 
    elif amount > 0 and coins: 
     coin = coins.pop() 
     yield from change_gen(amount, coins) 
     coins.append(coin) 
     for lis in change_gen(amount - coin, coins): 
      lis.append(coin) 
      yield lis 

changes = list(change_gen(5, [1,2,3])) 
print(changes) 
assert changes == [ 
[1, 1, 1, 1, 1], 
[1, 1, 1, 2], 
[1, 2, 2], 
[1, 1, 3], 
[2, 3], 
]

斷言通過。

來源

2017-06-17 23:54:20

遞歸發生器代碼修正

回答

相關問題