Praktikum - Programmieren mit (rekursiven) Funktionen

Vorbemerkung

Man benötigt etwas Übung, um Probleme funktional zu lösen - vor allem dann, wenn man Probleme vorher in der Regel imperativ gelöst hat.

Die folgenden Aufgaben sollen dazu dienen, das funktionale Denken zu schulen. Achte auf die Einschränkung, dass Variablen nur zur Erzeugung lokaler Bindungen benutzt werden sollen und dass keine Wiederholungsanweisungen vorkommen dürfen.

Beachte, dass die folgenden Aufgaben voraussetzen, dass du die Verarbeitung von Zahlen und Listen beherrschst. Wenn nicht, musst du dir gegebenenfalls in anderen Kapiteln die erforderlichen Informationen besorgen.

Aufgabe 1

Wir betrachten die Berechnung der Summe natürlicher Zahlen. Hier ein iterativer Algorithmus zur Summenberechnung:

ALGORITHMUS Summenberechnung:
{vorher: n ∈ N}
setze s auf 0
setze i auf 0
SOLANGE i <= n:
    erhöhe s um i
    erhöhe i um 1
{nachher: s = 0+1+2+...+n}

Die folgenden Problemreduktionsschritte verdeutlichen, wie man die Summenberechnung auch rekursiv durchführen kann.

summe(0) -> 
    0

summe(5) ->
    5 + summe(4)

Entwickle und teste eine hierzu passende Funktionsdefinition.

Aufgabe 2

Ein Kapital von 1000 Euro wird jährlich mit 5% verzinst. Die Funktion kapital(n) beschreibe den Kapitalwert nach n Jahren.

Die folgenden Problemreduktionsschritte sollen einem funktionalen Programm zu Grunde liegen.

kapital(0) -> 
    1000

kapital(5) ->
    kapital(4) + 0.05 * kapital(4)

Verallgemeinere diese Reduktionsschritte zu einem Programm und teste es mit mehreren Funktionsaufrufen.

Aufgabe 3

Ein Patient nimmt jeden Morgen 5 mg eines Medikaments ein. Im Laufe des Tages werden von dem gesamten, im Körper befindlichen Medikament 40% abgebaut. Die Funktion medikamentenmenge(n) beschreibe die Menge des Medikaments (in mg), die sich am n-ten Tag morgens nach Einnahme des Medikaments im Körper befindet.

Ergänze die folgenden Problemreduktionsschritte und verallgemeinere sie zu einem funktionalen Programm.

medikamentenmenge(0) -> 
    ...

medikamentenmenge(5) ->
    ...

Aufgabe 4

Was leistet die folgendermaßen definierte Funktion?

def anzahl(element, liste):
    if len(liste) == 0:
        return 0
    else:
        if liste[0] == element:
            return (1 + anzahl(element, liste[1:]))
        else:
            return anzahl(element, liste[1:])

Teste diese Funktion mit verschiedenen Aufrufen wie dem folgenden und erkläre, wie die Ergebnisse zustande kommen.

>>>anzahl('b', ['a', 'b', 'd', 'a', 'b']) 
...

Aufgabe 5

Betrachte die folgende rekursiven Funktionsdefinition:

def laenge(liste):
    if liste == []:
        return 0
    else:
        return 1 + laenge(liste[1:]) 

Was leistet sie? Erläutere die Idee mit Hilfe konkreter Reduktionsschritte.

Aufgabe 6

(a) 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 funktionalen 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.

(b) 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 funktionalen Programm.

entferneAlle('b', []) -> 
    

entferneAlle('b', ['b', 'c', 'b']) ->
    

entferneAlle('b', ['a', 'd', 'b', 'c', 'b']) ->
  

Aufgabe 7

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 funktionalen Programm.

addiere(3, []) -> 
    

addiere(3, [4, 6, 6, 2, 0, 3]) ->

Aufgabe 8

Das Problem besteht darin, aus einer Zahlenliste alle Elemente herauszufiltern, die kleiner als ein bestimmter Wert sind.

Erstelle erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem funktionalen Programm.

Aufgabe 9

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]

Erstelle erst einmal geeignete Problemreduktionsschritte. Verallgemeinere sie anschließend zu einem funktionalen Programm.

Aufgabe 10

Das folgenden Funktionsdefinitionen zur Bildverarbeitung sind noch keine Funktionsdefinitionen im Sinne der funktionalen Programmierung. Warum?

def invertiereBild(L):
    """
    das in L dargestellte Bild wird invertiert
    d.h.: aus 0 wird 1 und aus 1 wird 0
    """
    for i in range(3, len(L)):
        if L[i] == 0:
            L[i] = 1
        else:
            L[i] = 0
    return L

def addBit(i, j):
    """
    die Bits i und j werden wie folgt addiert:
    0+0->0; 0+1->1; 1+0->1; 1+1->1
    """
    s = i+j
    if s == 2:
        s = 1
    return s

def addBilder(M, N):
    """
    die Bitfolgen in M und N werden Bit für Bit addiert
    """
    L = []
    for i in range(len(M)):
        if i < 3:
            L = L + [M[i]]
        else:
            L = L + [addBit(M[i], N[i])]
    return L

Schreibe sie so um, dass keine Wiederholungsanweisungen mehr vorkommen und Variablen nur für lokale Bindungen benutzt werden. Überprüfe anschließend das Verhalten der Funktionen.