在Python中确定硬币组合

Question

我被要求用Python写一个程序，能够正确找到在给定金额中硬币的组合，以及每种硬币的数量。在这个问题中，只使用五美分和十美分的硬币。

举个例子 - 假设有10个硬币，如何计算出在0.85美元中有多少个五美分和十美分的硬币？

这是我解决这个问题的方法：

1. 建立方程：

   d + n = 10
   0.10d + 0.05n = 0.85

2. 求n的值：
   n = 10 - d

3. 解方程：
   0.10d + 0.05(10-d) = 0.85
   0.05d + 0.5 - 0.05d = 0.85
   0.05d = 0.35
   d = 7
   n = 3

我该如何编写这个程序呢？

抱歉如果这个问题很傻，但我对Python还很陌生，这个问题让我完全迷茫了。

Answer 1

如果你只有十分和五分的硬币，你可以这样做：

>>> total_coins = 10
>>> nickels = 85 / 5  # 85 is the total amount in cents; 5 is the value of a nickel
>>> nickels
17
>>> dimes = 0
>>> while dimes + nickels != total_coins:
...    dimes += 1
...    nickels -= 2
... 
>>> dimes
7
>>> nickels
3
>>>

因为每个十分相当于两个五分，所以你可以先算出有多少个五分，然后每有两个五分就加一个十分，直到你得到正确数量的硬币。

Answer 2

虽然这个方法不太讲究风格，但它很简单，能快速列出所有可能的情况，写起来也很快，实际使用时速度也足够快。你可以先从所有的五分硬币开始，不用一角硬币，然后不断增加一角硬币的数量，同时减少一枚五分硬币，直到找到答案（或者找不到）。

def solve(ncoins, cents):
    nickels = ncoins
    dimes = 0
    for ii in range(ncoins):
        if (nickels * 5) + (dimes * 10) == cents:
            return "{nickels} nickels, {dimes} dimes".format(
                nickels=nickels, dimes=dimes)
        nickels -= 1
        dimes += 1
    raise AssertionError("{ncoins} coins can't be {cents} cents!".format(
        ncoins=ncoins, cents=cents))

print solve(10, 85)
print solve(10, 75)
print solve(100, 75)

输出结果：

3 nickels, 7 dimes
5 nickels, 5 dimes
Traceback (most recent call last):
  File "/home/akg/tmp/sacoins.py", line 16, in <module>
    print solve(100, 75)
  File "/home/akg/tmp/sacoins.py", line 10, in solve
    raise AssertionError("{ncoins} coins can't be {cents} cents!".format(ncoins=ncoins, cents=cents))
AssertionError: 100 coins can't be 75 cents!

Answer 3

假设硬币的数量是 a，那么就有 d + n = a，也就是说，d 和 n 的总和等于硬币的数量。

再假设这些硬币的总金额是 b，那么可以写成 0.1d + 0.05n = b，这表示 d 个 0.1 元硬币和 n 个 0.05 元硬币的总金额。

接下来

n = a - d
0.1d+0.05(a-d)=b
0.05d = b-0.05a
d = 20b - a
n = a - d = a - 20b +a = 2a - 20b

所以，给定 a 和 b：

d = 20b - a
n = a - d

现在我们只需要把这两个公式用 Python 编程实现一下。

可以看看官方文档中的例子：http://docs.python.org/tutorial/controlflow.html#defining-functions

def count(num, total_sum):
    d = 20*total_sum - num
    n = num - d
    return (n,d)

print count(10, 0.85)