====== Aufgaben Serie B =====
{{gem/mgr}}{{gem/pageinfo}}

==== 1 Römische Zahlen I ====
Schreibe einen Algorithmus, der aus einfachen Strichen (unären Zahlen) römische Zahlen (additiv) generiert.

  ; Eingabe
  : <code>IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII</code>
  ; Ausgabe
  : <code>CLXVIIII</code>

 {{gem/plain#74d671347041bc60}}

++++ Lösung  | <code text>/I{5}/V/g
/V{2}/X/g
/X{5}/L/g
/L{2}/C/g
/C{5}/D/g
/D{2}/M/g
</code> ++++

++++ Lösung (inkl Substraktionsregeln) | <code text>/I{1000}/M/
/I{900}/CM/
/I{500}/D/
/I{400}/CD/
/I{100}/C/
/I{90}/XC/
/I{50}/L/
/I{40}/XL/
/I{10}/X/
/I{9}/IX/
/I{5}/V/
/I{4}/IV/</code> ++++

==== 2 Sortierer ====
Schreibe einen Algorithmus, eine Liste unärer Zahlen sortiert.

<code>111111111111111          111111
11111111111              111111111
111111111111       ->    11111111111
111111                   111111111111
111111111                111111111111111</code>

 {{gem/plain#f89eddf83829c294}}

++++ Antwortzugang | <code text>/^(1*)(1+)\n\1$/$1\n$1$2/m
</code> ++++

==== 3 Binäres Inkrementieren ====

Schreibe einen Algorithmus, der eine Binärzahl um eins vergrössert (inkrementiert). Beispiel:

  ; Eingabe
  : <code>110011</code>
  ; Ausgabe
  : <code>110100</code>

 {{gem/plain#22fc6b6f1cea8d0b}}

++++ Lösung | <code text>
/(^|^0+|0)x/1/ ! erste 0 vor x mit 1 ersetzten
/1x/x0/          x wandert nach links und ersetzt 1 mit 0
/$/x/            Ein x am Ende einfügen
</code> ++++
==== 4 Binärer Addierer ====

Schreibe einen Markow Algorithmus der zwei binäre Zahlen addiert. Beispiel

  ; Eingabe
  : <code>101+11001</code>
  ; Ausgabe
  : <code>11110</code>

 {{gem/plain#115cab11f6cc5383}}

++++ Lösung| <code text>
/(^|μ)0*10*10*10*ψ/1ψ1/
/(^|μ)0*10*10*ψ/1ψ0/
/(^|μ)0*10*ψ/ψ1/
/(^|μ)0+ψ/ψ0/
/^ψ0*//!
/^\+μ(.*)/$1ψ/
/([01]?)\+([01]*?)([01]?)(μ|$)/+$2μ$1$3$4/
</code> 

Geht es auch verständlicher? Die Aufgabe ''x+y'' ist kann wie eine schriftliche Addition im Dezimalsystem angegangen werden.

<code> 
    101
+ 11001
-------
=     ?
=======
</code>

Stelle für Stelle werden die Ziffern und der Übertrag addiert; das Resultat und der neue Übertrag wird festgehalten. Linearisiert sehen die Schritte wie folgt aus. Ziffern die verarbeitet kann man weglassen.

<code>
Formatiert                          Kompakt
000111 + 110011 Ü0  =   _______     000111+110011=0  
00011_ + 11001_ Ü1  =   ______0     00011+11001=10
0001__ + 1100__ Ü1  =   _____10     0001+1100=110
000___ + 110___ Ü1  =   ____010     000+110=1010
00____ + 11___  Ü0  =   ___1010     00+11=01010
0_____ + 1_____ Ü0  =   __11010     0+1=011010
______ + ______ Ü0  =   _111010     +=0111010
</code>

Der Algorithmus muss jeweils pro Stelle 8 Fälle unterscheiden, das führt zu den folgenden Regeln:
<code>
/0(\+[01]*)0=0/$1=00/
/0(\+[01]*)0=1/$1=01/
/0(\+[01]*)1=0/$1=01/
/1(\+[01]*)0=0/$1=01/
/0(\+[01]*)1=1/$1=10/
/1(\+[01]*)0=1/$1=10/
/1(\+[01]*)1=0/$1=10/
/1(\+[01]*)1=1/$1=11/
/\+=0*//!</code>
++++
==== 5 Multiplikation====
Schreibe einen Algorithmus der zwei ''*''-getrennte unäre Zahlen miteinander multipliziert. Beispiel:

  ; Eingabe
  : <code>1111*1111</code>
  ; Ausgabe
  : <code>1111111111111111</code>

 {{gem/plain#4de2eef1dc7b82e4}}

++++ Lösung | <code text>
/1\*(1*)/*$1α$1/
/\*1*|α//
</code> ++++
==== 6 Teilen mit Rest ====
Schreibe eine Markow Alogrithmus für die Division zweier '':''-getrennten unären Zahlen //n// und //m//, wobei //m// nicht 0 sein darf. Beispiel:

  ; Eingabe
  : <code>11111111111:111</code>
  ; Ausgabe
  : <code>111R11</code>

 {{gem/plain#c3be9777f5456e76}}

++++ Lösung | <code text>
/(1*):\1ξ/:$1ξ1/         Divisor vom Dividend abziehen
/(1*):.*ξ(1*)/$2R$1/!    Ausgabe formatieren (stop)
/.*:$/div 0!/!           Division durch 0 (stop)
/$/ξ/                    Trennzeichen ξ einfügen
</code> ++++
==== 7 GGT ====
Schreibe einen Alogrithmus, der den grössten gemeinsamen Teiler von zwei ''#''-getrennten unären Zahlen berechnet. Bespiel:

  ; Eingabe
  : <code>111111111111#111111</code>
  ; Ausgabe
  : <code>111111</code>              

 {{gem/plain#89f05a39c4894ae4}}

++++ Lösung | <code text> 
/^(1+)#\1$/$1/ !        ggt(x,x) = x (stop) 
/^(1+)#\1(1+)$/$1#$2/   ggt(x,y) = ggt(x,y-x) falls x < y
/^(1+)(1+)#\1$/$1#$2/   ggt(x,y) = ggt(x-y,y) falls x > y
</code> ++++
==== 8 KGV ====
Schreibe einen Alogrithmus, der das kleinste gemeinsamen Vielfache von zwei ''#''-getrennten unären Zahlen berechnet. Beispiel:

  ; Eingabe
  : <code>111111111111#111111111111111111</code>
  ; Ausgabe
  : <code>111111111111111111111111111111111111</code>

 {{gem/plain#7d894d6197b6ac49}}

++++ Lösung | <code text>
/^(1+)#(1+)ψ(\2+)$/$3/! Dritte Gruppe (Kandidat) ist ein
                        Vielfaches der zweiten Gruppe (STOPP)

/^(1+)#(1+)ψ/$1#$2ψ$1/  Kandidat wird um erste Gruppe 
                        vergrössert

/$/ψ/                   Initialisierung (Kandidat = 0)</code> 
++++
==== 9 Von unär nach binär konvertieren ====

Schreibe einen Markow Algorithmus, der eine unäre Zahl in eine binäre Zahl konvertiert.

++++ Lösung ohne Gruppen (exotisch) | <code text> 
/1β/β0/
/0β/1/
/β/1/
/α1/βα/
/α// !
/1/α1/
//0/ ! </code> ++++

 {{gem/plain#7d221606c8df60d0}}

++++ Lösung mit Gruppen | <code text> 
/^(1+)\1(α|$)/$1α0/    gerade anzahl > 0 & behalte die hälfte
/^1(1+)\1(α|$)/$1α1/ ungerade anzahl > 1 & behalte die hälfte 
/^1α/1/!
/^$/0/!             eingabe war leer > 0</code> ++++

==== 10 Von binär nach unär konvertieren ====

Schreibe einen Markow Algorithmus, der eine binäre Zahl in eine unäre Zahl konvertiert.

 {{gem/plain#6603837ed9f3574f}}

++++ Lösung a| <code text> 
/0ζ(1+)/ζ$1$1/      Abarbeiten eine unbelegten Stelle
/1ζ(1+)ξ/ζ$1$1ξ$1/  Abarbeiten eine belegten Stelle
/^ζ.*ξ//!           Terminierung
/$/ζ1ξ/             Initialisierung</code> 

Erläuterungen: Mit jeder Stelle verdoppelt sich die Wertigkeit ''$1$1''. Fall die Stelle belegt ist, so ist dem aktuellen Wert die Wertigkeit der Stelle anzufügen: ''ξ$1''
++++

++++ Lösung b (exotisch) | <code text> 
/I0/0II/
/1/0I/
/0// </code> ++++