Aufgaben Serie C
1 X-Mas Tree
Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechenden Weihnachtsbaum zeichnet:
- Eingabe
-
ooooooo
- Ausgabe
-
o
ooo
ooooo
ooooooo
o
Die Grösse des Baumes ist abhängig von der Eingabe.
Erweiterung 1: Baumstrunk
Erweiterung 2: Baumschmuck
Loading ⌛
Lösung von Roli
/^(\s*)(o*)oo/ $1$2\n$&/
/^( *o)((\n *o*)*)$/$1$2\n$1/!
Lösung von Tscherter
/^( *oo?)\n[o\s]*/$&\n$1/!
/^( *o*)oo/ $1\n$&/
2 Pascalsche Dreieck
Erstelle einen Algorithmus der aus der folgenden Eingabe eine entsprechendes binäres Pascalsche Dreieck zeichnet.
Eingabe
oooooooooooooooooooooooooooooooooooooooo
o
o
o
o
o
o
o
o
o
o
Ausgabe
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
Loading ⌛
Lösung (TSC)
/α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/
3 Häufigste Wort in einem Text
Erstelle einen Algorithmus der jenes Wort aus einem Text herausliest, das am häufigsten vorkommt.
- Eingabe
-
Allein sitzen, allein ruhen, allein gehen. Indem er sich selbst zaehmt, wird er gluecklich allein - allein im Wald.
- Ausgabe
-
allein
Loading ⌛
Lösung
/\W+$//g
/ξ(\w+)\b(.*?)(ξ+)\1\b/ξ$3$1$2/g
/(ξ+)(ξ+)(\w+)\1(\w+)/$1$2$3/g
/.*ξ//!
/\W+|^/ξ/g
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
-
111
- Ausgabe
-
111
1111111111
11111
1111111111111111
11111111
1111
11
1
Loading ⌛
Lösung
/(^|\n)1$/$&/! stopt bei 1
/(^|\n)(1+)\2$/$&\n$2/ halbiert die zeile
/(^|\n)(1+)$/$&\n$2$2$21/ verdreifacht die zeile +1
5 Römische Zahlen II
Schreibe einen Algorithmus der eine Dezimalzahl römisch darstellt. Bespiel:
- Eingabe
-
42
- Ausgabe
-
XXXXII
Loading ⌛
Lösung
/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β/
6 Römische Zahlen III
Schreibe einen Algorithmus der zwei römische Zahlen addiert. Bespiel:
- Eingabe
-
LIII + CLXIII
- Ausgabe
-
CCXVI
Loading ⌛
Lösung
- 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/
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
cf. 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:
Loading ⌛
Lösungen
Lösung von Sandro Ackermann
/α(.*)#([-]+)([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/
/α//!
Lösung von Vincent Tscherter
/ξ(\w.*)(\w.*)#(-+)(\w.*)-\3$/$1$2-$3$4#$3/
/ξ(\w.*)(\w.*)-(-+)(\w.*)#\3$/$1$2#$3$4-$3/
/^(\w.*)#(\w.*)-(\w.*)$/ξ$2#$3$1-/
/ξ//!
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
-
guten morgen liebe sorgen
- Ausgabe
-
Vokale : ueoeieeoe
Konsonanten : gtnmrgnlbsrgn
Loading ⌛
Lösung
/ //g
/([^aeiou])([aeiou])/$2$1/g
/([aeiou]+)([^aeiou])/Vokale : $1\nKonsonanten : $2/ !
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)
Loading ⌛
Antwortzugng
/^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
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γ