Aufgaben

Hausaufgabe: Suche in sortierten Arrays

Wir haben zwei Varianten einer Funktion has_element betrachtet, die testet, ob ein gegebenes Array 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 ein sortiertes Array 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.

Aufgabe: Array von Fibonacci-Zahlen

Schreiben Sie analog zum Programm aus der Vorlesung ein Python-Programm, das ein Array 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).

Aufgabe: Binäre Suche in Arrays

Wir können die Array-Suche im Fall sortierter Felder 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 Felder erzeugen und dann mit beiden Funktionen die selben Elemente darin suchen.

Bonusaufgabe: Was berechnet dieses Programm?

Beschreiben Sie die Arbeitweise und die Ausgabe dieses Programms, ohne es auszuführen.

p = [None] * 101

p[0] = False
p[1] = False

for i in range(2, 101):
  p[i] = True

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)