<p>真正的诀窍是知道,因为每一枚硬币至少值下一个较小面额<a href="https://en.wikipedia.org/wiki/Change-making_problem#Greedy_method" rel="nofollow">you can use a greedy algorithm</a>的两倍。剩下的只是实现细节。</p>
<p>这里有一个稍显枯燥(但可能,呃,更令人困惑)的实现。我真正做的不同之处在于使用一个列表来存储我的结果,并利用<a href="https://docs.python.org/release/1.5.1p1/tut/tuples.html" rel="nofollow">tuple unpacking</a>和<a href="https://docs.python.org/3/library/functions.html#divmod" rel="nofollow">divmod</a>。而且,这在将来更容易扩展:我只需要将<code>coins</code>更改为<code>[100, 25, 10, 5, 1]</code>,就可以支持$1账单。等等。</p>
<pre><code>coins = [25,10,5,1] #values of possible coins, in descending order
results = [0]*len(coins) #doing this and not appends to make tuple unpacking work
initial_change = int(input('Change to make: ')) #use raw_input for python2
remaining_change = initial_change
for index, coin in enumerate(coins):
results[index], remaining_change = divmod(remaining_change, coin)
print("In order to make change for %d cents:" % initial_change)
for amount, coin in zip(results, coins):
print(" %d %d cent piece(s)" % (amount, coin))
</code></pre>
<p>给你:</p>
<pre><code>Change to make: 99
In order to make change for 99 cents:
3 25 cent piece(s)
2 10 cent piece(s)
0 5 cent piece(s)
4 1 cent piece(s)
</code></pre>