Übungen
Aufgabe 1
Das im letzten Abschnitt entwickelte Programm ist hier um print-Anweiungen ergänzt worden:
def anzahl(element, liste):
print("anzahl", element, liste)
if len(liste) == 0:
return 0
else:
if liste[0] == element:
print("Element gefunden")
return (1 + anzahl(element, liste[1:]))
else:
return anzahl(element, liste[1:])
Teste dieses Programm mit verschiedenen Aufrufen wie dem folgenden und erkläre die Ausgaben auf dem Bildschirm.
>>>anzahl('b', ['a', 'b', 'd', 'a', 'b'])
...
Aufgabe 2
Betrachte den folgenden rekursiven Algorithmus:
def laenge(liste):
if liste == []:
return 0
else:
return 1 + laenge(liste[1:])
Was leistet er? Erläutere die Idee des Algorithmus mit Hilfe konkreter Reduktionsschritte.
Nutze das folgende Werkzeug, um den Aufrufbaum schrittweise zu erkunden und deine Erklärung zu überprüfen.
Aufgabe 3
Das Problem besteht darin, ein Element aus einer Liste zu entfernen. Kommt das Element mehrfach vor, so soll nur das erste vorkommende Element entfernt werden.
Die folgenden Problemreduktionsschritte sollen dem Algorithmus / Programm zu Grunde liegen.
entferneErstes('b', []) ->
[]
entferneErstes('b', ['b', 'c', 'b']) ->
['c', 'b']
entferneErstes('b', ['a', 'd', 'b', 'c', 'b']) ->
['a'] + entferneErstes('b', ['d', 'b', 'c', 'b'])
Verallgemeinere diese Reduktionsschritte zu einem Programm und teste es mit mehreren Funktionsaufrufen.
Hilfe-Schritt 1: Implementierung ausprobieren
Wenn du deinen Algorithmus implementiert hast, kannst du ihn hier mit verschiedenen Eingaben testen. Der RecursionTutor zeigt dir den vollständigen Aufrufbaum und hilft dir, Fehler in deiner Lösung zu finden.
Hilfe-Schritt 2: Lücken füllen
Nutze den RecursionTutor, um deine Lösung zu überprüfen. Fülle zunächst die Lücken im Diagramm für entferneErstes(2, [1,3,2,4]) aus.
Hilfe-Schritt 3: Algorithmus ausprobieren
Hier siehst du den fertigen Algorithmus im RecursionTutor. Erkunde das Diagramm mit verschiedenen Eingaben und beobachte, wie sich der Aufrufbaum verändert. Versuche anschließend, den Algorithmus selbst nachzuschreiben.
Aufgabe 4
Das Problem besteht darin, ein Element aus einer Liste zu entfernen. Kommt das Element mehrfach vor, so sollen alle vorkommenden Elemente entfernt werden.
Ergänze die folgenden Problemreduktionsschritte und verallgemeinere sie zu einem Algorithmus / Programm.
entferneAlle('b', []) ->
entferneAlle('b', ['b', 'c', 'b']) ->
entferneAlle('b', ['a', 'd', 'b', 'c', 'b']) ->
Hilfe-Schritt 1: Implementierung ausprobieren
Wenn du deinen Algorithmus implementiert hast, kannst du ihn hier mit verschiedenen Eingaben testen. Der RecursionTutor zeigt dir den vollständigen Aufrufbaum und hilft dir, Fehler in deiner Lösung zu finden.
Hilfe-Schritt 2: Lücken füllen
Nutze den RecursionTutor, um die Rekursion Schritt für Schritt nachzuvollziehen. Fülle die Lücken im Diagramm für entferneAlle(2, [1,2]) aus.
Hilfe-Schritt 3: Algorithmus ausprobieren
Hier siehst du den fertigen Algorithmus im RecursionTutor. Erkunde das Diagramm mit verschiedenen Eingaben und beobachte, wie sich der Aufrufbaum verändert. Versuche anschließend, den Algorithmus selbst nachzuschreiben.
Aufgabe 5
Das Problem besteht darin, jedes Element aus einer Zahlenliste um einen bestimmten Wert zu erhöhen.
Ergänze die folgenden Problemreduktionsschritte und verallgemeinere sie zu einem Algorithmus / Programm.
addiere(3, []) ->
addiere(3, [4, 6, 6, 2, 0, 3]) ->
Hilfe-Schritt 1: Implementierung ausprobieren
Wenn du deinen Algorithmus implementiert hast, kannst du ihn hier mit verschiedenen Eingaben testen. Der RecursionTutor zeigt dir den vollständigen Aufrufbaum und hilft dir, Fehler in deiner Lösung zu finden.
Hilfe-Schritt 2: Lücken füllen
Nutze den RecursionTutor, um die Rekursion Schritt für Schritt nachzuvollziehen. Fülle die Lücken im Diagramm für addiere(3, [1,2]) aus.
Hilfe-Schritt 3: Algorithmus ausprobieren
Hier siehst du den fertigen Algorithmus im RecursionTutor. Erkunde das Diagramm mit verschiedenen Eingaben und beobachte, wie sich der Aufrufbaum verändert. Versuche anschließend, den Algorithmus selbst nachzuschreiben.
Aufgabe 6
Das Problem besteht darin, aus einer Zahlenliste alle Elemente herauszufiltern, die kleiner als ein bestimmter Wert sind.
Erstell erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem Algorithmus / Programm.
Hilfe-Schritt 1: Implementierung ausprobieren
Wenn du deinen Algorithmus implementiert hast, kannst du ihn hier mit verschiedenen Eingaben testen. Der RecursionTutor zeigt dir den vollständigen Aufrufbaum und hilft dir, Fehler in deiner Lösung zu finden.
Hilfe-Schritt 2: Lücken füllen
Nutze den RecursionTutor, um die Rekursion Schritt für Schritt nachzuvollziehen. Fülle die Lücken im Diagramm für alleKleiner(4, [1,5]) aus.
Hilfe-Schritt 3: Algorithmus ausprobieren
Hier siehst du den fertigen Algorithmus im RecursionTutor. Erkunde das Diagramm mit verschiedenen Eingaben und beobachte, wie sich der Aufrufbaum verändert. Versuche anschließend, den Algorithmus selbst nachzuschreiben.
Aufgabe 7
Das Problem besteht darin, eine Liste umzukehren.
Erstell erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem Algorithmus / Programm.
Hilfe-Schritt 1: Implementierung ausprobieren
Wenn du deinen Algorithmus implementiert hast, kannst du ihn hier mit verschiedenen Eingaben testen. Der RecursionTutor zeigt dir den vollständigen Aufrufbaum und hilft dir, Fehler in deiner Lösung zu finden.
Hilfe-Schritt 2: Lücken füllen
Nutze den RecursionTutor, um die Rekursion Schritt für Schritt nachzuvollziehen. Fülle die Lücken im Diagramm für umkehr([1,2]) aus.
Hilfe-Schritt 3: Algorithmus ausprobieren
Hier siehst du den fertigen Algorithmus im RecursionTutor. Erkunde das Diagramm mit verschiedenen Eingaben und beobachte, wie sich der Aufrufbaum verändert. Versuche anschließend, den Algorithmus selbst nachzuschreiben.
Aufgabe 8
Das Problem besteht darin, aus einer geschachtelten Liste eine flache Liste zu erzeugen.
>>>flacheListe([[3, 5], 6, [], [4, [2, 9]]])
[3, 5, 6, 4, 2, 9]
Erstell erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem Algorithmus / Programm.