Het probleem: eieren laten vallen

👀 Voorbeeld - Eieren breken

Eieren zijn kwetsbaar en breken snel, maar hoe snel? Je doet een experiment: je kan een ei laten vallen van 1 cm, 2 cm of 3 cm hoogte. Je wil uitzoeken vanaf welke hoogte eieren breken en je beschikt over 2 eieren.

Dit weet je:

• Alle eieren breken op dezelfde hoogte.
• Als een ei breekt op een bepaalde hoogte, dan breekt het ook op elke grotere hoogte.
• Als je een ei laat vallen en het breekt niet, dan kan je het ook opnieuw gebruiken.

Aanpak 1 - Een slechte strategie ❌

Begin bij 3 cm:

• Ei 1 valt van 3 cm → breekt 💥
• Ei 2 valt van 2 cm → breekt 💥
• Je hebt geen antwoord: je weet niet of eieren ook bij 1 cm breken!

❗ Opgelet

Als je al je eieren kwijt bent vóór je een definitief antwoord hebt, is je experiment mislukt. Je moet je eieren slim inzetten!

Aanpak 2 - De voorzichtige strategie ✅ (maar niet optimaal)

Begin bij de laagste hoogte en werk omhoog:

1. Ei 1 valt van 1 cm → breekt niet → gebruik opnieuw
2. Ei 1 valt van 2 cm → breekt niet → gebruik opnieuw
3. Ei 1 valt van 3 cm → breekt 💥 → antwoord: eieren breken bij 3 cm

Dit werkt, maar in het slechtste geval heb je 3 pogingen nodig. Kan het slimmer?

Aanpak 3 - Brute Force: alle mogelijkheden overlopen

We kunnen alle mogelijke strategieën uitschrijven en de beste kiezen. Dat is de Brute Force-aanpak.

👀 Alle mogelijkheden uitgewerkt

Kies de strategie met het kleinste aantal pogingen in het slechtste geval:

---

Strategie A - Begin bij 1 cm:

• Ei valt van 1 cm → breekt: antwoord na 1 poging ✅
• Ei valt van 1 cm → breekt niet:
  • Ei valt van 2 cm → breekt: antwoord na 2 pogingen ✅
  • Ei valt van 2 cm → breekt niet:
    • Ei valt van 3 cm → breekt: antwoord na 3 pogingen
    • Ei valt van 3 cm → breekt niet: antwoord na 3 pogingen

→ Slechtste geval: 3 pogingen

---

Strategie B - Begin bij 2 cm:

• Ei valt van 2 cm → breekt:
  • Ei valt van 1 cm → breekt: antwoord na 2 pogingen ✅
  • Ei valt van 1 cm → breekt niet: antwoord na 2 pogingen ✅
• Ei valt van 2 cm → breekt niet:
  • Ei valt van 3 cm → breekt: antwoord na 2 pogingen ✅
  • Ei valt van 3 cm → breekt niet: antwoord na 2 pogingen ✅

→ Slechtste geval: 2 pogingen 🏆

---

Strategie C - Begin bij 3 cm:

• Ei valt van 3 cm → breekt:
  • Ei valt van 1 cm → breekt: antwoord na 2 pogingen ✅
  • Ei valt van 1 cm → breekt niet:
    • Ei valt van 2 cm → breekt: antwoord na 3 pogingen
    • Ei valt van 2 cm → breekt niet: antwoord na 3 pogingen
• Ei valt van 3 cm → breekt niet: antwoord na 1 poging ✅

→ Slechtste geval: 3 pogingen

Conclusie: Strategie B (begin bij 2 cm) heeft in het slechtste geval slechts 2 pogingen nodig. Maar, oef, wat een werk om dit allemaal uit te schrijven! Stel je voor wat er gebeurt bij 15 cm hoogte en 3 eieren…

🤔 Huh? - Brute kracht is duidelijk niet alles

Naarmate het probleem groter wordt, wordt de lijst van mogelijkheden exponentieel langer. Er moet een slimmere aanpak bestaan!

Aanpak 4 - Memoisatie: slim hergebruiken 💡

Als je de Brute Force-boom goed bekijkt, zie je dat hetzelfde deelprobleem meerdere keren voorkomt. Bijvoorbeeld: “je hebt nog 2 eieren en 1 hoogte te testen” komt op twee verschillende plaatsen in de boom voor.

👀 Hergebruik van resultaten

Wat telt in dit probleem zijn twee dingen:

• Het aantal eieren dat je nog hebt
• De grootte van het bereik waarbinnen je nog zoekt

Als je voor een bepaalde combinatie van (aantal eieren, bereik) al weet wat het minimale aantal pogingen is, moet je dat niet opnieuw berekenen — je kan het gewoon hergebruiken!

❗ Begrip - Memoisatie

Memoisatie is een techniek waarbij je een eerder berekend resultaat onthoudt en hergebruikt, zodat je hetzelfde rekenwerk niet twee keer hoeft te doen.

Als de zoekruimte groter wordt, loopt het werk dat je uitspaart met memoisatie flink op.