====== Aufgaben Serie A ====== {{gem/mgr}} {{gem/pageinfo}} ==== 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 {{gem/plain#e7c7042d0b73d166}} ++++ 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 {{gem/plain#e6c1c67d26b7aea2}} ++++ 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) | /I - I/ - /g / - $//g++++ ==== 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 ... {{gem/plain#0de680f5762bedf3}} ++++ Lösung | //"They are not organized!"\n\n/! Erläuterungen: Das leere Wort '''' wird gleich am Anfang des Textes gefunden.++++ ==== 4 Suffix ==== Schreibe einen Algorithmus, der zwei Leerzeilen und (c)-Notiz an einen beliebigen Text anfügt. Beispiel: ; Eingabe : Es war einmal .... ; Ausgabe : Es war einmal ... © by BOFH, 2012 {{gem/plain#d94499fa57abd894}} ++++ 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 {{gem/plain#0b808d3b5101c0df}} ++++ 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. {{gem/plain#09adc43b60d43bdc}} ++++ 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 [[wpde>Palindrom]] handelt: Ausgabe ''1'', sonst ''0''. {{gem/plain#710c4ac943c8575d}} ++++ Lösung | /^(.)(.*)\1$/$2/ /^.?$/1/! /.*/0/! ++++ ==== 8 Palindrom erstellen ==== Schreibe einen Algorithmus, der aus der Eingabe ein Palindrom erzeugt. Beispiel: ; Eingabe : reit ; Ausgabe : reittier {{gem/plain#cdbf5bc99e95feff}} ++++ 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 [[wpde>Pangramm]] (ohne ä, ö, ü und ss) vorliegt. Beispiel: ; Eingabe : Stanleys Expeditionszug quer durch Afrika wird von jedermann bewundert. ; Ausgabe : ok {{gem/plain#c3829d1a11044e32}} ++++ 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. {{gem/plain#3c6b1a36af04fce4}} ++++ 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|...++ ++++