Algoritmes om lijsten te verwerken
Op deze pagina, test je of de elementen van een lijst verschillend zijn (dus
of er geen duplicaten zijn).
Stel dat je een lijst met elementen hebt en wilt weten of de elementen van de lijst verschillend zijn (uniek). Dit soort vragen komen vaak voor: een webzoekmachine wil bijvoorbeeld zeker weten dat alle zoekresultaten van elkaar verschillen.
Hier is één algoritme om het probleem op te lossen:
Algoritmen kunnen worden uitgedrukt in natuurlijke taal of in pseudocode, tekst die de
stappen beschrijft die een programma moet uitvoeren. Deze tekst die makkelijk voor mensen te begrijpen
is kan helpen voor het schrijven van het algoritme in een programmeertaal.
- Stap 1. Vergelijk het eerste element van de lijst met alle latere elementen in
de lijst (het tweede, het derde, enz.). Als je het eerste element opnieuw ziet, meld
je dat de cijfers niet verschillend zijn (
onwaar). - Stap 2. Als je stap 1 voltooid hebt zonder te stoppen, vergelijk je het tweede
element met alle latere element (de derde, de vierde, enz.). Als je het tweede element opnieuw ziet,
meld
je dat de cijfers niet verschillend zijn (
onwaar). - Stap 3. Herhaal stap 2 voor elk element in de lijst. Vergelijk dat element met elk van de latere elementen in de lijst.
- Stap 4. Als je stap 3 voltooid hebt zonder dubbelen te vinden, rapporteer dan
dat de elementen verschillend zijn (
waar).
- Bouw een predikaat dat het bovenstaande algoritme implementeert.
Als
je de lengte van de lijst zou verdubbelen, zou dit algoritme dan evenveel tijd kosten? Twee keer
zo lang? Meer dan twee keer zo lang?
Alex: Ons predikaat vertelt ons of de elementen van een lijst verschillend zijn. Ik
wil nog iets meer informatie hebben.
Yasmine: Wat wil je dan?
Alex: Als er duplicaten in de lijst staan, wil ik graag zien welke getallen het zijn. Op
die manier kan ik ze verwijderen.
Bo: Oké, laten we een rapporteur schrijven die de lijst met duplicaten in een lijst
rapporteert.
- Bouw een rapporteur die alle dubbele elementen in een lijst geeft:
- Bouw een rapporteur,
verwijder dubbelen, die een lijst als invoer gebruikt en diezelfde lijst maar zonder dubbele elementen rapporteert.