遞歸找到產生指定數量的所有硬幣組合

我提前致歉。我知道，這個問題之前已經被問到了沒有產生我想要/需要的結果的答案。我正在嘗試寫，做在Python3以下功能：遞歸找到產生指定數量的所有硬幣組合

我需要返回產生一定量的方式（硬幣組合）的所有號碼的遞歸函數。這個函數只能包含兩個參數，金額和硬幣。我有困難的時候圍繞遞歸，所以解釋也將不勝感激。謝謝。

這是我目前有：

COINS = dict(
    USA=[100, 50, 25, 10, 5, 1], 
    AUSTRALIA=[200, 100, 50, 20, 10, 5], 
    UK=[500, 200, 100, 50, 20, 10, 5, 2, 1] 
) 

def change(amount, coins): 
    """ 
    >>> change(100, COINS['USA']) 
    293 
    """ 
    if amount < 0: 
     return 0 
    elif amount == 0: 
     return 1 
    else: 
     biggestcoin, *rest = coins[0], coins[1:] 
     return change(amount-biggestcoin, coins) + change(amount, rest)

來源

2012-03-22 sudostack

如果這是家庭作業（我假設它是），請其標記爲此類。如果有很多類似的問題，你的問題又有什麼不同？ – phihag 2012-03-22 01:06:34

嘗試搜索造成問題的更改。維基百科頁面上有很多很好的信息。 – 2012-03-22 01:09:30

聞起來像家庭作業 – inspectorG4dget 2012-03-22 01:14:28

biggestcoin, *rest = coins[0], coins[1:]

你要rest這裏，邏輯地而不是*rest，因爲你必須在每邊兩個項目。在這裏使用*rest會創建一個額外的列表環繞層，然後導致您大概看到的異常。

一旦你解決這個問題：想想，如果你不能讓每個硬幣1所需的量會發生什麼。 change(amount, rest)遞歸調用最終會發生，amount大於零，且rest爲空。你也需要處理這種情況。

來源

2012-03-22 01:17:08

這非常有幫助！ – sudostack 2012-03-22 02:00:03

這是Python 3.x的一個很好的語法，希望。 – Bartek 2012-03-22 03:47:11

讓tuple解包的*語法很好，但是正如前面提到的那樣，這裏實際上並不需要：/ – 2012-03-22 04:12:24

遞歸背後的想法很簡單：

試圖減少問題的大小，每次一個小小的一步。

如果你能做到這一點，你就差不多完成了！從大問題開始，逐漸減小尺寸，直到最終出現一個非常小的問題。無論你喜歡，你都可以解決。

這是如何適用於變更問題？那麼，如果你被要求製作n，你可以通過使用一枚硬幣來減少問題的大小。如果你繼續前進，最終你會得到一個足夠小的問題來解決！

來源

2012-03-22 01:17:35 katrielalex

遞歸找到產生指定數量的所有硬幣組合

回答

相關問題