首頁猿問如果給出一些美元價值，如何找到所有...

如果給出一些美元價值，如何找到所有硬幣組合

源碼算法與數據結構

慕蓋茨4494581 2019-08-29 09:10:56

如果給出一些美元價值，如何找到所有硬幣組合幾個月前，我找到了一段代碼，我正在編寫面試。根據我的評論，它試圖解決這個問題：給定一美分的美分價值（例如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

TA貢獻1797條經驗獲得超6個贊

我很久以前就研究了這個問題，你可以讀一下我的小文章。這是Mathematica的來源。

通過使用生成函數，您可以獲得問題的封閉形式的恒定時間解決方案。格雷厄姆，克努特和帕塔什尼克的混凝土數學就是這本書的書，并且對這個問題進行了相當廣泛的討論?；旧?，您定義了一個多項式，其中第n個系數是以n美元進行更改的方式的數量。

這篇文章的第4-5頁顯示了如何使用Mathematica（或任何其他方便的計算機代數系統）在三行代碼中在幾秒內計算10 ^ 10 ^ 6美元的答案。

（而且這已經很久以前在75Mhz Pentium上只有幾秒鐘......）

反對回復 2019-08-29

DIEA

TA貢獻1820條經驗獲得超3個贊

注意：這僅顯示方式的數量。

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

TA貢獻1876條經驗獲得超7個贊

我贊成遞歸解決方案。你有一些面額列表，如果最小的面額可以平均分配任何剩余的貨幣金額，這應該工作正常。

基本上，您從最大面額移動到最小面額。
遞歸，

您有一個當前總數要填充，以及一個最大面額（剩下超過1個）。如果只剩下1個面額，那么只有一種方法可以填補總數。您可以使用當前面額的0到k個副本，使得k * cur面額<=總計。
對于0到k，使用修改的總計和新的最大面額調用函數。
將結果從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 關注
711 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

如果給出一些美元價值，如何找到所有硬幣組合

如果給出一些美元價值，如何找到所有硬幣組合

3 回答

添加回答

如果給出一些美元價值，如何找到所有硬幣組合

如果給出一些美元價值，如何找到所有硬幣組合