Komplexe Anwendungen: Von musizierenden Chinesen und Schüttelwörtern
Aus ProgrammingWiki
Inhaltsverzeichnis |
Zur Wiederholung: Selektoren für Zeichenketten
Für die nachfolgenden Manipulationen von Zeichenketten benötigen wir die schon bekannten Selektoren für Zeichenketten, die wir in den komplexen Anwendungen mit Zeichenketten und Listen definiert haben. Wir sollten dabei auch an die korrekten Signaturen denken.
Erstes Zeichen einer Zeichenkette
string-car: $string \longmapsto char$
Quelltext überprüfen:
Restzeichenkette
Unter einer Restzeichenkette wollen wir wieder die Zeichenkette ohne das erste Zeichen verstehen:
string-cdr: $string \longmapsto string$
Quelltext überprüfen:
Zeichen einer Zeichenkette voranstellen
Weiterhin soll es möglich sein, ein beliebiges Zeichen einer Zechenkette voranzustellen:
string-cons: $char, string \longmapsto string$
Quelltext überprüfen:
Drei Chinesen mit dem Kontrabass...
Sie kennen alle dieses bekannte Kinderlied, bei dem von Strophe zu Strophe alle Vokale durch einen einzigen zu ersetzen sind:
"Drei Chinesen mit dem Kontrabass sassen auf der Strasse und erzaehlten sich was." --> "Drii Chinisin mit dim Kintribiss sissin iif dir Strissi ind irziihltin sich wis."
Vervollständigen Sie die nachfolgende Prozedur, die eine beliebige Strophe dieses Kinderliedes generieren kann.
Achten Sie dabei auf eine unveränderte Groß- und Kleinschreibung aller Wörter. Vermeiden Sie aber den Gebrauch von Umlauten. Weiterhin ist es zu empfehlen, die oben definierten Prozeduren string-car, string-cdr und string-cons zu nutzen.
Quelltext überprüfen:
Schüttelwörter
Schüttelwörter entstehen dadurch, dass ihre Zeichen in eine neue, völlig beliebige Reihenfolge gebracht werden. Einen Sinn müssen die neu gewonnenen Zeichenketten nicht besitzen. Lediglich die ursprüngliche Groß- und Kleinschreibung soll erhalten bleiben.
Algorithmus
- Das Schüttelwort einer leeren Zeichenkette ist ebenfalls leer.
- Ermittle anderenfalls ein Zeichen an einer zufälligen Position in der übergebenen Zeichenkette und
- stelle es der geschüttelten (Rest-)Zeichenkette voran, in der dieses Zeichen gestrichen wurde.
Implementation
Der Algorithmus legt die Konstruktion einer Hilfsprozedur nahe, mit der ein beliebiges Zeichen $z$ in einer Zeichenkette $zk$ beim ersten Auftreten gestrichen werden kann.
Implementieren Sie zunächst diese Prozedur.
Quelltext überprüfen:
Nun sollte die Generierung von Schüttelwörtern kein Problem mehr sein.
Quelltext überprüfen:
Hinweis: Schüttelwörter, die selbst wieder einen Sinn ergeben, heißen Anagramme.
Zum Weiterarbeiten
Palindromsätze
Mit bedingten Ausdrücken haben wir einen einfachen Palindrom-Prüfer konstruiert.
Interessanterweise können auch ganze Sätze vor- und rückwärts gleich lauten, wenn Leer- und Sonderzeichen unberücksichtigt bleiben.
Entwickeln Sie ein vergleichbares Prädikat, das auch Palindrom-Sätze detektieren kann.
Zur Problemlösung.
Zickzack-Verschlüsselung
Durch ein strukturiertes Umordnen von Buchstaben, Ziffern, Satz- und Sonderzeichen lassen sich Texte bereits in einfacher Weise verschlüsseln. Eine Möglichkeit besteht darin, die Zeichen eines Textes wechselseitig in zwei Teilzeichenketten abzulegen und diese dann aneinander zu hängen. Zum Entschlüsseln muss nun diese Zeichekette geteilt werden, um die Zeichen wechselseitig (also zickzackförmig) zum Klartext zusammenzusetzen. Implementieren Sie diese Zickzack-Ver- und Entschlüsselung.
Zur Problemlösung.