递归解决方案？

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