Aufgaben Serie A
1 Strichaddition / unäres Addieren
Schreibe einen Algorithmus, der Zahlen, die als Striche (I+) dargestellt werden, addieren kann. Z.B.
- Eingabe
-
IIII + III + I
- Ausgabe
-
IIIIIIII
Loading ⌛
Lösung A
/ \+ //
Erläuterung: Damit das Zeichen + nicht als Steuerzeichen interpretiert wird, muss man dies mit einem \ markieren.
Lösung B
/[^I]//g
Erläuterung: Die Variante B entfernt alle Zeichen die kein I sind.
2 Strichsubstraktion / unäres Substrahieren
Schreibe einen Algorithmus, der Zahlen, die als Striche (I+) dargestellt werden, subtrahieren kann. Z.B.
- Eingabe
-
IIII - III
- Ausgabe
-
I
Loading ⌛
Lösung 1
1. Versuch:
/II - II/I - I/
/I - I//
Der Algorithmus löst alle Aufgaben der Form (I+)(I*) - \I bzw. (n + m) - n für n>1 und m>0 zuverlässig. Aufgaben mit einem Resultat < 0 werden falsch gelöst; der Algorithmus liefert den Betrag zurück.
2. Versuch:
/II - II/I - I/
/^I - II/- I/ !
/I - I//
Der Algorithmus löst nun alle Aufgaben der Form I+ - I+ korrekt, auch solche die ein negatives Resultat zurückgeben. Eine Verkettung von Subsitutionen der Form I+ (- I+)+ ist jedoch nicht möglich.
Lösung 2
/(I*) - \1$//
Dieser Algoithmus berechnet alle Substraktionen die ein Resultat ≤ 0 haben. Ansonsten bleibt die Eingabe unverändert.
Lösung 3 (Roman)
3 Präfix
Schreibe einen Algorithmus, der dein Lieblingszitat plus zwei Leerzeilen an den Anfang einer beliebigen Eingabe einfügt. Beispiel:
- Eingabe
-
Es war einmal ....
- Ausgabe
-
"They are not organized!"
Es war einmal ...
Loading ⌛
Lösung
//"They are not organized!"\n\n/!
Erläuterungen: Das leere Wort
4 Suffix
Schreibe einen Algorithmus, der zwei Leerzeilen und ©-Notiz an einen beliebigen Text anfügt. Beispiel:
- Eingabe
-
Es war einmal ....
- Ausgabe
-
Es war einmal ...
© by BOFH, 2012
Loading ⌛
Lösung
/$/\n\n© by BOFH, 2012/!
Erläuterungen: $ markiert das Ende des Textes.
Gäbe es das $-Zeichen zum Markieren des Wortendes nicht, so müsste jeweils der ganze Text mit in Betracht gezogen werden:
/.*/$&\n\n© by BOFH, 2012/ !
5 Zeichenreduktion
Schreibe einen Algorithmus, der eine Reihe gleicher Zeichen auf ein Zeichen reduziert. Ansonsten wird ERROR ausgegeben.
- Eingabe
-
aaaaaaaaaaaaaaaaaaa
- Ausgabe
-
a
Loading ⌛
Lösung
/^(.)\1*$/$1/ !
/.*/ERROR/ !
6 Stottern
Schreibe eine Algorithmus, der jeweils die ersten zwei Buchstaben eines Wortes in einen Text drei mal wiederholt. Beispiel
- Eingabe
-
Stottern, auch Balbuties, ist eine Störung
des Redeflusses, welche durch häufige
Unterbrechungen des Sprechablaufs,
durch Wiederholungen von Lauten,
Silben und Wörtern gekennzeichnet ist.
- Ausgabe
-
StStStottern, auauauch BaBaBalbuties,
isisist eieieine StStStörururung
dededes ReReRedeflusses, wewewelche
dududurch häufufufige UnUnUnterbrechungen
dededes SpSpSprechablaufs, dududurch
WiWiWiederholungen vovovon LaLaLauten,
SiSiSilben ununund Wörtrtrtern
gegegekennzeichnet isisist.
Loading ⌛
Lösung
/\b(\w{2})/$1$1$1/ig
Erläuterungen:
-
\b
- Kennzeichnet den Anfang eines Wortes
-
(\w{2})
- Gruppe 1
-
\w
- Bezeichnet ein Buchstaben.
Die Buchstaben mit Umlauten und sowie andere Sonderzeichen sind nicht in der Zeichenklasse \w enthalten
-
{2}
- Gibt an, dass das Muster
\w sich wiederholt (i.a.W wir wollen zwei Buchstaben)
7 Palindrom prüfen
Schreibe einen Markow Algorithmus, der für eine Eingabe prüft ob es sich um ein Palindrom handelt: Ausgabe 1, sonst 0.
Loading ⌛
Lösung
/^(.)(.*)\1$/$2/
/^.?$/1/!
/.*/0/!
8 Palindrom erstellen
Schreibe einen Algorithmus, der aus der Eingabe ein Palindrom erzeugt. Beispiel:
- Eingabe
-
reit
- Ausgabe
-
reittier
Loading ⌛
Lösung
/(.)ξ(.*)/ξ$1$2$1/
/ξ//!
/$/ξ/
Erläuterungen: Beachte zuerst die beiden Regeln
/(.)ξ(.*)/ξ$1$2$1/
/ξ//!
/$/ξ/
Das ist eine Programmtechnik die in vielen Markow-Algorithmen zu finden ist. Ein bestimmter Marker wird eingefügt (als letzte Regel). Und als vorletzte Regel wird der Marker wieder entfernt und die Ausführung stoppt. Die Idee ist folgende: Sämtliche andere Regeln werden nur ausgeführt wenn ein bestimmter Marker vorliegt. In diesem Fall grenzt der Marker ξ den Teil des Wortes ab, der noch nicht bearbeitet wurde. Beachte wie er nach dem Einführen in jedem Schritt nach links rutscht bis das ganze Wort bearbeitet wurde.
9 Pangramm
Schreibe einen Algorithmus, der prüft ob ein Pangramm (ohne ä, ö, ü und ss) vorliegt. Beispiel:
- Eingabe
-
Stanleys Expeditionszug quer durch Afrika wird von jedermann bewundert.
- Ausgabe
-
ok
Loading ⌛
Lösung
/[^a-z]//ig entfernt alle nicht zählenden Zeichen
/(.)(.*)\1/$1$2/ig entfernt alle mehrfach vorkommende Zeichen
/.{26}/ok/ ! ok, falls 26 Zeichen vorhanden (stop)
/.*/fail/ ! fail, sonst (stop)
10 Parität
Schreibe einen Markow Algorithmus, der 1 zurückgibt wenn die Länge einer Eingabe ungerade ist, und das leere Wort, wenn die Länge der Eingabe gerade ist.
Loading ⌛
Lösungen
/..//g
/./1/!
Diese Lösung versagt beim Vorhandensein von Zeilenumbrücken \n, da diese vom Jocker . nicht erfasst werden. Alternative Lösung:
/^((.|\n)(.|\n))*$// !
/(.|\n)*/1/ !
Variante: Wie sieht die Lösung aus, wenn geprüft werden sollte, ob die Länge durch 8 ohne Rest teilbar ist? Lösung …