MINT üben

Lineare Suche

Zwei Aufgaben im Abiturformat — von der Einlasskontrolle bis zur Hochwasserwarnung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Einlass im Schwimmbad

AFB I–II

Am Drehkreuz eines Schwimmbads wird jede Jahreskarte gescannt. Das Programm prüft, ob die Kartennummer x in der Reihung karten der gültigen Karten vorkommt. Die Reihung ist nicht sortiert; eine versehentlich doppelt ausgegebene Nummer steht zweimal darin. Zur Prüfung wird die lineare Suche verwendet, die den Index des ersten Vorkommens oder −1 liefert.

Ausschnitt der Reihung karten (Länge 8)
  1. Beschreiben Sie das Vorgehen der linearen Suche bei der Prüfung einer Kartennummer x und nennen Sie die beiden möglichen Arten von Rückgabewerten.
  2. Stellen Sie den Ablauf der Suche nach x = 7002 in einer Tracetabelle mit den Spalten i, karten[i] und karten[i] = x dar. Geben Sie außerdem die Rückgabewerte für x = 1187 und x = 1000 mit der jeweiligen Zahl der Vergleiche an.
  3. Implementieren Sie eine Methode static boolean istGueltig(int[] karten, int x), die genau dann true liefert, wenn x in karten vorkommt. Die Methode soll beim ersten Treffer abbrechen.
  4. Das Bad hat 12 000 Jahreskarten. Schätzen Sie ab, wie viele Vergleiche eine Prüfung im ungünstigsten Fall und bei einer gültigen Karte durchschnittlich benötigt, und wie sich beides ändert, wenn sich die Zahl der Karten verdoppelt.

Hinweise

Hinweis zu Aufgabe a)
Zwei Fälle unterscheiden: x wird gefunden oder nicht.
Hinweis zu Aufgabe b)
Die Tabelle endet mit dem ersten Vergleich, der wahr ist. Die Nummer 1187 steht zweimal in der Reihung.
Hinweis zu Aufgabe c)
Zählschleife über alle Indizes, im Rumpf ein Vergleich mit sofortigem return true; return false erst nach der Schleife.
Hinweis zu Aufgabe d)
Bei einer gültigen Karte ist jede Position etwa gleich wahrscheinlich — im Mittel liegt der Treffer in der Mitte.