Ga naar hoofdinhoud

Bouw zelf — een nieuw probleem

Leerdoel: je gebruikt de bouwstenen van lineair zoeken om een nieuw probleem op te lossen, zonder dat je het algoritme letterlijk kopieert.

Opdracht​

Bouw een functie alle_indexen(lijst, doel) die een lijst teruggeeft met alle indexen waar het doel voorkomt.

  • alle_indexen([3, 1, 4, 1, 5], 1) → [1, 3]
  • alle_indexen([7, 7, 7], 7) → [0, 1, 2]
  • alle_indexen([], 9) → []
  • alle_indexen([1, 2, 3], 9) → []

De startcode roept je functie aan op die vier lijsten en print het resultaat naast wat het moet zijn.

Python
Code-omgeving wordt voorbereid…
Tip

Twee dingen veranderen ten opzichte van zoek:

  1. Je hebt een lijst nodig om de resultaten in te bewaren (resultaat = []).
  2. Stop niet bij de eerste match, maar loop door tot het eind.

Aan het eind van de functie return je de lijst.

Welke bouwsteen valt weg? Welke krijgen er een variant?

Antwoord
def alle_indexen(lijst, doel):
    resultaat = []
    for i, waarde in enumerate(lijst):
        if waarde == doel:
            resultaat.append(i)
    return resultaat

print(alle_indexen([3, 1, 4, 1, 5], 1))   # [1, 3]
print(alle_indexen([7, 7, 7], 7))         # [0, 1, 2]
print(alle_indexen([], 9))                # []

Wat hier opvalt:

  • Bouwsteen 1 en 2 zijn precies hetzelfde gebleven (doorlopen + vergelijken).
  • Bouwsteen 3 is nu toevoegen aan lijst in plaats van direct return.
  • Bouwsteen 4 valt weg — geen -1 meer, een lege lijst is al een betekenisvol "niet-gevonden"-signaal.

Onderzoek​

Kun je alle_indexen eerder laten stoppen als het doel nergens voorkomt?

Nee — en dat is precies het verschil met zoek. Bij zoek mocht je stoppen zodra je het doel één keer had gezien. Bij alle_indexen weet je pas aan het einde van de lijst zeker dat er geen match meer komt, dus je loopt hem altijd helemaal door.

alle_indexen doet dus altijd n vergelijkingen, waar zoek er in het beste geval maar één doet.

Uitdaging (optioneel)​

Schrijf eerste_groter_dan(lijst, drempel) die de index van het eerste element returnt dat groter is dan drempel, of -1 als er geen zo'n element is.

  • eerste_groter_dan([3, 8, 2, 9], 5) → 1
  • eerste_groter_dan([1, 2, 3], 5) → -1
Tip

Dit is zoek met een andere vergelijking: niet waarde == doel, maar waarde > drempel. Alle vier de bouwstenen blijven staan, ook de -1 aan het eind.

Antwoord
def eerste_groter_dan(lijst, drempel):
    for i, waarde in enumerate(lijst):
        if waarde > drempel:
            return i
    return -1

print(eerste_groter_dan([3, 8, 2, 9], 5))   # 1
print(eerste_groter_dan([1, 2, 3], 5))      # -1

Door naar veelgemaakte fouten.