如何计算表示n美分的方式数

Question

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

给定无穷多的硬币、一角硬币、五分硬币和便士，编写代码来计算表示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

硬币的顺序无关紧要，所以硬币。min在这种情况下帮不了你——事情太复杂了。

首先我们必须对硬币的种类和要计算的变化量之间的关系有一种直觉

使用n不同种类的硬币来更改金额的方法的数量等于

• 使用除第一种硬币外的所有硬币加上
• 更改金额的方法的数量a− d使用所有n种硬币，其中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

Answer 2

我们可以很容易地看出您的代码是否正确。让我们试着换一角钱。有四种方法：一角硬币，两个五分镍币，一个五分镍币和五个一分镍币，还有十个一分镍币，然而count_方法（10）#=

您可以使用递归执行如下操作。

密码

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\u ways（12，coins），它应该返回对12美分进行更改的四种方式：[[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 3

不，你将是重复计算的解决方案，因为你可以先选择一个25美分的硬币，然后选择一个10美分的硬币，或者相反，但是这些解决方案基本上是相同的。

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

代码：

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作为初始最大硬币