中级农民
- 积分
- 153
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2014-7-9
- 最后登录
- 1970-1-1
|
- def make_change(amount, coins):
- """Return a list of coins that sum to amount, preferring the smallest coins
- available and placing the smallest coins first in the returned list.
- The coins argument is a dictionary with keys that are positive integer
- denominations and values that are positive integer coin counts.
- >>> make_change(2, {2: 1})
- [2]
- >>> make_change(2, {1: 2, 2: 1})
- [1, 1]
- >>> make_change(4, {1: 2, 2: 1})
- [1, 1, 2]
- >>> make_change(4, {2: 1}) == None
- True
- >>> coins = {2: 2, 3: 2, 4: 3, 5: 1}
- >>> make_change(4, coins)
- [2, 2]
- >>> make_change(8, coins)
- [2, 2, 4]
- >>> make_change(25, coins)
- [2, 3, 3, 4, 4, 4, 5]
- >>> coins[8] = 1
- >>> make_change(25, coins)
- [2, 2, 4, 4, 5, 8]
- """
- if not coins:
- return None
- smallest = min(coins)
- rest = remove_one(coins, smallest)
- "*** YOUR CODE HERE ***"
- if amount == smallest:
- return [smallest]
- lst = make_change(amount - smallest, rest)
- if lst:
- return [smallest] + lst
- else:
- return make_change(amount, rest)
- def remove_one(coins, coin):
- """Remove one coin from a dictionary of coins. Return a new dictionary,
- leaving the original dictionary coins unchanged.
- >>> coins = {2: 5, 3: 2, 6: 1}
- >>> remove_one(coins, 2) == {2: 4, 3: 2, 6: 1}
- True
- >>> remove_one(coins, 6) == {2: 5, 3: 2}
- True
- >>> coins == {2: 5, 3: 2, 6: 1} # Unchanged
- True
- """
- copy = dict(coins)
- count = copy.pop(coin) - 1
- if count:
- copy[coin] = count
- return copy
- class ChangeMachine:
- """A change machine holds a certain number of coins, initially all pennies.
- The change method adds a single coin of some denomination X and returns a
- list of coins that sums to X. The machine prefers to return the smallest
- coins available. The total value in the machine never changes, and it can
- always make change for any coin (perhaps by returning the coin passed in).
- The coins attribute is a dictionary with keys that are positive integer
- denominations and values that are positive integer coin counts.
- >>> m = ChangeMachine(2)
- >>> m.coins == {1: 2}
- True
- >>> m.change(2)
- [1, 1]
- >>> m.coins == {2: 1}
- True
- >>> m.change(2)
- [2]
- >>> m.coins == {2: 1}
- True
- >>> m.change(3)
- [3]
- >>> m.coins == {2: 1}
- True
- >>> m = ChangeMachine(10) # 10 pennies
- >>> m.coins == {1: 10}
- True
- >>> m.change(5) # takes a nickel & returns 5 pennies
- [1, 1, 1, 1, 1]
- >>> m.coins == {1: 5, 5: 1} # 5 pennies & a nickel remain
- True
- >>> m.change(3)
- [1, 1, 1]
- >>> m.coins == {1: 2, 3: 1, 5: 1}
- True
- >>> m.change(2)
- [1, 1]
- >>> m.change(2) # not enough 1's remaining; return a 2
- [2]
- >>> m.coins == {2: 1, 3: 1, 5: 1}
- True
- >>> m.change(8) # cannot use the 2 to make 8, so use 3 & 5
- [3, 5]
- >>> m.coins == {2: 1, 8: 1}
- True
- >>> m.change(1) # return the penny passed in (it's the smallest)
- [1]
- >>> m.change(9) # return the 9 passed in (no change possible)
- [9]
- >>> m.coins == {2: 1, 8: 1}
- True
- >>> m.change(10)
- [2, 8]
- >>> m.coins == {10: 1}
- True
- >>> m = ChangeMachine(9)
- >>> [m.change(k) for k in [2, 2, 3]]
- [[1, 1], [1, 1], [1, 1, 1]]
- >>> m.coins == {1: 2, 2: 2, 3: 1}
- True
- >>> m.change(5) # Prefers [1, 1, 3] to [1, 2, 2] (more pennies)
- [1, 1, 3]
- >>> m.change(7)
- [2, 5]
- >>> m.coins == {2: 1, 7: 1}
- True
- """
- def __init__(self, pennies):
- self.coins = {1: pennies}
- def change(self, coin):
- """Return change for coin, removing the result from self.coins."""
- "*** YOUR CODE HERE ***"
- self.coins[coin] = 1 + self.coins.get(coin, 0)
- result = make_change(coin, self.coins)
- for coin in result:
- count = self.coins.pop(coin) - 1
- if count:
- self.coins[coin] = count
- return result
复制代码 |
|