AlgoI (09-10): reeks 1
Algoritmen I (2009-2010)
reeks 1: het Josephus-probleem
Algemene uitleg en demonstraties vind je
hier
of
hier.
Opdracht
Gegeven een kring van n personen, genummerd van 1 tot n, waaruit telkens de k-de persoon
geëlimineerd wordt. Welk nummer blijft laatst over?
Voorbeeld: voor n=10 en k=2 worden achtereenvolgens geëliminieerd: 2, 4, 6, 8, 10, 3, 7, 1, 9 en 5 blijft over.
Er zijn verschillende implementaties van dit algoritme mogelijk.
Probeer er verschillende uit en vergelijk de performanties.
Maak functies van de vorm
int josephusX(int n, int k)
waarbij X het nummer van je implementatie is. De functie geeft het nummer van de overblijvende persoon terug, bv. josephus1(10,2) geeft 5.
Om de performantie te meten kun je de functie clock()
uit <ctime> gebruiken.
NetBeans
We werken in C++ in NetBeans onder Linux.
Meer uitleg hier
|
Algemeen