为了账号安全,请及时绑定邮箱和手机立即绑定

如果给出一些美元价值,如何找到所有硬币组合

/ 猿问

如果给出一些美元价值,如何找到所有硬币组合

如果给出一些美元价值,如何找到所有硬币组合

几个月前,我找到了一段代码,我正在编写面试。

根据我的评论,它试图解决这个问题:

给定一美分的美分价值(例如200 = 2美元,1000 = 10美元),找到构成美元价值的所有硬币组合。只有便士(1¢),镍(5¢),角钱(10¢)和四分之一(25¢)。

例如,如果给出100,答案应该是:

4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies  3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies  etc.

我相信这可以通过迭代和递归方式解决。我的递归解决方案非常错误,我想知道其他人如何解决这个问题。这个问题的难点在于尽可能提高效率。


查看完整描述

3 回答

?
FFIVE

我很久以前就研究了这个问题,你可以读一下我的小文章。这是Mathematica的来源

通过使用生成函数,您可以获得问题的封闭形式的恒定时间解决方案。格雷厄姆,克努特和帕塔什尼克的混凝土数学就是这本书的书,并且对这个问题进行了相当广泛的讨论。基本上,您定义了一个多项式,其中第n个系数是以n美元进行更改的方式的数量。

这篇文章的第4-5页显示了如何使用Mathematica(或任何其他方便的计算机代数系统)在三行代码中在几秒内计算10 ^ 10 ^ 6美元的答案。

(而且这已经很久以前在75Mhz Pentium上只有几秒钟......)


查看完整回答
反对 2019-08-29
?
DIEA

注意:这仅显示方式的数量。

Scala功能:

def countChange(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (coins.isEmpty || money < 0) 0
  else countChange(money - coins.head, coins) + countChange(money, coins.tail)


查看完整回答
反对 2019-08-29
?
幕布斯6054654

我赞成递归解决方案。你有一些面额列表,如果最小的面额可以平均分配任何剩余的货币金额,这应该工作正常。

基本上,您从最大面额移动到最小面额。
递归,

  1. 您有一个当前总数要填充,以及一个最大面额(剩下超过1个)。如果只剩下1个面额,那么只有一种方法可以填补总数。您可以使用当前面额的0到k个副本,使得k * cur面额<=总计。

  2. 对于0到k,使用修改的总计和新的最大面额调用函数。

  3. 将结果从0添加到k。这就是你可以用多少种方式从目前的面额中填补总数。返回此号码。

这是我所说的问题的python版本,200美分。我得到了1463种方式。此版本打印所有组合和最终计数总数。

#!/usr/bin/python# find the number of ways to reach a total with the given number of combinationscents = 200denominations = [25, 10, 5, 1]names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}def count_combs(left, i, comb, add):
    if add: comb.append(add)
    if left == 0 or (i+1) == len(denominations):
        if (i+1) == len(denominations) and left > 0:
           if left % denominations[i]:
               return 0
           comb.append( (left/denominations[i], demoninations[i]) )
           i += 1
        while i < len(denominations):
            comb.append( (0, denominations[i]) )
            i += 1
        print(" ".join("%d %s" % (n,names[c]) for (n,c) in comb))
        return 1
    cur = denominations[i]
    return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))count_combs(cents, 0, [], None)


查看完整回答
反对 2019-08-29
  • 3 回答
  • 0 关注
  • 241 浏览

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信