| Beide Seiten der vorigen RevisionVorhergehende ÜberarbeitungNächste Überarbeitung | Vorhergehende Überarbeitung |
| markow:seriea [2019/02/24 20:47] – Tscherter, Vincent | markow:seriea [2024/03/03 22:36] (aktuell) – Tscherter, Vincent |
|---|
| | ====== 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 |
| | : <code>IIII + III + I</code> |
| | ; Ausgabe |
| | : <code>IIIIIIII</code> |
| | |
| | {{gem/plain#e7c7042d0b73d166}} |
| | |
| | ++++ Lösung A | <code>/ \+ //</code> |
| | |
| | Erläuterung: Damit das Zeichen ''+'' nicht als Steuerzeichen interpretiert wird, muss man dies mit einem ''\'' markieren.++++ |
| | |
| | ++++ Lösung B | <code>/[^I]//g</code> |
| | |
| | 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 |
| | : <code>IIII - III</code> |
| | ; Ausgabe |
| | : <code>I</code> |
| | |
| | {{gem/plain#e6c1c67d26b7aea2}} |
| | ++++ Lösung 1 | 1. Versuch: <code>/II - II/I - I/ |
| | /I - I//</code> 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: <code>/II - II/I - I/ |
| | /^I - II/- I/ ! |
| | /I - I//</code> 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 | <code>/(I*) - \1$//</code> |
| | Dieser Algoithmus berechnet alle Substraktionen die ein Resultat ≤ 0 haben. Ansonsten bleibt die Eingabe unverändert. ++++ |
| | |
| | ++++ Lösung 3 (Roman) | <code>/I - I/ - /g |
| | / - $//g</code>++++ |
| | ==== 3 Präfix ==== |
| | Schreibe einen Algorithmus, der dein Lieblingszitat plus zwei Leerzeilen an den Anfang einer beliebigen Eingabe einfügt. Beispiel: |
| | |
| | ; Eingabe |
| | : <code>Es war einmal ....</code> |
| | ; Ausgabe |
| | : <code>"They are not organized!" |
| | |
| | Es war einmal ... |
| | </code> |
| | |
| | {{gem/plain#0de680f5762bedf3}} |
| | ++++ Lösung | <code>//"They are not organized!"\n\n/!</code> |
| | |
| | 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 |
| | : <code>Es war einmal ....</code> |
| | ; Ausgabe |
| | : <code>Es war einmal ... |
| | |
| | © by BOFH, 2012</code> |
| | |
| | {{gem/plain#d94499fa57abd894}} |
| | ++++ Lösung | <code> |
| | /$/\n\n© by BOFH, 2012/!</code> |
| | |
| | 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: |
| | |
| | <code text> |
| | /.*/$&\n\n© by BOFH, 2012/ ! |
| | </code>++++ |
| | |
| | ==== 5 Zeichenreduktion ==== |
| | Schreibe einen Algorithmus, der eine Reihe gleicher Zeichen auf ein Zeichen reduziert. Ansonsten wird ''ERROR'' ausgegeben. |
| | |
| | ; Eingabe |
| | : <code>aaaaaaaaaaaaaaaaaaa</code> |
| | ; Ausgabe |
| | : <code>a</code> |
| | |
| | {{gem/plain#0b808d3b5101c0df}} |
| | ++++ Lösung | <code>/^(.)\1*$/$1/ ! |
| | /.*/ERROR/ !</code>++++ |
| | |
| | ==== 6 Stottern ==== |
| | Schreibe eine Algorithmus, der jeweils die ersten zwei Buchstaben eines Wortes in einen Text drei mal wiederholt. Beispiel |
| | |
| | ; Eingabe |
| | : <code>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.</code> |
| | ; Ausgabe |
| | : <code> |
| | 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.</code> |
| | |
| | {{gem/plain#09adc43b60d43bdc}} |
| | ++++ Lösung | <code text>/\b(\w{2})/$1$1$1/ig</code> |
| | |
| | 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 | <code text> |
| | /^(.)(.*)\1$/$2/ |
| | /^.?$/1/! |
| | /.*/0/! |
| | </code>++++ |
| | |
| | ==== 8 Palindrom erstellen ==== |
| | Schreibe einen Algorithmus, der aus der Eingabe ein Palindrom erzeugt. Beispiel: |
| | |
| | ; Eingabe |
| | : <code>reit</code> |
| | ; Ausgabe |
| | : <code>reittier</code> |
| | |
| | |
| | {{gem/plain#cdbf5bc99e95feff}} |
| | ++++ Lösung | <code> |
| | /(.)ξ(.*)/ξ$1$2$1/ |
| | /ξ//! |
| | /$/ξ/ |
| | </code> |
| | |
| | Erläuterungen: Beachte zuerst die beiden Regeln <code>/(.)ξ(.*)/ξ$1$2$1/ |
| | /ξ//! |
| | /$/ξ/</code> 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 |
| | : <code>Stanleys Expeditionszug quer durch Afrika wird von jedermann bewundert.</code> |
| | ; Ausgabe |
| | : <code>ok</code> |
| | |
| | {{gem/plain#c3829d1a11044e32}} |
| | ++++ Lösung | <code> |
| | /[^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)</code> ++++ |
| | |
| | ==== 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 | <code text> |
| | /..//g |
| | /./1/! |
| | </code> Diese Lösung versagt beim Vorhandensein von Zeilenumbrücken ''\n'', da diese vom Jocker ''.'' nicht erfasst werden. Alternative Lösung: <code text> |
| | /^((.|\n)(.|\n))*$// ! |
| | /(.|\n)*/1/ ! |
| | </code> |
| | |
| | Variante: Wie sieht die Lösung aus, wenn geprüft werden sollte, ob die Länge durch 8 ohne Rest teilbar ist? ++Lösung|...++ ++++ |
| |
