exorciser.ch

exorciser.ch

Webseiten-Werkzeuge

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

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:serieb [2013/11/18 23:46] – [14 Binärer Addierer] Tscherter, Vincentmarkow:serieb [2024/03/03 22:36] (aktuell) – Tscherter, Vincent
Zeile 1: Zeile 1:
 +
 +====== 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> ++++
 +
  

Benutzer-Werkzeuge

Seiten-Werkzeuge

Webseiten-Werkzeuge