遞歸解決方案？

Question

問題：我們有3種硬幣（1美元，2美元，5美元），我們將有這些硬幣的混合物，以賺取1000美元;我們想要 使用這些硬幣創建1000美元的所有可能方法的數量，並且我們還需要打印每種可能的方式

我剛纔寫下面的代碼爲非遞歸風格的硬幣問題，它是好好工作。 現在我需要WITE做同樣的事情遞歸函數，但我只是想不出 我的遞歸function.any的想法基本情況寫一個遞歸函數？

i=0 
for x in range(1001): 
    for y in range(501): 
    for z in range(201): 
     if x + 2*y + 5*z == 1000: 
      print(" {} coin $1 , {} coin $2 , {} coin $5".format(x,y,z)) 
      i+=1 
print("number of possibilities",i) 

Answer 1

我真的懷疑遞歸是否是做這件事的最佳方法。動態編程將永遠適合這類任務。這是一個遞歸代碼。

def counts(x, y, z): 
    if(x + y + z > 1000): 
     return 

    if x + y + z == 1000: 
     print(" {} coin $1 , {} coin $2 , {} coin $5".format(x,y/2,z/5)) 

    counts(x+1, y, z) 
    counts(x, y+2, z) 
    counts(x, y, z+5) 


counts(1, 2, 5) 

Answer 2

你有三個基本情況：

• 如果貨幣創造的總金額等於你只有一個方法來創建這個和0。
• 如果創建的總金額小於0，則無法創建總和 - 所以有0種方法。
• 如果有0種硬幣，你不能從它們中得到任何金額，所以有0種方法。

如果您需要解決這一問題的遞歸方法的深入解釋，你可以在「計算機程序的結構與解釋：」讀它（我在我的母語讀它，這樣我就可以」 t指向確切的頁面 - 它必須位於名爲「遞歸」的部分中）。

Answer 3

AGA已經上市的基礎情況，但稱SICP怎麼辦遞歸（據說一個很好的書 - 我還沒有看過，雖然我警告你，我做知道它的目標計劃 - 一個Lisp方言）。

基本上，你需要爲每個遞歸步驟做的是......你

1. 檢查是否已經到了一個基本情況。如果是，請確定您是否找到了有效的解決方案，並根據需要輸出解決方案。無論哪種方式，返回（回溯）尋找更多的解決方案。

2. 否則，依次選擇每一個可能的硬幣型，更新彙總，使遞歸調用每一個。

你會通過爲每個呼叫必須的總數包括每個硬幣值的數量，並且還可以包括總價值到目前爲止（雖然你同樣可以計算出，當您需要它）。

僞...

def recursive_solution (totals) : 
    if found_a_base_case : 
    if its_a_valid_solution_base_case : 
     output solution 
    else 
    derive totals for adding another $5 
    recursive_solution (those_new_totals) 

    derive totals for adding another $2 
    recursive_solution (those_new_totals) 

    derive totals for adding another $1 
    recursive_solution (those_new_totals) 

正如我在評論中提到的，這會做大量的重複勞動 - 一個副作用是，它往往會多次找到每個解決方案。爲了防止這種情況，你需要記住你已經找到的解決方案。如果您還記得您已經嘗試過的部分解決方案，並使用它來避免重新開展這項工作，這就是所謂的記憶。

Answer 4

這是一個簡單的解決方案。但它會產生重複的解決方案。動態規劃仍然可以更好地解決問題。

>>> def coins(total, coins1=0, coins2=0, coins5=0): 
...  if total == 0: 
...    print "%s 1$, %s 2$, %s 5$" % (coins1, coins2, coins5) 
...    return 
...  if total < 0: 
...    return 
...  coins(total - 1, coins1 + 1, coins2, coins5) 
...  coins(total - 2, coins1, coins2 + 1, coins5) 
...  coins(total - 5, coins1, coins2, coins5 + 1) 
... 
>>> coins(1000) 

Answer 5

試試這個：

def changes(amount, coins): 
    possibilities = [0] * (amount + 1) 
    possibilities[0] = 1 
    for coin in coins: 
     for j in range(coin, amount + 1): 
      possibilities[j] += possibilities[j - coin] 
    return possibilities[amount] 

print(changes(1000, [1,2,5])) 
#50401 

Answer 6

這裏是一個遞歸和動態的方式。請選擇：

def dynamic(tgt,coins): 
    combos = [1]+[0]*tgt 
    for coin in coins: 
     for i in range(coin, tgt+1): 
      combos[i] += combos[i-coin] 
    return combos[tgt]   

def recursive(tgt,coins): 
    if coins==[1]: return 1 
    coin = coins.pop() 
    return sum(recursive(tgt%coin + coin*n, coins[:]) for n in range(tgt//coin+1)) 

print(dynamic(1000,[1,2,5])) 
# 50401 
print(recursive(1000,[1,2,5])) 
# 50401