Algorithmische Suche

Suche einen eigenen Algorithmus

Zunächst wollen wir versuchen, selbst einen Algorithmus zu finden, der unser Problem löst.

Aufgabe 1

(a) Lade die Schülerdatenbank data.txt herunter. Wenn Du dir diese Datenbank anschaust siehst Du, dass es achtzig paarweise verschiedene, vierstellige Nummern sind. Dies sind die Schülernummern.

(b) Importiere den Datensatz nach Python und entwickle einen Algorithmus, um ihn nach einer beliebigen Schülernummer zu durchsuchen.

Wenn Du nicht genau weißt, wie Du eine Textdatei nach Python importieren kannst, verwende einfach folgenden Code:

# Einlesen der Daten
Schuelerlist=[]
read = open("data.txt")
for line in read:
    Schuelerlist.append(line)
for i in range(len(Schuelerlist)):
    Schuelerlist[i]=Schuelerlist[i].replace("\n","")
    Schuelerlist[i]=int(Schuelerlist[i])
# Kontrollausgabe
for i in range(len(Schuelerlist)):
    print(Schuelerlist[i])

Achte darauf, dass das Programm und die Daten sich im selben Orden befinden. In der Liste Schuelerlist befinden sich nach der Nutzung von importData alle in data.txt gespeicherten Schuelernummern als String.

(c) Nutze deinen Algorithmus, um die Schülernummern 8889, 5755, 9956 und 1077 in der Liste zu finden. Nutze die dir bekannten Möglichkeiten, um die Laufzeit zu bestimmen.

(d) Nun bestimme die Laufzeit einer Prozedur, die deinen Algorithmus nutzt, um jede einzelne Schülernummer zwanzig mal zu suchen.

Im folgenden wollen wir gemeinsam einige andere Möglichkeiten entdecken, unser Problem zu lösen und diese Möglichkeiten mit deinem Algorithmus vergleichen.