Een probleem beschrijven: invoer, uitvoer en stappen
Voordat je code schrijft, beschrijf je het probleem precies. Dat heet de specificatie.
- Invoer: welke gegevens we krijgen, hun soort en grenzen (bijv. "n hele getallen, 1 ≤ n ≤ 1000").
- Uitvoer: wat we moeten teruggeven (bijv. "het grootste getal").
- Voorwaarden: wat waar is vóór (voorwaarde) en na (nawaarde) het algoritme.
De stappen opschrijven
Een algoritme is een eindige lijst duidelijke stappen die elke geldige invoer omzet in de juiste uitvoer. Je schrijft het op als:
- gewone taal: "Kijk naar elk getal; als het groter is dan het beste tot nu toe, onthoud het."
- een genummerde stappenlijst: 1. beste ← eerste getal. 2. Voor elk volgend getal x: als x > beste, dan beste ← x. 3. Geef beste terug.
- pseudocode of een stroomdiagram als je het nauwkeuriger wilt.
Test het met de hand op kleine invoer, ook op lastige gevallen (alles gelijk, negatieve getallen, maar één getal).
Top-down en bottom-up ontwerpen
Top-down (stapsgewijs verfijnen): begin met de hele taak, knip die in een paar grote stappen en knip elke stap weer op, tot elk deel makkelijk te programmeren is. Voorbeeld: "Maak een rapport" → cijfers inlezen → gemiddelden berekenen → beoordelingen bepalen → afdrukken.
Bottom-up: bouw en test eerst kleine, herbruikbare stukjes (een functie die het maximum vindt, een functie die sorteert) en voeg ze daarna samen tot het hele programma.
In echte projecten gebruik je beide: plannen doe je top-down, bouwen en testen bottom-up.
Verdeel en heers, en de halveringsmethode
Verdeel en heers heeft drie stappen: het probleem splitsen in kleinere delen van dezelfde soort, elk deel oplossen (vaak met recursie) en de antwoorden samenvoegen.
- Binair zoeken (halveren): in een gesorteerde lijst vergelijk je met het midden en gooi je de helft weg. n items kosten ongeveer log₂ n controles: 16 → 4, 1 000 000 → 20.
- Mergesort: splits de lijst in tweeën, sorteer elke helft en voeg ze samen: O(n log n).
- Snel machtsverheffen: a⁸ = ((a²)²)²: 3 vermenigvuldigingen in plaats van 7.
- Een nulpunt vinden met bisectie: halveer een interval waarin de functie van teken wisselt.
Greedy-algoritmen
Een greedy (hebzuchtig) algoritme maakt de keuze die nu het beste lijkt en verandert die nooit meer.
- Wisselgeld met 50, 20, 10, 5, 2, 1: eerst de grootste munt. Optimaal voor dit soort muntstelsel.
- Zoveel mogelijk activiteiten op een dag kiezen: pak steeds de activiteit die het vroegst eindigt. Optimaal.
- Fractionele knapzak: neem eerst de spullen met de beste waarde per kg. Optimaal.
Maar greedy is niet altijd goed: met munten 1, 3, 4 geeft 6 betalen op de greedy manier 4 + 1 + 1 (3 munten), terwijl 3 + 3 maar 2 munten kost. Om een greedy methode te vertrouwen moet je hem bewijzen of testen tegen een methode die zeker klopt.
Dynamisch programmeren en backtracking
Dynamisch programmeren (DP)
Als dezelfde kleinere problemen steeds terugkomen, los je ze één keer op en bewaar je het antwoord in een tabel. Minste munten voor bedrag a: best[a] = 1 + min(best[a - c]) over de munten c ≤ a, beginnend met best[0] = 0. Voor munten 1, 3, 4: best = 0, 1, 2, 1, 1, 2, 2. De tabel van klein naar groot invullen is bottom-up; recursie met een geheugen is top-down (memoisatie). Zie de aparte les over dynamisch programmeren voor meer.
Backtracking
Bouw een oplossing keuze voor keuze op. Als een keuze een regel breekt of in een doodlopend eind belandt, draai je hem terug en probeer je de volgende mogelijkheid. Je gebruikt het voor doolhoven, sudoku, het N-koninginnenprobleem en het opsommen van alle deelverzamelingen. Het is brute kracht met verstand: hele takken die niet kunnen werken sla je over.
Brute kracht
Probeer elk mogelijk antwoord. Altijd juist, maar vaak veel te traag (2ⁿ deelverzamelingen, n! volgordes).
Een techniek kiezen: juistheid, efficiëntie en datastructuren
| Techniek | Gebruik als | Voorbeeld | Typische tijd |
|---|---|---|---|
| Brute kracht | de invoer heel klein is | alle pincodes van 3 cijfers proberen | vaak 2ⁿ of n! |
| Verdeel en heers | de delen onafhankelijk zijn | binair zoeken, mergesort | O(log n), O(n log n) |
| Greedy | een beste lokale keuze bewezen veilig is | activiteitenkeuze, wisselgeld | O(n log n) |
| Dynamisch programmeren | deelproblemen terugkomen | muntenprobleem, kortste paden | grootte van de tabel |
| Backtracking | je zoekt met regels | doolhof, sudoku | exponentieel, maar met snoeien |
Onderbouw je keuze
Juistheid: laat zien dat het algoritme altijd stopt en de juiste uitvoer geeft (een lusinvariant, een bewijs of tests op randgevallen). Efficiëntie: tel de stappen als n groter wordt (grote-O) en vergelijk met andere methoden.
Datastructuren helpen
Arrays voor tabellen (DP), stacks voor backtracking (onthouden waar je naartoe moet terugkeren), queues voor zoeken laag voor laag. Een binaire boom bewaart items zo dat elke knoop hoogstens twee kinderen heeft; in een binaire zoekboom gaan kleinere sleutels naar links en grotere naar rechts, zodat zoeken op elk niveau het werk halveert, net als binair zoeken.
Probeer het: munten en een raadspel
- Speel het raadspel 1-100 met een vriend. Vraag altijd naar het midden. Kun je altijd winnen in 7 vragen? (2⁷ = 128.)
- Schrijf met munten 1, 3, 4 de DP-tabel voor bedragen 0 tot 10 op papier. Waar gaat greedy fout?
- Open de laatste 3D-stap. Probeer munten 1, 7, 10 en bedrag 14. Greedy geeft 10 + 1 + 1 + 1 + 1; DP geeft 7 + 7.
- Schrijf een stappenlijst voor "vind het kleinste getal in een lijst" en test die op 5, 5, 5 en op één getal.
Belangrijke formules en begrippen
- Specificatie = invoer + uitvoer + voorwaarden
- Halveren: ongeveer log₂ n stappen (16 → 4, 1024 → 10)
- Munten-DP: best[0] = 0; best[a] = 1 + min best[a - c]
- Verdeel en heers = splitsen + oplossen + samenvoegen
- Greedy is snel, maar moet bewezen optimaal zijn
Uitgewerkte voorbeelden
1. Schrijf een specificatie en een stappenlijst om het grootste van n getallen te vinden.
Invoer: n ≥ 1 getallen. Uitvoer: het grootste. Stappen: 1. beste ← eerste getal. 2. Voor elk ander getal x: als x > beste, beste ← x. 3. Geef beste terug. Voor 4, 9, 2, 7, 12, 5, 10, 3 is de uitvoer 12 na 7 vergelijkingen.
2. Hoeveel vragen heeft halveren nodig om een getal van 1 tot 1000 te vinden?
Elke vraag halveert het bereik: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Dat zijn 10 vragen (2¹⁰ = 1024 ≥ 1000).
3. Betaal 87 op de greedy manier met munten 50, 20, 10, 5, 2, 1.
50 (37 over), 20 (17), 10 (7), 5 (2), 2 (0): 50 + 20 + 10 + 5 + 2 = 5 munten.
4. Vul de DP-tabel in voor munten 1, 3, 4 tot bedrag 7.
best[0]=0, [1]=1, [2]=2, [3]=1, [4]=1, [5]=min(best4, best2, best1)+1=2, [6]=min(best5, best3, best2)+1=2, [7]=min(best6, best4, best3)+1=2 (3 + 4).
5. Activiteiten (begin-eind): A 9-11, B 10-12, C 11-13, D 12-14, E 13-15. Kies zoveel mogelijk activiteiten die elkaar niet overlappen.
Greedy op vroegste einde: A (eindigt 11), dan C (begint 11, eindigt 13), dan E (begint 13). 3 activiteiten: A, C, E.
6. Plan top-down: een programma dat een klas het gemiddelde cijfer en de beste leerling vertelt.
Niveau 1: gegevens inlezen → berekenen → afdrukken. Niveau 2: namen en cijfers in lijsten inlezen; totaal en gemiddelde berekenen; het hoogste cijfer en de bijbehorende naam vinden; beide afdrukken. Elk stukje wordt daarna bottom-up geprogrammeerd en getest.
Veelgemaakte fouten
- Beginnen met programmeren voordat je invoer en uitvoer hebt beschreven. Veel 'bugs' zijn eigenlijk een onduidelijke specificatie.
- Denken dat greedy altijd optimaal is. Het werkt alleen als je het kunt bewijzen (munten 1, 3, 4 laten het falen).
- Binair zoeken gebruiken op een ongesorteerde lijst. Halveren heeft gesorteerde gegevens nodig.
- DP verwarren met verdeel en heers. DP is voor overlappende deelproblemen die je bewaart; verdeel en heers splitst in onafhankelijke delen.