Wir haben zwei Varianten einer Funktion has_element betrachtet, die testet, ob eine gegebene Liste ein gesuchtes Element enthält. Die zweite Variante mit bedingter Schleife bricht die Suche ab, sobald das gesuchte Element gefunden wurde. Im Fall eines aufsteigend sortierten Eingabefeldes, können wir die Suche auch dann abbrechen, wenn wir das Element noch nicht gefunden haben, aber alle weiteren Elemente größer sind als das gesuchte.
Implementieren Sie ein Prädikat is_in_sorted, das eine sortierte Liste als erstes Argument erwartet und diese Idee umsetzt. Dokumentieren Sie dessen Ausführung für die Eingaben a = [2,4,6,8,10] und x = 5 mit einer Programmtabelle.
Schreiben Sie analog zum Programm aus der Vorlesung ein Python-Programm, das ein Liste fibs der ersten 11 Fibonacci-Zahlen berechnet. Die erste Fibonacci-Zahl F(0) ist gleich 0, für die zweite gilt F(1)= 1 und für alle weiteren Fibonacci Zahlen gilt F(i) = F(i-1) + F(i-2).
Wir können die Listen-Suche im Fall sortierter Listen noch verbessern. Implementieren Sie eine Funktion, die so aufgerufen werden kann wie is_in_sorted und auch das selbe Ergebnis liefert. Berechnen Sie dieses Ergebnis mit einer Teile-und-Herrsche-Suchstrategie, die analog zum Spiel “Zahlenraten” verfährt: In jedem Schritt soll dabei die Größe des durchsuchten Bereichs halbiert werden, bis das Element gefunden wurde oder der Bereich das gesuchte Element nicht mehr enthalten kann. Vergleichen Sie Laufzeiten Ihrer Funktion mit der von is_in_sorted, indem Sie zunächst mit einer Schleife große sortierte Listen erzeugen und dann mit beiden Funktionen die selben Elemente darin suchen.
Beschreiben Sie die Arbeitweise und die Ausgabe dieses Programms, ohne es auszuführen.
p = [True] * 101
p[0] = False
p[1] = False
for i in range(2, 11):
if p[i]:
for j in range(i, 100 // i + 1):
p[i*j] = False
for i in range(0,101):
if p[i]:
print(i)