如何计算代表n美分的方法数量

我正在研究以下算法，并想知道我的实现是否正确：

给定无穷多的四分之一，硬币，镍币和硬币，编写代码来计算代表n分的方式的数量

这没有记忆：

def count_ways(n) return 0 if n < 0 return 1 if n == 0 count_ways(n-25) + count_ways(n-5) + count_ways(n-10) + count_ways(n-1) end 

Answer 1

我们可以很容易地看到您的代码是否正确。 让我们尝试换一毛钱。 有四种方式：1角钱，2个镍币，1个镍和5个便士，10个便士，但count_ways(10) #=> 9 。

您可以使用递归按如下方式执行此操作。

码

 def count_ways(cents, coins) if coins.size == 1 return (cents % coins.first) == 0 ? [cents/coins.first] : nil end coin, *remaining_coins = coins (0..cents/coin).each_with_object([]) { |n, arr| count_ways(cents-n*coin, remaining_coins).each { |a| arr << [n, *a] } } end 

例子

 coins = [25, 10, 5, 1] count_ways(32, coins) #=> [[0, 0, 0, 32], [0, 0, 1, 27], [0, 0, 2, 22], [0, 0, 3, 17], [0, 0, 4, 12], # [0, 0, 5, 7], [0, 0, 6, 2], [0, 1, 0, 22], [0, 1, 1, 17], [0, 1, 2, 12], # [0, 1, 3, 7], [0, 1, 4, 2], [0, 2, 0, 12], [0, 2, 1, 7], [0, 2, 2, 2], # [0, 3, 0, 2], [1, 0, 0, 7], [1, 0, 1, 2]] count_ways(100, coins) #=> [[0, 0, 0, 100], [0, 0, 1, 95], [0, 0, 2, 90], [0, 0, 3, 85], [0, 0, 4, 80], # [0, 0, 5, 75], [0, 0, 6, 70], [0, 0, 7, 65], [0, 0, 8, 60], [0, 0, 9, 55], # ... # [3, 1, 2, 5], [3, 1, 3, 0], [3, 2, 0, 5], [3, 2, 1, 0], [4, 0, 0, 0]] count_ways(100, coins).size #=> 242 

说明

显示递归如何工作的最好方法是使用puts语句对代码进行加密，然后针对一个简单示例运行它。

 INDENT = 8 @indentation = 0 def indent @indentation += INDENT end def undent @indentation = [@indentation-INDENT, 0].max end def ind ' '*@indentation end 

 def count_ways(cents, coins) puts "#{ind}** entering count_ways with cents=#{cents}, coins=#{coins}" if coins.size == 1 puts "#{ind}<< returning [cents]=#{[cents]} as coins.size == 1" undent end return [cents] if coins.size == 1 coin, *remaining_coins = coins puts "#{ind}coin=#{coin}. remaining_coins=#{remaining_coins}" puts "#{ind}0..cents/coin=#{0..cents/coin}" arr = (0..cents/coin).each_with_object([]) do |n, arr| puts "#{ind} n=#{n}, arr=#{arr}" puts "#{ind} >> calling count_ways(#{cents}-#{n}*#{coin}, remaining_coins)" indent aa = count_ways(cents-n*coin, remaining_coins) puts "#{ind} aa=#{aa}" aa.each do |a| arr << [n, *a] puts "#{ind} arr << [#{n}, *#{a}], arr=#{arr}" end puts "#{ind} after all coins, arr=#{arr}" end puts "#{ind}<< returning arr=#{arr}" undent arr end 

现在让我们运行count_ways(12, coins) ，这应该返回4种方式进行12美分的变化： [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] count_ways(12, coins) [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] count_ways(12, coins) [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] count_ways(12, coins) [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] 。

 count_ways(12, coins) ** entering count_ways with cents=12, coins=[25, 10, 5, 1] coin=25. remaining_coins=[10, 5, 1] 0..cents/coin=0..0 n=0, arr=[] >> calling count_ways(12-0*25, remaining_coins) ** entering count_ways with cents=12, coins=[10, 5, 1] coin=10. remaining_coins=[5, 1] 0..cents/coin=0..1 n=0, arr=[] >> calling count_ways(12-0*10, remaining_coins) ** entering count_ways with cents=12, coins=[5, 1] coin=5. remaining_coins=[1] 0..cents/coin=0..2 n=0, arr=[] >> calling count_ways(12-0*5, remaining_coins) ** entering count_ways with cents=12, coins=[1] << returning [cents]=[12] as coins.size == 1 

  aa=[12] arr << [0, *12], arr=[[0, 12]] after all coins, arr=[[0, 12]] n=1, arr=[[0, 12]] >> calling count_ways(12-1*5, remaining_coins) ** entering count_ways with cents=7, coins=[1] << returning [cents]=[7] as coins.size == 1 aa=[7] arr << [1, *7], arr=[[0, 12], [1, 7]] after all coins, arr=[[0, 12], [1, 7]] n=2, arr=[[0, 12], [1, 7]] >> calling count_ways(12-2*5, remaining_coins) ** entering count_ways with cents=2, coins=[1] << returning [cents]=[2] as coins.size == 1 

  aa=[2] arr << [2, *2], arr=[[0, 12], [1, 7], [2, 2]] after all coins, arr=[[0, 12], [1, 7], [2, 2]] << returning arr=[[0, 12], [1, 7], [2, 2]] aa=[[0, 12], [1, 7], [2, 2]] arr << [0, *[0, 12]], arr=[[0, 0, 12]] arr << [0, *[1, 7]], arr=[[0, 0, 12], [0, 1, 7]] arr << [0, *[2, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]] after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]] n=1, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2]] >> calling count_ways(12-1*10, remaining_coins) ** entering count_ways with cents=2, coins=[5, 1] coin=5. remaining_coins=[1] 0..cents/coin=0..0 n=0, arr=[] >> calling count_ways(2-0*5, remaining_coins) ** entering count_ways with cents=2, coins=[1] << returning [cents]=[2] as coins.size == 1 

  aa=[2] arr << [0, *2], arr=[[0, 2]] after all coins, arr=[[0, 2]] << returning arr=[[0, 2]] aa=[[0, 2]] arr << [1, *[0, 2]], arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]] after all coins, arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]] << returning arr=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]] aa=[[0, 0, 12], [0, 1, 7], [0, 2, 2], [1, 0, 2]] arr << [0, *[0, 0, 12]], arr=[[0, 0, 0, 12]] arr << [0, *[0, 1, 7]], arr=[[0, 0, 0, 12], [0, 0, 1, 7]] arr << [0, *[0, 2, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2]] arr << [0, *[1, 0, 2]], arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] after all coins, arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] << returning arr=[[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] => [[0, 0, 0, 12], [0, 0, 1, 7], [0, 0, 2, 2], [0, 1, 0, 2]] 

Answer 2

不，你将是重复计算的解决方案，因为你可以首先选择一个四分之一，然后是一角硬币或其他方式，但这些解决方案基本相同。

防止重复计算的最简单方法是确保你从不挑选比你已经选择的硬币更大的硬币。

在代码中：

 def count_ways(n, max_coin) return 0 if n < 0 return 1 if n == 0 result = count_ways(n-1, 1) result = result + count_ways(n- 5, 5) if max_coin >= 5 result = result + count_ways(n-10, 10) if max_coin >= 10 result = result + count_ways(n-25, 25) if max_coin >= 25 result end 

并将其称为25作为初始最大硬币

Answer 3

硬币的顺序并不重要，所以coins.min在这种情况下不会帮助你 – 这是过于复杂的事情。

首先，我们必须建立一种关于硬币种类与计数变化量之间关系的直觉

使用n种硬币改变金额a方法n等于

• 使用除第一种硬币以外的所有硬币改变数量的方法的数量加上
• 使用所有n种硬币改变金额a − d的方法的数量，其中d是第一种硬币的面额。

_{来源： SICP第1.2章}

 ### change_coins :: (Int, [Int]) -> Int def change_coins amount, (x,*xs) if amount == 0 1 elsif amount < 0 or x.nil? 0 else change_coins(amount, xs) + change_coins(amount - x, [x,*xs]) end end change_coins 11, [1, 2, 5] # => 11 change_coins 2, [3] # => 0 change_coins 100, [1, 5, 10, 25, 50] # => 292 

明智的回报价值

例如，在这个问题中，如果金额的任何组合都无法弥补金额，我们必须返回-1。

-1案件是愚蠢的。 只使用3美分硬币就有零改变2美分的方法; 因此我们返回0 。

如果你真的必须返回-1 ，只需使用一个愚蠢的包装器

 def cc amount, xs count = change_coins amount, xs if count == 0 then -1 else count end end 

订单无关紧要

 change_coins 11, [5, 1, 2] # => 11 change_coins 2, [3] # => 0 change_coins 100, [50, 1, 25, 10, 5] # => 292