Wisselgeld¶
Hoeveel munten?¶
In het eerste college schreef je
exact_change: kun je een bedrag precies betalen met de munten in je
portemonnee? Het antwoord was True of False. In dit werkcollege wil je meer
weten: met hoeveel munten betaal je het bedrag? En met hoeveel munten kan het
minimaal, zodat je portemonnee zo licht mogelijk wordt?
Het gegeven¶
Bedragen en munten zijn in centen, en de munten staan in een lijst. Dezelfde
waarde mag vaker voorkomen: [20, 50, 50] zijn drie munten. Kan een bedrag
niet, dan geeft een functie in dit werkcollege -1 terug. Een aantal munten is
nooit negatief, dus -1 kan geen echt antwoord zijn.
Dit is exact_change uit het college. Beide functies in dit werkcollege hebben
dezelfde basisgevallen en hetzelfde kleinere probleem.
def exact_change(amount, coins):
"""Geeft True als je amount precies kunt betalen met munten uit coins."""
if amount == 0: # basisgeval: alles is betaald
return True
elif amount < 0: # basisgeval: te veel betaald
return False
elif coins == []: # basisgeval: geen munten meer
return False
else: # recursief geval: probeer beide keuzes
use_it = exact_change(amount - coins[0], coins[1:])
lose_it = exact_change(amount, coins[1:])
return use_it or lose_it
Wat je gaat maken¶
Stap |
Functie |
Doet |
Hoe je combineert |
|---|---|---|---|
1 |
|
het aantal munten van de eerste manier die je vindt |
use it als het kan, anders lose it |
2 |
|
het kleinste aantal munten |
het kleinste van use it en lose it |
In beide stappen moet je -1 afvangen voordat je ermee rekent. Kan use it niet,
dan is 1 + -1 geen aantal munten.
Stap 1: num_coins(amount, coins)¶
Geeft het aantal munten waarmee je amount precies betaalt, of -1 als dat niet
kan. Kan het op meer manieren, dan zoek je zo:
Probeer eerst use it: betaal de rest van het bedrag met de rest van de munten. Lukt dat, dan geef je 1 plus dat aantal terug.
Lukt use it niet, dan geef je het antwoord van lose it terug: het hele bedrag met de rest van de munten.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
|
|
Hint
De basisgevallen zijn die van exact_change, met 0 in plaats van True en -1
in plaats van False. Bewaar use it eerst in een variabele, en vraag met if
of die -1 is. Pas als use it niet lukt, doe je de recursieve aanroep voor
lose it.
# jouw oplossing
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)¶
Geeft het kleinste aantal munten waarmee je amount precies betaalt, of -1 als
dat niet kan.
Aanroep |
Resultaat |
|---|---|
|
|
|
|
|
|
|
|
Hint
Nu moet je beide keuzes proberen, zoals bij subset. Reken use it en lose it
allebei uit. Er zijn dan vier gevallen: lukken ze allebei niet, lukt alleen
lose it, lukt alleen use it, of lukken ze allebei? Alleen in het laatste
geval kies je met min het kleinste aantal. Vergeet bij use it de eerste munt
niet mee te tellen.
# jouw oplossing
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
Tot slot¶
Voor 100 cent met de munten [5, 5, 5, 10, 10, 25, 50] vindt num_coins zes
munten, en min_coins vijf. num_coins neemt de eerste manier die lukt, en
probeert daarom alleen lose it als use it niet lukt. min_coins probeert
beide keuzes en vergelijkt ze. Dat is use it or lose it: zoek je het beste
antwoord, dan moet je alle manieren bekijken.
In beide functies betekende -1 dat het niet kon. Zo’n afgesproken waarde moet
je afvangen voordat je ermee rekent. Met min(use_it, lose_it) zonder die
controle zou -1 altijd winnen.