遞歸解決方案？

問題：我們有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)

來源

2013-12-15 Soheil

在每次遞歸時，您都會從要生成的總數中減去要添加到混合物中的硬幣的值。基本情況是當總數爲0. – Barmar

對於非遞歸解決方案，您不需要'z'循環。計算'ZZ = 1000-（X + 2 * Y）'，並檢查是否zz''是由5整除如果是這樣，則必須以Z = ZZ/5'的溶液。 – Steve314

BTW - 遞歸解決方案將受益於記憶化，或者你可以使用表格/動態規劃的選擇 - 無論哪種方式，以改善不考慮不同的方式來達到同樣的硬幣計數的性能 - 顯然，如果你選擇，然後A $ 1 $ 2 ，這相當於選擇了2美元，然後是1美元。如果你不知道memoization或動態編程，但不要擔心。 – Steve314

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

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)

來源

2013-12-15 16:25:29

你有三個基本情況：

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

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

來源

2013-12-15 15:03:44 aga

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

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

檢查是否已經到了一個基本情況。如果是，請確定您是否找到了有效的解決方案，並根據需要輸出解決方案。無論哪種方式，返回（回溯）尋找更多的解決方案。
否則，依次選擇每一個可能的硬幣型，更新彙總，使遞歸調用每一個。

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

僞...

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)

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

來源

2013-12-15 15:25:29 Steve314

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

>>> 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)

來源

2013-12-15 16:17:49

試試這個：

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

來源

2013-12-15 16:31:38

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

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

來源

2013-12-15 18:40:38 dawg

遞歸解決方案？

回答

相關問題