Binary search

Gepost door Adriaan Gijssen op 25 augustus 2017

Algoritmiek is een belangrijk onderdeel van het nieuwe examenprogramma. En wat ons betreft ook een heel leuk en uitdagend onderdeel! De leerlingen maken kennis met een aantal standaardalgoritmen als quicksort [verwijzing naar het blog hierover] en het algoritme van Dijkstra, om een kortste route te vinden.

Ze leren daarbij ook iets over efficiëntie. Maar bepalen hoe efficiënt een algoritme werkt, is best lastig. Toch kun je leerlingen daarover op een eenvoudige manier toch veel leren. Zo gebruiken we het binary searchalgoritme om de leerlingen er kennis mee te laten maken, in de vorm van een raadspelletje.

Het idee van het spelletje is als volgt: Iemand neemt een getal tussen de 1 en de 100 in gedachten. Jij moet raden welk getal dat is. Je mag zo vaak raden als je wilt. Je tegenspeler mag steeds maar één van drie antwoorden geven:

Pogingen: 0

Vragen die hierbij gesteld kunnen worden zijn onder andere:

  1. Welke aanpak kies je om snel het getal te raden? Schrijf dit in het kort op.
  2. Hoe vaak moet je met jouw aanpak maximaal raden om het getal tussen de 1 en de 100 te vinden? Geef een schatting.

De antwoorden van deze vragen geven aanleiding om de begrippen bestcasescenario, worstcasescenario en averagecasescenario uit te leggen.

Bij dit spelletje moet je een getal tussen de 1 en de 100 raden. Stel dat je daarbij alle getallen één voor één opnoemt. Je raadt dan eerst 1, dan 2, dan 3, enzovoort.

Gemiddeld 50 keer raden is erg veel. Er zijn snellere manieren te bedenken om het juiste getal te raden. Bijvoorbeeld:

Voor dit algoritme is het bestcasescenario dat je maar één keer hoeft te raden. Dat gebeurt als je tegenspeler het getal 50 heeft gekozen. In het worstcasescenario vind je het getal in 7 keer raden.

 

-- Share It --