Problemreduktion

Das Problem auf ein analoges zurückführen

Hier noch einmal die Verschlüsselungstabelle, die zum Verschlüsseln benutzt werden soll.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
| | | | | | | | | | | | | | | | | | | | | | | | | |
G K X C S L Z U A H W D B M T Y E N J V P O I R F Q

Der Text PARTY soll mit der Funktion verschluesselterText in den Geheimtext YGNVF überführt werden.

P A R T Y
| | | | |
Y G N V F

Bei der Implementierung verwenden wir die Strategie der rekursiven Problemreduktion:

Rekursionsschritt:

verschluesselterText "PARTY" -> (verschluesseltesZeichen "P") ++ (verschluesselterText "ARTY")

Rekursionsanfang:

verschluesselterText "" -> ""

Aufgabe 1

(a) Erläutere den gezeigten Rekursionsschritt. Inwiefern wird hier das Problem "PARTY"-verschlüsseln auf ein entsprechendes Problem in verkleinerter Form zurückgeführt? Welche Rolle spielt die Hilfsfunktion verschluesseltesZeichen im Rekursionsschritt?

(b) Erläutere auch den gezeigten Rekursionsanfang. Warum gelangt man zum Rekursionsanfang, wenn man den Rekursionsschritt wiederholt ausführt?

Aufgabe 2

Wir verallgemeinern jetzt den Rekursionsschritt und den Rekursionsanfang. Setze die Teilausdrücke (erstesZeichen text) und (ohneErstesZeichen text) an die richtigen Stellen.

Rekursionsschritt:

Falls text nicht die leere Zeichenkette "" ist:
verschluesselterText text -> (verschluesseltesZeichen ...) ++ (verschluesselterText ...)

Rekursionsanfang:

Falls text == "":
verschluesselterText text -> ""

Aufgabe 3

Entwickle analog einen Rekursionsschritt und einen Rekursionsanfang für die Funktion entschluesselterText.

Rekursionsschritt:

Falls text nicht die leere Zeichenkette "" ist:
entschluesselterText text -> ...

Rekursionsanfang:

Falls text == "":
entschluesselterText text -> ...