Ü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.

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.

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']) ->
    

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]) ->
    

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.

Aufgabe 7

Das Problem besteht darin, eine Liste umzukehren.

Erstell erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem Algorithmus / Programm.

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.