Aufgaben Serie B

/I{5}/V/g
/V{2}/X/g
/X{5}/L/g
/L{2}/C/g
/C{5}/D/g
/D{2}/M/g

/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/

/^(1*)(1+)\n\1$/$1\n$1$2/m

/(^|^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

/(^|μ)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/

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

 
    101
+ 11001
-------
=     ?
=======

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.

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

Der Algorithmus muss jeweils pro Stelle 8 Fälle unterscheiden, das führt zu den folgenden Regeln:

/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*//!

/1\*(1*)/*$1α$1/
/\*1*|α//

/(1*):\1ξ/:$1ξ1/         Divisor vom Dividend abziehen
/(1*):.*ξ(1*)/$2R$1/!    Ausgabe formatieren (stop)
/.*:$/div 0!/!           Division durch 0 (stop)
/$/ξ/                    Trennzeichen ξ einfügen

/^(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

/^(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)

/1β/β0/
/0β/1/
/β/1/
/α1/βα/
/α// !
/1/α1/
//0/ ! 

/^(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

/0ζ(1+)/ζ$1$1/      Abarbeiten eine unbelegten Stelle
/1ζ(1+)ξ/ζ$1$1ξ$1/  Abarbeiten eine belegten Stelle
/^ζ.*ξ//!           Terminierung
/$/ζ1ξ/             Initialisierung

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

/I0/0II/
/1/0I/
/0//