Wisselgeld¶
Opdracht: Wisselgeld
Stap 1: num_coins(amount, coins)¶
Lose it wordt alleen uitgerekend als use it niet lukt. Bij use it telt de
eerste munt mee: 1 + use_it.
def num_coins(amount, coins):
"""Geeft het aantal munten van de eerste manier om amount te betalen, of -1."""
if amount == 0: # basisgeval: alles is betaald
return 0
elif amount < 0: # basisgeval: te veel betaald
return -1
elif coins == []: # basisgeval: geen munten meer
return -1
use_it = num_coins(amount - coins[0], coins[1:])
if use_it != -1:
return 1 + use_it
else:
return num_coins(amount, coins[1:]) # lose it
assert num_coins(70, [20, 50, 50]) == 2
assert num_coins(100, [5, 5, 5, 10, 10, 25, 50]) == 6
assert num_coins(30, [10, 10, 10, 30]) == 3
assert num_coins(80, [20, 50, 50]) == -1
assert num_coins(0, [5, 5]) == 0
assert num_coins(42, []) == -1
Stap 2: min_coins(amount, coins)¶
Lukt maar één van de twee keuzes, dan is dat het antwoord. Lukken ze allebei,
dan kiest min het kleinste aantal. Lukken ze geen van beide, dan is lose_it
gelijk aan -1, en dat geeft de eerste tak terug.
def min_coins(amount, coins):
"""Geeft het kleinste aantal munten waarmee je amount betaalt, of -1."""
if amount == 0: # basisgeval: alles is betaald
return 0
elif amount < 0: # basisgeval: te veel betaald
return -1
elif coins == []: # basisgeval: geen munten meer
return -1
use_it = min_coins(amount - coins[0], coins[1:])
lose_it = min_coins(amount, coins[1:])
if use_it == -1:
return lose_it
elif lose_it == -1:
return 1 + use_it
else:
return min(1 + use_it, lose_it)
assert min_coins(70, [20, 50, 50]) == 2
assert min_coins(100, [5, 5, 5, 10, 10, 25, 50]) == 5
assert min_coins(30, [10, 10, 10, 30]) == 1
assert min_coins(40, [20, 10, 10, 20]) == 2
assert min_coins(80, [20, 50, 50]) == -1
assert min_coins(0, [5, 5]) == 0
assert min_coins(42, []) == -1