AuK/Teile und Herrsche 2 SS10/Aufgaben Lösung
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
Diese Seite hält die Lösungen der Aufgaben auf der Seite [[AuK/Teile und Herrsche 2 SS10/Aufgaben]] bereit.
== Lösungen zu den Übungsaufgaben ==
<language>Scheme</language>
<language>Scheme</language>
===Binäre Suche===
<code id="4bcc22e889a76" hidden>
(define not-list?
(lambda wert
(cond
[(list? wert) '#f]
[else '#t])))
;;;;;ermitteln der Länge einer Liste
(define list-lalng1
(lambda (ls i)
(cond
[(not-list? ls)(+ i 1)]
[else (list-lalng (cdr ls) (+ i 1))])))
(define list-lalng
(lambda (ls i)
(cond
[(eq? ls '()) i]
; [number? ls i]
[else (list-lalng (cdr ls) (+ i 1))])))
(define listen-lang
(lambda (ls)
(list-lalng ls 0)))
;;;;;Ermitteln der linken 50% Liste LLL
(define liste-l
(lambda (ls)
(list-linkses ls (/ (listen-lang ls) 2))))
(define list-linkses
(lambda (ls laenge)
(cond
[(< laenge 1) '() ]
[else (cons (car ls) (list-linkses (cdr ls) (- laenge 1)))])))
;;;;;Ermitteln der rechten 50% Liste RRR
(define liste-ra
(lambda (ls)
(list-rechtest ls (modulo (listen-lang ls) 2))))
(define liste-r
(lambda (ls)
(list-rechtest ls (/ (listen-lang ls) 2))))
(define list-rechtest
(lambda (ls laenge)
(cond
[(< laenge 1) ls]
[else (list-rechtest (cdr ls) (- laenge 1))])))
;;;;;BinäreSuche
;Konzeptionel
(define ist-er-es
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[else (ist-er-es (cdr ls) wert)]
)))
;paar-durchsuchung
;isers1 wird nicht genutzt
(define isers1
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[(eq? (cadr ls) wert) (cadr ls)]
[else 'no]
)))
(define isers
(lambda (ls wert)
(cond
[(eq? ls '()) "unter Umständen ist ein Fehler aufgetreten! Die End-Liste ist leer!!!"]
[(eq? (car ls) wert) "Wert Enthalten"]; für bint-suc i = 2
[(eq? (cadr ls) wert) "Wert Enthalten"]; für bint-suc i = 2
[(eq? (cddr ls) wert) "Wert Enthalten"]; für bint-suc i = 3;(!!!! Wichtig ansonsten entsteht eine endlose
sich selbst verarbeitende Schleife in bin-suc im falle das die vorletzte Teil Liste eine 3-er liste ist)
[else "Wert nicht Enthalten"]
)))
;;;;;Binär Such Maske mit sicherheits abfragen
(define bin-suche
(lambda (ls wert)
(bin-such ls wert)))
(define bin-such
(lambda (ls wert)
(cond
[(number? wert)
(cond
[(eq? ls '()) "Fehler! Eingegebene Liste ist leer"]
[(eq? wert '()) "Fehler! Eingegebener Wert ist leer"]
[(list? wert) "Fehler! Der zusuchende Wert soll eine Liste sein!?!"]
[(eq? (cdr ls) '())
(cond
[(eq? (car ls) wert) wert]
[else "Element Nicht vorhanden + Liste besteht aus max einem Wert."])]
[else (bint-suc (sort < ls) wert (listen-lang ls))])]
[Else "Ausschließlich Zahlen sind als Suchabfrage erlaubt."])))
;ls = Liste
;wert = gesuchter Wert
;i = länge der liste
;;;tatsächlicher binär Sucher
;wenn die unterste teilliste eine Linke-Liste ist entsteht ein Fehler!
(define sort
(lambda (rel ls)
(cond
[(eq? '() ls)'()]
[(eq? '() (cdr ls)) ls]
[(Cond
[(eq? rel <)(einf < (sort rel (cdr ls))(car ls) )]
[(eq? rel >)(einf > (sort rel (cdr ls))(car ls) )]
[else "Relation unzulässig!"])])))
(define einf
(lambda (relatio ls wawert)
(cond
[(eq? ls '())(list wawert)]
;[(eq? wawert (car ls) ) (cons sortls wawert)]
[(relatio wawert (car ls))(cons wawert ls)]
[else (cons (car ls)(einf relatio (cdr ls) wawert))])))
;;;;; TESTLISTEN ;;;;;
;testliste "d" mit länge 18
(define d
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 18))
;testliste "c" mit länge 19
(define c
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19))
;testliste "c" mit länge 19
(define c2
'(93 2 245 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19))
;testliste "b" mit länge 20
(define b
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20))
;testliste "b2" mit länge 20
(define b2
'(91 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20))
;testliste "a" mit länge 21
(define a
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 17 21))
;testliste "z" mit länge 23
(define z
'(93 2 4 86 5 6 3 34 7 38 45 3333 44 87 10 27 53 233 17 25 102 23))
;genervt-von-unlogischen-Fehlern-sei-testliste "t" mit länge 20
(define t
'(1 1 96 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 233 1))
</code>
<code id="4bcc227d3c36b">
(define bint-suc
(lambda (ls wert i)
(cond
[(eq? i 2)(isers ls wert)]
[(eq? i 3)(isers ls wert)] ;<-- Diese Zeile fehlte!
[(< wert (car (liste-r ls)))
(bint-suc (liste-l ls) wert (listen-lang (liste-l ls)))
]
[(>= wert (car (liste-r ls))) ;Fehler Lokaliesiert irgend wo hier
(bint-suc (liste-r ls) wert (listen-lang (liste-r ls))); oder eher hier
]
)))
</code>
<eval id="4bcc227d3cb34">
</eval>
===Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN===
*<math>3812 \cdot 3264</math>
<math>a=3802\Rightarrow a_1=38 \textrm{ und }a_0=12\\
b=3264\Rightarrow b_1=32 \textrm{ und }b_0=64</math>
Damit berechnet man <math>r</math>, <math>s</math>und <math>t</math>:
<math>
r=a_{1}\cdot b_{1}=38\cdot32=1216\\
s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})=-832\\
t=a_{0}\cdot b_{0}=768\\
\\
a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t=1216\cdot10^4+(1216+768+832)\cdot10^2+768=\underline{\underline{12442368}}
</math>
*<math>837147 \cdot 479253</math>
<math>a=837147\Rightarrow a_1=837 \textrm{ und }a_0=147\\
b=479253\Rightarrow b_1=479 \textrm{ und }b_0=253</math>
Damit berechnet man <math>r</math>, <math>s</math>und <math>t</math>:
<math>
r=a_{1}\cdot b_{1}=38\cdot32=400923\\
s=(a_{0}-a_{1})\cdot(b_{0}-b_{1})=155940\\
t=a_{0}\cdot b_{0}=37191\\
\\
a\cdot b = r\cdot z^{n}+(r+t-s)z^{\frac{n}{2}}+t=400923\cdot10^6+(400923+155940-37191)\cdot10^3+155940=\underline{\underline{401205211191}}
</math>
*<math>34 \cdot 56</math>
===Schnelle Matrixmultiplikation nach STRASSEN===
Gegeben sind die zwei Matrizen <math>A</math> und <math>B</math> mit:
<math>
A=\begin{pmatrix}
3 & 4 & 8 & 9\\
1 & 5 & 9 & 2\\
5 & 7 & 4 & 3\\
2 & 3 & 8 & 1
\end{pmatrix}</math> und
<math>B=\begin{pmatrix}
3 & 2 & 8 & 6\\
1 & 4 & 9 & 5\\
7 & 6 & 4 & 3\\
2 & 9 & 2 & 3
\end{pmatrix}</math>
Die Matrizen zerlegt man nach folgendem Muster in Teilmatrizen:
<math>
C=A\cdot B=
\begin{pmatrix}
A_{1,1} & A_{1,2}\\
A_{2,1} & A_{2,2}
\end{pmatrix}\cdot
\begin{pmatrix}
B_{1,1} & B_{1,2}\\
B_{2,1} & B_{2,2}
\end{pmatrix}
=\begin{pmatrix}
C_{1,1} & C_{1,2}\\
C_{2,1} & C_{2,2}
\end{pmatrix}
</math>
Daraus ergeben sich die 8 Teilmatrizen:
<math>
A_{1,1}=\begin{bmatrix}3 & 4\\1 & 5\end{bmatrix}\text{, } A_{1,2}=\begin{bmatrix}8 & 7\\9 & 2\end{bmatrix}\text{, } A_{2,1}=\begin{bmatrix}5 & 7\\2 & 3\end{bmatrix}\text{, } A_{2,2}=\begin{bmatrix}4 & 3\\8 & 1\end{bmatrix}\\
B_{1,1}=\begin{bmatrix}3 & 2\\1 & 4\end{bmatrix}\text{, } B_{1,2}=\begin{bmatrix}8 & 6\\9 & 5\end{bmatrix}\text{, } B_{2,1}=\begin{bmatrix}7 & 6\\2 & 9\end{bmatrix}\text{, } B_{2,2}=\begin{bmatrix}4 & 3\\2 & 3\end{bmatrix}
</math>
Damit lassen sich <math>M_{1}</math> bis <math>M_{7}</math> berechnen:
<math>
M_{1}=(A_{1,1}+A_{2,2})\cdot(B_{1,1}+B_{2,2})=\begin{pmatrix}70 & 84\\81 & 87\end{pmatrix}\\
M_{2}=(A_{2,1}+A_{2,2})\cdot B_{1,1}=\begin{pmatrix}37 & 58\\34 & 36\end{pmatrix}\\
M_{3}=A_{1,1}\cdot(B_{1,2}-B_{2,2})=\begin{pmatrix}40 & 17\\39 & 13\end{pmatrix}\\
M_{4}=A_{2,2})\cdot (B_{2,1}-B_{1,1})=\begin{pmatrix}19 & 31\\33 & 37\end{pmatrix}\\
M_{5}=(A_{1,1}+A_{1,2})\cdot B_{2,2}=\begin{pmatrix}66 & 66\\54 & 51\end{pmatrix}\\
M_{6}=(A_{2,1}-A_{1,1})\cdot(B_{1,1}+B_{1,2})=\begin{pmatrix}52 & 43\\-9 & -10\end{pmatrix}\\
M_{7}=(A_{1,2}-A_{2,2})\cdot(B_{2,1}+B_{2,2}=\begin{pmatrix}60 & 84\\15 & 21\end{pmatrix})
</math>
Danach kann man die 4 Teilmatrizen von <math>C</math> durch Addition bzw. Subtraktion berechnen.
<math>
C_{1,1}=M_1 + M_4 - M_5 + M_7=\begin{pmatrix}83 & 133\\75 & 94\end{pmatrix}\\
C_{1,2}=M_3 + M_5=\begin{pmatrix}106 & 83\\93 & 64\end{pmatrix}\\
C_{2,1}=M_2 + M_4=\begin{pmatrix}56 & 89\\67 & 73\end{pmatrix}\\
C_{2,2}=M_1 - M_2 + M_3 + M_6=\begin{pmatrix}125 & 86\\77 & 54\end{pmatrix}
</math>
Durch Zusammensetzen der Teilmatrizen zur Ergebnismatrix <math>C</math> ergibt sich das Ergebnis der Rechnung:
<math>C=\begin{pmatrix}C_{1,1} & C_{1,2}\\C_{2,1} & C_{2,2}\end{pmatrix}=
\begin{pmatrix}
83 & 133 & 106 & 83\\
75 & 94 & 93 & 64\\
56 & 89 & 125 & 86\\
67 & 73 & 77 & 54
\end{pmatrix}</math>