Komplexe Anwendungen: Von musizierenden Chinesen und Schüttelwörtern

Aus ProgrammingWiki

(define char-downcase (lambda (z) (string-ref (string-downcase (string z)) 0))) (define char-upcase (lambda (z) (string-ref (string-upcase (string z)) 0))) (define element? (lambda (el ls) (cond [(null? ls) #f] [(equal? el (car ls)) #t] [else (element? el (cdr ls))]))) (define element-streichen (lambda (el ls) (cond [(null? ls) ls] [(equal? el (car ls)) (cdr ls)] [else (cons (car ls) (element-streichen el (cdr ls)))]))) (define set-equal? (lambda (ls1 ls2) (cond [(and (null? ls1) (null? ls2)) #t] [(or (null? ls1) (not (element? (car ls1) ls2))) #f] [else (set-equal? (cdr ls1) (element-streichen (car ls1) ls2))]))) (define schuettelwort? (lambda (zk1 zk2) (set-equal? (string->list zk1) (string->list zk2))))

Inhaltsverzeichnis 1 Zur Wiederholung: Selektoren für Zeichenketten 1.1 Erstes Zeichen einer Zeichenkette 1.2 Restzeichenkette 1.3 Zeichen einer Zeichenkette voranstellen 2 Drei Chinesen mit dem Kontrabass... 3 Schüttelwörter 3.1 Algorithmus 3.2 Implementation 4 Zum Weiterarbeiten 4.1 Palindromsätze 4.2 Zickzack-Verschlüsselung

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$

(define string-car (lambda (zk) ...))

(string-car "Informatik")

ausführen

Restzeichenkette

Unter einer Restzeichenkette wollen wir wieder die Zeichenkette ohne das erste Zeichen verstehen:

string-cdr: $string \longmapsto string$

(define string-cdr (lambda (zk) ...))

(string-cdr "Informatik")

ausführen

Zeichen einer Zeichenkette voranstellen

Weiterhin soll es möglich sein, ein beliebiges Zeichen einer Zechenkette voranzustellen:

string-cons: $char, string \longmapsto string$

(define string-cons (lambda (z zk) ...))

(string-cons #\I "nformatik")

ausführen

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.

(define drei-chinesen (lambda (zk vok) ...))

(drei-chinesen "Drei Chinesen mit dem Kontrabass sassen auf der Strasse und erzaehlten sich was." #\i)

ausführen

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.

(define zeichen-streichen (lambda (z zk) ...))

(zeichen-streichen #\t "Informatik")

ausführen

Nun sollte die Generierung von Schüttelwörtern kein Problem mehr sein.

(define schuettelwort (lambda (zk) ...))

(schuettelwort "Informatik")

ausführen

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.