遞歸 - Python硬幣組合列表

-4

我目前正在嘗試編寫一些代碼，給定一個硬幣值列表，將返回所有可能的硬幣總和合計值。這裏有一個程序應該如何運行的例子：遞歸 - Python硬幣組合列表

>>> find_changes(4,[1,2,3]) 
[[1, 1, 1, 1], [2, 1, 1], [1, 2, 1], [3, 1], [1, 1, 2], [2, 2], [1, 3]]

我得到了下面的代碼模板填寫：

def find_changes(n, coins): 
    if n < 0: 
     return [] 
    if n == 0: 
     return [[]] 
    all_changes = [] 

    for last_used_coin in coins: 
     ### DELETE THE "pass" LINE AND WRITE YOUR CODE HERE 
     pass 

    return all_changes

我使用for循環內的以下代碼嘗試：

all_changes.append[last_used_coin] 
find_changes(n-last_used_coin,coins)

目前無法使用。我究竟做錯了什麼？

來源

2013-11-14 user2928714

什麼是它應該做的？出了什麼問題？家庭作業需要更多的努力... – sdasdadas

是的，我知道，它應該返回給我們所有可能的組合列表的列表，我是新的Python遞歸，所以..... – user2928714

你應該先數字瞭解你的基本情況，然後弄清楚如何將問題分解成更小的子問題。如果這很難（因爲這不是最簡單的遞歸問題），首先嚐試解決像斐波那契遞歸這樣的問題。 – sdasdadas

您的回答很接近，但由於語法錯誤和邏輯錯誤的組合而失敗。

記住，append是一個方法調用 - 你想添加一組括號周圍的支架，像這樣：

all_changes.append([last_used_coin]) 
# Add a list of one element to the `all_changes` list

但是，你的代碼還沒有做相當的工作。讓我們試着挑選代碼。

如果我們看看您的for循環，它會遍歷列表中的每一枚硬幣。您採取了正確的下一步 - 您通過您的線路find_changes(n - last_used_coin, coins)找到了所有可能的硬幣組合n - last_used_coin。

現在，您需要做的就是遍歷所有可能的硬幣組合，從調用find_changes開始，在last_used_coin上重新添加，並將所有內容附加到all_changes列表中。

這裏的決賽中，工作代碼：

def find_changes(n, coins): 
    if n < 0: 
     return [] 
    if n == 0: 
     return [[]] 
    all_changes = [] 

    for last_used_coin in coins: 
     combos = find_changes(n - last_used_coin, coins) 
     for combo in combos: 
      combo.append(last_used_coin) 
      all_changes.append(combo) 

    return all_changes 

print find_changes(4, [1,2,3])

來源

2013-11-14 18:05:50 Michael0x2a

非常感謝Michael，我非常感謝！ – user2928714

儘管我完全理解如何將其應用於數學遞歸定義，但它需要時間來適應遞歸思維。 – user2928714

存在一個問題，輸出爲：[[[[[[1]，1]，1]，[[2] ，[1]，[1]，1]，[[[1]，1]，[[1]，1]，[[2]，1] 1]，[1]，[1]，[1]，[[1]，[[1]，[[2] ，[1]，1]，[[[1]，2]，1]，[[3]，1]]，[[[[1]，1]，[1]，[[2]，1 ] [1,1,1]，[[[1]，1]，1]，[[2]，1]，1,1]，[[[1]，2]，1]，[[3]， 1]，[[1]]，[[[1]，1]，[[2]，1]，[1] ] [1]，[1]，[2]，1]，[[3]，1]]，[[[1]，2] [[[1]，1]，2]，[[2]，2]]，[[[1]，3]]] – user2928714

遞歸 - Python硬幣組合列表

回答

相關問題