exorciser.ch

exorciser.ch

Webseiten-Werkzeuge

Sie befinden sich hier: exorciser.ch » Markow Algorithmen » Aufgaben Serie C

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen RevisionVorhergehende Überarbeitung
Nächste Überarbeitung		Vorhergehende Überarbeitung
markow:seriec [2018/09/04 15:17] – [9 Conway Folge] Tscherter, Vincentmarkow:seriec [2024/03/03 22:36] (aktuell) – Tscherter, Vincent
Zeile 1: Zeile 1:
 +===== Aufgaben Serie C =====
 +
 +{{gem/mgr}}{{gem/pageinfo}}
 +
 +==== 1 X-Mas Tree ======
 +
 +Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechenden Weihnachtsbaum zeichnet:
 +
 +  ; Eingabe
 +  : <code>
 +ooooooo
 +</code>
 +  ; Ausgabe
 +  : <code>
 +   o 
 +  ooo
 + ooooo
 +ooooooo
 +   o
 +</code>
 +
 +  * Die Grösse des Baumes ist abhängig von der Eingabe.
 +  * Erweiterung 1: Baumstrunk
 +  * Erweiterung 2: Baumschmuck
 +
 + {{gem/plain#d419758672dd4212}}
 +
 +++++ Lösung von Roli | <code text>
 +/^(\s*)(o*)oo/ $1$2\n$&/
 +/^( *o)((\n *o*)*)$/$1$2\n$1/!
 +</code> ++++
 +
 +++++ Lösung von Tscherter| <code text>
 +/^( *oo?)\n[o\s]*/$&\n$1/!
 +/^( *o*)oo/ $1\n$&/</code> ++++
 +
 +==== 2 Pascalsche Dreieck =====
 +
 +Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechendes binäres Pascalsche Dreieck zeichnet.
 +
 +Eingabe <code>
 +oooooooooooooooooooooooooooooooooooooooo
 +o
 +o
 +o
 +o
 +o
 +o
 +o
 +o
 +o
 +o
 +</code>
 +
 +Ausgabe <code>
 +oooooooooooooooooooooooooooooooooooooooo
 +o o o o o o o o o o o o o o o o o o o o 
 +oo  oo  oo  oo  oo  oo  oo  oo  oo  oo  
 +o   o   o   o   o   o   o   o   o   o   
 +oooo    oooo    oooo    oooo    oooo    
 +o o     o o     o o     o o     o o     
 +oo      oo      oo      oo      oo      
 +o       o       o       o       o       
 +oooooooo        oooooooo        oooooooo
 +o o o o         o o o o         o o o o 
 +oo  oo          oo  oo          oo  oo  
 +</code>
 +
 + {{gem/plain#f983e5a38d8e7023}}
 +
 +++++ Lösung (TSC) | <code>
 +/αo([o \n]*)βo/oα$1oβ /
 +/αo([o \n]*)β /oα$1 βo/
 +/α ([o \n]*)βo/ α$1oβo/
 +/α ([o \n]*)β / α$1 β /
 +/α\no(.*)β(.)\no/\noα$1$2\nβo/
 +/α\n(.*)β(.)/\n$1$2/ !
 +/^o(o*)\no/oα$1\nβo/
 +</code> ++++
 +
 +==== 3 Häufigste Wort in einem Text ======
 +
 +Erstelle einen Algorithmus der jenes Wort aus einem Text herausliest, das am häufigsten vorkommt.
 +
 +  ; Eingabe
 +  : <code>Allein sitzen, allein ruhen, allein gehen. Indem er sich selbst zaehmt, wird er gluecklich allein - allein im Wald.</code>
 +  ; Ausgabe
 +  : <code>allein</code>
 +
 + {{gem/plain#57189171ba8425d3}}
 +
 +++++ Lösung| <code text>
 +/\W+$//g
 +/ξ(\w+)\b(.*?)(ξ+)\1\b/ξ$3$1$2/g
 +/(ξ+)(ξ+)(\w+)\1(\w+)/$1$2$3/g
 +/.*ξ//!
 +/\W+|^/ξ/g
 +</code> ++++
 +
 +==== 4 Zahlenreihe =====
 +
 +Eine Zahlenreihe ist folgend aufgebaut: Man beginnt mit einer beliebigen Zahl.
 +  - Ist die Zahl gerade, kann sie durch zwei geteilt werden
 +  - Ist die Zahl ungerade, wird sie mit drei multipliziert und eins wird dazu addiert
 +  - Ist die Zahl 1 stoppt die Reihe
 +
 +Beispiel: 6, 3, 10, 5, 16, 8, 4, 2, 1
 +
 +Programmiere die Zahlenreihe als Markow Algorithmus für eine beliebige Eingabe in unärer Form. Beispiel:
 +
 +  ; Eingabe
 +  : <code>111</code>
 +  ; Ausgabe
 +  : <code>111
 +1111111111
 +11111
 +1111111111111111
 +11111111
 +1111
 +11
 +1</code>
 +
 + {{gem/plain#f8e4233bf03072ef}}
 +
 +++++ Lösung | <code text>
 +/(^|\n)1$/$&/!              stopt bei 1
 +/(^|\n)(1+)\2$/$&\n$2/      halbiert die zeile
 +/(^|\n)(1+)$/$&\n$2$2$21/   verdreifacht die zeile +1
 +</code> ++++
 +
 +==== 5 Römische Zahlen II =====
 +
 +Schreibe einen Algorithmus der eine Dezimalzahl römisch darstellt. Bespiel:
 +
 +  ; Eingabe
 +  : <code>42</code>
 +  ; Ausgabe
 +  : <code>XXXXII</code>
 +
 + {{gem/plain#0285cb446a1ded53}}
 +
 +++++ Lösung | <code>
 +/IIIII/V/g
 +/VV/X/g
 +/XXXXX/L/g
 +/LL/C/g
 +/CCCCC/D/g
 +/DD/M/g
 +/^α(.*)β//!
 +/9α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1$1$1/
 +/8α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1$1/
 +/7α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1$1/
 +/6α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1$1/
 +/5α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1$1/
 +/4α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1$1/
 +/3α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1$1/
 +/2α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1$1/
 +/1α(.*)β/α$1$1$1$1$1$1$1$1$1$1β$1/
 +/0α(.*)β/α$1$1$1$1$1$1$1$1$1$1β/
 +/$/αIβ/</code>++++
 +
 +==== 6 Römische Zahlen III =====
 +
 +Schreibe einen Algorithmus der zwei römische Zahlen addiert.  Bespiel:
 +
 +  ; Eingabe
 +  : <code>LIII + CLXIII</code>
 +  ; Ausgabe
 +  : <code>CCXVI</code>
 +  
 +
 + {{gem/plain#4e4967079acf84be}}
 +
 +++++ Lösung | <code>
 +- Filtern
 +/[^MDCLXVI]//g
 +- Sortieren
 +/(I)([MDCLXV])/$2$1/g
 +/(V)([MDCLX])/$2$1/g
 +/(X)([MDCL])/$2$1/g
 +/(L)([MDC])/$2$1/g
 +/(C)([MD])/$2$1/g
 +/(D)(M)/$2$1/g
 +- Verdichten
 +/I{5}/V/
 +/V{2}/X/
 +/X{5}/L/
 +/L{2}/C/
 +/C{5}/D/
 +/D{2}/M/
 +</code>
 +
 +Bemerkung: Der Algrithmus prüft nicht ob eine syntaktisch korrekte Addition vorliegt. Er addiert lediglich sämtliche vorhandene Zahlensymbole ''M'', ''D'', ''C'', ''L'', ''X'', ''V'' und ''I'' zu einer einzigen römischen Zahl.
 +++++
 +
 +==== 7 Towers of Hanoi ======
 +
 +{{http://upload.wikimedia.org/wikipedia/commons/0/07/Tower_of_Hanoi.jpeg?200}}
 +\\ cf. [[wpde>Türme von Hanoi]]
 +
 + 
 +Wir haben Scheiben, der Markow-Algorithmus arbeitet aber mit Buchstaben. Um die Lage der Scheiben zu beschreiben, braucht es eine geeignete Codierung:
 +
 +  * {{:markow:tvh1.png|}}
 +  * {{:markow:tvh2.png|}}
 +  * {{:markow:tvh3.png|}}
 +
 + {{gem/plain#05058d36af3ff8ff}}
 +
 +=== Lösungen ====
 +
 +++++ Lösung von Sandro Ackermann | <code text>
 +/α(.*)#([-]+)([bc].*)-\2(c|$)/$1-$2$3#$2$4/
 +/^(a.*)#([bc][#-]+)-(c|$)/α$1-$2#$3/
 +/^(a.*)-(b[#-]+-c)([#-]+)#/α$1#$2$3-/
 +/α(.*)-([-]+)([bc].*)#\2(c|$)/$1#$2$3-$2$4/
 +/α//!
 +</code>++++
 +
 +++++ Lösung von Vincent Tscherter | <code text>
 +/ξ(\w.*)(\w.*)#(-+)(\w.*)-\3$/$1$2-$3$4#$3/
 +/ξ(\w.*)(\w.*)-(-+)(\w.*)#\3$/$1$2#$3$4-$3/
 +/^(\w.*)#(\w.*)-(\w.*)$/ξ$2#$3$1-/
 +/ξ//!
 +</code>
 +
 +Regeln 0 oder 1 wechseln sich mit Regel 2 ab. Regel 2 dient dazu, die kleinste Scheibe eins weiterzugeben (mod 3). Regel 0 resp. Regel 1 führen geweils den einzigen legalen Zug, der die kleinste Scheibe nicht betrifft, aus. ++++
 +
 +==== 8 Vokalen  und Konsonantentrenner ======
 +
 +Erstelle einen Algorithmus, der die Buchstaben in einem Text nach Vokalen und Konsonanten auftrennt.
 +
 +  ; Eingabe
 +  : <code>
 +guten morgen liebe sorgen
 +</code>
 +  ; Ausgabe
 +  : <code>
 +Vokale      : ueoeieeoe
 +Konsonanten : gtnmrgnlbsrgn
 +</code>
 +
 + {{gem/plain#630d637f08f44a9e}}
 +
 +++++ Lösung| <code text>
 +/ //g
 +/([^aeiou])([aeiou])/$2$1/g
 +/([aeiou]+)([^aeiou])/Vokale      : $1\nKonsonanten : $2/ !</code> ++++
 +
 +==== 9 Conway Folge  ======
 +
 +  ; Problemstellung
 +  : Prüfe ob eine Zahl zur Conway-Folge ''1'', ''11'', ''21'', ''1211'', ''111221'', ''312211'', ''13112221'', ''1113213211'', ...  gehört (''✔'') oder nicht (''✘'').
 +  ; Beispiele
 +  : ''111221''→ ''111221 ✔''
 +  : ''111222''→ ''111222 ✘''
 +  ; Idee
 +  : Erstelle beginnend mit ''1'' solange das Folgeelement der Conway-Folge bis dieses der Eingabe entspricht. Falls dabei ein Folgeelement länger als die Eingabe wird kann die Berechnung abgebrochen werden. \\ Da die Länge von Zeichenketten in Markov-Algorithmen nicht direkt verglichen werden kann, wird diese mit dem Hilfssysmbol '':'' in unärer Schreibweise laufend ermittelt. ''1211'' → ''::::1211'' (entspricht der Textlänge 4)
 +
 + {{gem/plain#4a6f10fd886b308f}}
 +
 +++++Antwortzugng| <code>/^1$/$& ✔/
 +/^\d+$/α1βγ$&/
 +
 +/γ(\d)/:$1γ/
 +/(\d)(:+)/$2$1/g
 +
 +/α(\d)\1\1/::3$1α/
 +/α(\d)\1/::2$1α/
 +/α(\d)/::1$1α/
 +
 +/:+(\d+)αβ:+\1γ/$1 ✔/
 +/(:+):+.*β\1(\d+)γ/$2 ✘/
 +/:+(\d+)α/α$1/g</code>
 +
 +==Erläuterungen ==
 +  ; A Initialisierung
 +  : Die erste Regeln prüften den Trivialfall ''1''. Ansonsten kommt die zweite Regel zum Zug welche den eigentlichen Algorithmus initialisiert: \\ ''**111221**'' -> ''//α//**1**//βγ//**111221**''
 +  ; B Eingabelänge
 +  : Über Regel 4 und 5 werden solange '':'' eingefügt und umplatziert bis die Länge der Eingabe unär feststeht. Dabei wandert ''γ'' ans Ende. \\ ''//α//**1**//βγ//**111221**'' -> ''//α//**1**//β//**::::::111221**//γ//''
 +  ; C Folgeelement
 +  : Es folgt über die Regeln 7 bis 9 die Bestimmung des Folgeelements und dessen unären Länge zwischen ''α'' und ''β''. Dabei wandert ''α'' zu ''β''. \\ ''//α//**1**//β//**::::::111221**//γ//'' -> ''::**11**//αβ//**::::::111221**//γ//''
 +  ; D Inhaltsvergleich
 +  : Über Regel 11 wird geprüft ob die beiden Elemente links von ''α'' und ''γ'' identisch sind und ein Element der Conwey-Folge konnte gefunden werden (STOP ✔): \\ ''::::::**111221**//αβ//::::::**111221**//γ//'' -> ''**111221** ✔'' 
 +  : Über Regel 12 prüft der Algorithmus ob das letzte berechnete Folgeelement bereits mehr Zeichen als die zu prüfende Eingabe hat (STOP ✘). \\ ''::::::::**13112221**//αβ//::::::**111222**//γ//'' -> ''**111222** ✘''
 +  : Über Regel 13 wird der nächste Iterationsschritt eingeleitet, so dass anschliessend das nächste Folgeelement berechnet werden kann (WEITER BEI C): \\ ''::::**1211**//αβ//::::::**111221**//γ//'' -> ''//α//**1211**//β//::::::**111221**//γ//''
 +  
 +++++
 +
  

Benutzer-Werkzeuge

Seiten-Werkzeuge

Webseiten-Werkzeuge