06D: Design, Debugging en Donuts

In deze les geven we je suggesties hoe je het ontwerpen van programma's en het corrigeren van fouten gemakkelijker kunt maken. Hoe langer je programmeert, des te vaardiger je zult worden in het vermijden en verbeteren van fouten. Maar nu willen we je wat algemene nuttige adviezen geven. We zullen de volgende technieken bespreken:

  • splits en schrijf je programma in delen
  • los enkele voorbeelden op met pen en papier
  • maak een plan voor dat je het programma gaat schrijven
  • schrijf het programma
  • test het programma met de voorbeelden die je op papier hebt uitgewerkt
  • test met extra voorbeelden inclusief "grensgevallen" en willekeurig gekozen gevallen

Deze magische formule zal niet alles automatisch oplossen, maar het kan je hoofdpijn besparen en je behoeden voor aantal problemen die je anders later moet oplossen.

Wanneer je een probleem tegenkomt, dan kun je om de fouten te herstellen print opdrachten gebruiken om er achter te komen waar de fout zit (we zullen dat verderop in deze les toepassen), de visualizer gebruiken, het geschreven programma nauwkeurig nalezen, en goede tests schrijven. Wanneer je Python thuis uitvoert, kun je breakpoints en step tools gebruiken om meer inzicht te krijgen wat er mis gaat.

Een algoritme bestaat uit een rij opdrachten. Terwijl een computer-programma geschreven moet worden in een speciale taal zoals Python of JavaScript, geeft een algoritme  de stap-voor-stap instructies weer die ook in het Nederlands kunnen worden geschreven of in een diagram tot uiting kunnen worden gebracht. Zo is een recept voor donuts een algoritme, waarbij  "neem drie kopjes bloem" een stap is, en "laat het deeg twee uur rijzen" een andere stap is. We zullen in deze les een eenvoudig algoritme ontwikkelen. Daarna zullen we het algoritme implementeren, dat wil zeggen omzetten in een werkend computer programma.

Opgave: Donutkosten berekenen

Tim Horton, die een keten van koffie shops bezit in Canada, verkoopt timbits, zeer smakelijke donuts:

Foto: looking_and_learning, flickr

Je moet de komende week meerdere feestjes organiseren, en je wilt verschillende aantallen timbits bestellen voor elk feestje. Je wilt daarom een programma schrijven dat in staat is de prijs van een willekeurig aantal timbits te bepalen, zodat je de kosten kunt berekenen. De prijzen zijn als volgt

Aantal Prijs
1 $0.20
10 (kleine doos) $1.99
20 (medium doos $3.39
40 (grote doos) $6.19

Schrijf een programma, het ene deel na het andere

Naar we aannemen, wil je een programma schrijven waarbij de invoer bestaat uit het aantal mensen P aanwezig op het feestje en de uitvoer is wat het feestje kost inclusief BTW. Op het hoogste niveau, zijn er drie deelprogramma's:

  1. bereken voor P mensen, wat het aantal timbits T is dat je moet kopen?
  2. bereken de prijs van precies T timbits
  3. bereken de BTW en daarna de totale kosten.

Je kunt echter elk van de drie delen één voor één schrijven. We bevelen ten zeerste aan dat je één deel schrijft, het test en verbetert voordat je aan het volgende deel begint, omdat hoe groter je programma is, des te moeilijker het zal zijn om een fout te vinden en die te herstellen. Het is gemakkelijker om de drie delen van het programma apart te testen, voor dat je ze combineert tot één geheel. Voor de rest van deze les zullen we ons focussen op stap 2: de prijs bepalen van precies T timbits.

Een paar voorbeelden handmatig oplossen

Om een computer te kunnen vertellen om iets te doen, moet je in staat zijn het zelf te doen. Laten we zelf een voorbeeld doorwerken: wat is de prijs van precies 45 timbits? Kijken we naar de grootte van de dozen, dan kunnen we één grote doos kopen met (40) timbits, met een prijs van $6.19. Daarna is het nodig om 45 – 40 = 5 losse timbits te kopen die dan 5 * $0.20 = $1.00 kosten. De totale prijs is dan $6.19 + $1.00 = $7.19.

Maak een plan voor je programma voordat je het gaat schrijven

Maar wat wanneer we 4 timbits willen kopen of 456 in plaats van 45? In het algemeen dienen we zoveel mogelijk grote dozen kopen als maar mogelijk is, en daarna zonodig een medium doos en/of een kleine doos en/of losse timbits om het juiste aantal te krijgen.  

Is dit algoritme echt het beste? Ja! Je kunt zien dat het kopen van twee medium dozen (2*$3.39 = $6.78) geen goed idee is omdat 2*20=40 timbits in één grote doos goedkoper is. Zo maakt een vergelijking van losse timbits tegenover een kleine doos en een kleine doos tegenover een medium doos duidelijk dat het algoritme de laagste prijs oplevert om welk aantal timbits dan ook te kopen. Wanneer de prijzen anders waren, zouden we wellicht voorzichtiger moeten zijn.

We gaven aan dat je je programma moet structureren voor dat je het schrijft. Je kunt

  • een korte stap voor stap beschrijving geven van het algoritme in gewoon Nederlands in plaats van in Python.
  • een diagram gebruiken of stroomschema om de stappen te laten zien.
  • focus  op de algemene lijnen in plaats van op de details, althans in het begin.

In het volgende voorbeeld geven we je een stap voor stap beschrijving in het Nederlands. We zullen geen stroomschema geven voor dit programma omdat voor dit programma dat zou bestaan uit een stroomschema met stappen onder elkaar van stap 1 naar stap 2 enz. Alles in een rechte lijn. Bij programma's met een loop, zoals we die later zullen tegenkomen, hebben we meer aan een stroomschema. 

Algoritme om de prijs te berekenen van een willekeurig aantal timbits

  1. leg het aantal timbits vast via invoer
  2. houdt de totale kosten bij, begin met nul
  3. koop zoveel mogelijk grote dozen als je kunt
    1. bereken het aantal timbits dat je nog steeds nodig hebt
    2. update de totale kosten
  4. koop een medium doos wanneer dat mogelijk is en herhaal de stappen A en B.
  5. koop een kleine doos wanneer dat mogelijk is en herhaal de stappen A en B.
  6. koop losse timbits en herhaal stap B.
  7. voer de totale kosten uit

We noemen dit een beschrijving van het algoritme in  pseudocode , omdat het uit  een rij instructies bestaat, stap voor stap weergegeven, maar niet in een echte programmeertaal.

Schrijf het programma

We roepen het eerste advies in herinnering, schrijf je programma deel voor deel  je kunt daarbij denken aan het het schrijven van een apart stukje code voor elk van de stappen 1 tot en met 7. Verder moeten wij bij elk van de stappen nagaan welke variabelen we zullen gebruiken. Welke namen krijgen ze en wat is hun beginwaarde?

Laten we timbitsLeft gebruiken om het aantal timbits vast te leggen die we nog moeten kopen, en laten we totalCost gebruiken om de totale kosten tot zover vast te leggen. We hoeven in Python niet vooraf het type vast  te leggen, maar we kunnen inzien dat timbitsLeft een int zal zijn, terwijl totalCost een  float variabele zal zijn waarmee de totale kosten in dollars is vastgelegd . (Dus is een dollarcent 0.01). We zullen nog enkele extra tijdelijke variabelen bij elke stap nodig hebben, maar dat zullen we bekijken op het moment dat we ze nodig hebben.

Stap 1 en 2 kunnen geschreven worden door middel van een regel per stap:

timbitsLeft = int(input()) # stap 1: leg de invoer vast
totalCost = 0              # stap 2: initialiseer de totale kosten
In Stap 3 dienen we het maximaal aantal grote dozen te berekenen dat we  kunnen kopen. Hoe kunnen we dat doen? Omdat een grote doos 40 timbits bevat, zal het aantal bigBoxes gelijk zijn aan het  integer quotient van timbitsLeft gedeeld door 40. Door de deling, de kosten en het verschil bij te houden krijgen we het volgende programma deel:

# stap 3: koop zoveel mogelijke grote dozen
bigBoxes = timbitsLeft / 40
totalCost = totalCost + bigBoxes * 6.19    # pas de totale prijs aan
timbitsLeft = timbitsLeft - 40 * bigBoxes  # bereken het aantal timbits dat we nog nodig hebben
Eigenlijk, zo blijkt,  hebben we al een fout gemaakt. De beste manier om een fout te ontdekken is je programma zo vroeg mogelijk (en ook vaak) te testen!  Laten we daarom dit deel van het programma testen. We zullen een paar print opdrachten toevoegen om de werking tot hier te kunnen  bekijken. (In plaats van print opdrachten te gebruiken, kun je ook de visualizer gebruiken om elke stap te checken.)

Voorbeeld
Test het programma  tot zover met als invoer 45, en gebruik daarbij een print opdracht om het verbeteren te vergemakkelijken.

Dat werkt niet zoals we dat willen! Wat is het probleem?  Waar staat de eerste regel, waarin iets gebeurt, dat we zo niet bedoeld hebben? Probeer die te vinden voordat je naar de volgende paragraaf gaat. Denk eraan dat we dit voorbeeld eerder met de hand hebben opgelost.

Klik om de uitleg te openen
De oorzaak van het probleem zit in de regel met bigBoxes = timbitsLeft / 40, omdat bigBoxes gelijk is aan 1.125, terwijl we de waarde 1 gewenst was. Je kunt immers geen deel van een doos kopen. Een mogelijke uitweg, die je in hoofdstuk 7A zult zien, is het gebruik van // (geheeltallig-delen) in plaats van / (decimaal delen). Een andere oplossing, gebaseerd op wat we in Les 4 zagen, is timbitsLeft / 40 te vertalen naar een geheel getal via (int) waardoor we de cijfers achter de komma weghalen. We zullen deze aanpak gebruiken: de regel wordt bigBoxes = int(timbitsLeft / 40).

Stappen 4 en 5 lijken op stap 3. Als alternatief, omdat je hoogstens één medium doos en hoogstens één kleine doos koopt, kunnen we een if opdracht gebruiken:

if timbitsLeft >= 20: # stap 4, kunnen we een medium doos kopen?
  totalCost = totalCost + 3.39
  timbitsLeft = timbitsLeft - 20
if timbitsLeft >= 10: # stap 5, kunnen we een kleine doos kopen?
  totalCost = totalCost + 1.99
  timbitsLeft = timbitsLeft - 20
Tot slot, moeten we 20 centen betalen voor elk van de overgebleven timbits en  het antwoord weergeven.

totalCost = totalCost + timbitsLeft * 20 # stap 6
print(totalCost)                         # stap 7

Test met de voorbeelden die je met de hand hebt opgelost

Hier is het volledige programma. Het eerste wat we zullen doen, is de test of het werkt met invoer 45 dat we met pen en papier hebben opgelost.

Voorbeeld
Wat kosten 45 timbits?
Type de invoer voor je programma hieronder in.

Er moet ergens iets fout zijn omdat we meer dan 100 dollar betalen voor maar 45 timbits! Je laatste opdracht is om deze fout te vinden en te verbeteren, en ook nog een andere fout die in het programma zit. Het zal worden getest in de volgende les.

Je dient nog te weten dat er iets bijzonders is met de prijzen van Tim Horton, maar dat is geen fout: het kan goedkoper door T+1 timbits te kopen in plaats van precies T timbits. Bijvoorbeeld, 19 timbits kosten $3.79, terwijl 20 timbits maar $3.39 kosten. Niettemin zullen we vast houden aan de opdracht om precies T timbits te kopen en wel zo goedkoop mogelijk. Hiervoor is het algoritme, zoals eerder uitgelegd, correct. Dus dient je programma 3.79 als uitvoer te geven bij een invoer van 19.

Test met nog meer voorbeelden

In Computer Science Circles, proberen we je programma intelligent en geautomatiseerd te testen om er zeker van te zijn dat je het probleem correct hebt opgelost. Maar in een echte programmeersituatie, is het aan jou om je programma zorgvuldig te testen. Hier volgen een paar nuttige tips om je programma te testen.

  • Je kunt nagaan of iedere regel van je programma correct werkt. In het timbit probleem, zal bij gebruik van de invoer 10 worden getest of we goed omgaan met kleine dozen. Op dezelfde manier zullen we met invoer 20 en 40 testen of medium en grote dozen correct worden afgehandeld. Tot slot dien je na te gaan of enkelvoudige timbits juist worden afgehandeld (bv. met  een invoer van 1).
    • Dit kan helpen om na te gaan of waarden zoals $3.39 en $1.99 correct zijn ingevoerd.
  • Ga in ieder geval "grensgevallen" na, die je programma tot het uiterste dwingen. Zo is bijvoorbeeld de kleinste invoer bij dit programma 0, omdat je niet een negatief aantal timbits kunt hebben. Ons programma heeft geen grootste invoer, maar je zou waarden kunnen proberen zoals 39 en 41 die dicht bij de grens liggen om slechts één grote doos te kopen.
    • Dit kan helpen om na te gaan dat je niet per ongeluk > hebt ingetypt in plaats van >=.
  • In sommige gevallen kun je automatisch elke invoer testen, of een groot aantal  random invoer om na te gaan of je programma correct werkt. We gebruiken bij  CS Circles  vaak random invoer bij het testen. Gebruik je import random bij het begin van je programma dan zal met random.randint(10, 100) een random geheel getal tussen 10 end 100 worden gegenereerd.

Kun je beide fouten opsporen en alle testen doorstaan? Probeer het!

Programmeeroefening: Timbits
Verbeter de fouten en doorsta alle testen!
Type de invoer voor je programma hieronder in.

Nog steeds hongerig? Dan ben je klaar om verder te gaan met de volgende les!

Terwijl  je met 10 timbits een doos kunt vullen, maken 8 timbits één  timbyte. Photo: thisisbrianfisher, flickr