Aufgaben

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgaben 1.1 Binäre Suche 1.2 Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN 1.3 Schnelle Matrixmultiplikation nach STRASSEN 2 Lösungen

Übungsaufgaben

Binäre Suche

Aufgabe 1 Binäresuche

Etwas stimmt beim nachfolgenden Code nicht, es gibt einen Fehler, finden, benennen und korrigieren sie ihn.

Nur keine Angst, die Übung sieht schlimer aus als sie tatsächlich ist.

Für Hilfe: "hilfe-bin-suche" eingeben
Für Tipps: "tipp-xy" wobei x ein Buchstabe ist und y eine Ziffer
Für die Buchstaben: a, b, c und l (für Lösung)
Die Tipps mit gleichen Buchstaben gehören zusammen
Für die Ziffern: 1, 2, 3, 4 die Ziffern stehen für die Tipp-intensitäts-stufe
(Oder sollten das zumindestens)


!!!Achtung!!! für Tipps und hilfe KEINE klammerung :
>tipp-a1

(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."]))) (define bint-suc (lambda (ls wert i) (cond [(eq? i 2)(isers ls wert)] [(< wert (car (liste-r ls))) (bint-suc (liste-l ls) wert (listen-lang (liste-l ls))) ] [(>= wert (car (liste-r ls))) (bint-suc (liste-r ls) wert (listen-lang (liste-r ls))) ] ))) (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] [else (list-lalng (cdr ls) (+ i 1))]))) (define listen-lang (lambda (ls) (list-lalng ls 0))) (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)))]))) (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))]))) (define ist-er-es (lambda (ls wert) (cond [(eq? ls '()) 'no] [(eq? (car ls) wert) (car ls)] [else (ist-er-es (cdr ls) wert)] ))) (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 [else "Wert nicht Enthalten"] ))) (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 unzulaessig!"])]))) (define einf (lambda (relatio ls wawert) (cond [(eq? ls '())(list wawert)] [(relatio wawert (car ls))(cons wawert ls)] [else (cons (car ls)(einf relatio (cdr ls) wawert))])))

(define d '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 18)) (define c '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19)) (define c2 '(93 2 245 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19)) (define b '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20)) (define b2 '(91 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20)) (define a '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 17 21)) (define z '(93 2 4 86 5 6 3 34 7 38 45 3333 44 87 10 27 53 233 17 25 102 23)) (define t '(1 1 96 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 233 1)) (define hilfe-bin-suche "Eingabe Format: (bin-such <zu-durchsuchende-Liste> <zu-Suchender-Wert>)") (define bin-such-wie? hilfe-bin-suche) (define bin-suche-wie? hilfe-bin-suche) (define hilfe-bin-such hilfe-bin-suche) (define hilfe-fehler "fuer hilfe: hilfe-bin-suche eingeben / oder: tipp-xy wobei x ein Buchstabe ist und y eine Ziffer / fuer die Buchstaben: a, b, c und l(für lösung) die Tipps mit gleichen Buchstaben gehören zusammen / für Ziffern: 1, 2, 3, 4 die Zahlen stehen für die Tipp-stufe") (define hilfe-zufalls-liste "Faule !*?#%! Schreib selber ne' Liste!!!!") (define hilfe-zufallsliste hilfe-zufalls-liste) (define tipp-a1 "fuer Tippfaule es gibt Testlisten: a ,b , b2, c, c2, d, t, z") (define tipp-a2 "> (bin-such a 100) = user break || > (bin-such b 100) = user break || > (bin-such c 100) = Wert nicht Enthalten || > (bin-such c2 100) = user break || > (bin-such d 100) = Wert nicht Enthalten || > (bin-such z 100) = Wert nicht Enthalten || > (bin-such t 100) = Wert nicht Enthalten") (define tipp-a3 "> (bin-such '(1 1 96 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 233 1) 100) = Wert nicht Enthalten || > (bin-such '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20) 100) = user break") (define tipp-a4 "(eq? i 3)(isers... hups...") (define tipp-b1 " alle Listen werden automatisch aufsteigend sortiert ") (define tipp-b2 " Testliste a, Zahlen von (einschliesslich) 96 bis 232 hmpf...") (define tipp-b3 "Die Funktionen mit einer Zahl am ende ihres Namens sind irrelevant, konzentration auf die direkten Funktionen der binaeren Suche") (define tipp-b4 "der Fehler ist eine Fehlende(!) Zeile") (define tipp-c1 "gib ein (bin-suche c2 100)") (define tipp-c2 "bleib beim wert 100 und versuche die anderen Testlisten und vergleiche die Reaktionen von DrScheme!") (define tipp-c3 "du willst einen Tipp: gib ein (sort < c2) und untersuche die letzten drei Zahlen") (define tipp-c4 "ernsthaft... versuch es nochmal, denke darueber nach was mit der 100 in der Testliste c2 passiert, wie läuft das ganze ab?! Tipp aus Gnade: 3-er Liste... hmpf...") (define tipp-l1 "Der Fehler ist eine fehlende Bedingung in einem Cond") (define tipp-l2 "Wenn eine Liste zerteilt wird und die Suche in eine Drei-Elemente-Liste mündet kommt dieser Quellcode nicht mehr aus der Untersuchung dieser drei Elemente Liste heraus!") (define tipp-l3 "der Fehler liegt NICHT an den BESTEHENDEN Bedingungen in bint-suc diese sind Richtig aber in bint-suc fehlt noch eine Bedingung!") (define tipp-l4 "Der Fehler liegt in bint-suc dort fehlt im Cond die Bedingung [(eq? i 3)(isers ls wert)] ziemlich fiess was... ich habe etwa 1h und 45min gebraucht")

Es ist sehr zu empfehlen die Datei herunter zu laden und in DrScheme zu verwenden.

Simabrzo_Fehler-Binaersuche.zip (0.1 MB)

Aufgabe 2
Schritt Vergleich zwischen Linearer Suche und Binärer Suche:

Untersuchen sie fünf verschiedene Eingaben sowohl für die Binäre Suche als auch für die Lineare Suche.
Und untersuchen sie die Unterschiede zwischen den Reaktionen der beiden Funktionen.

In der Formatierung von:
(Binaer-suche <listen-länge> <zu-suchender-Wert>)
(Linear-suche <listen-länge> <zu-suchender-Wert>)

(define Mll (lambda (wert) (Make-lange-liste wert))) (define Make-lange-liste (lambda (wert) (lgn-lst wert 0 wert) )) (define lgn-lst (lambda (wert j i) (cond [(eq? i 0) (cons wert '())] [else (cons j (lgn-lst wert (+ j 1) (- i 1)))] ))) (define Linear-suche (lambda (groesse wert) (lin-such (mll groesse) wert) )) (define Lin-such (lambda (ls wert) (cond [(eq? ls '()) "Bitte KEINE leere Liste eingeben." ] [(eq? wert '()) "Bitte einen Wert zum Suchen eingeben."] [(eq? (car ls) wert) "Best-Case!"] [Else (Linil-zuch ls wert (listen-lang ls) 1)] ))) (define Linil-zuch (lambda (ls wert i j) (cond [(eq? ls '()) (list "Das Element wurden nach" j "Schritten nicht gefunden")] [(eq? (car ls) wert) (list "das Element wurde nach" j "Schritten gefunden")] [(eq? i 0) (list "Das Element wurden nach" j "Schritten nicht gefunden")] [else (Linil-zuch (cdr ls) wert (- i 1) (+ j 1))]))) (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] [else (list-lalng (cdr ls) (+ i 1))]))) (define listen-lang (lambda (ls) (list-lalng ls 0))) (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)))]))) (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))]))) (define ist-er-es (lambda (ls wert) (cond [(eq? ls '()) 'no] [(eq? (car ls) wert) (car ls)] [else (ist-er-es (cdr ls) wert)] ))) (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 k) (cond [(eq? ls '()) "unter Umständen ist ein Fehler aufgetreten! Die End-Liste ist leer!!!"] [(eq? (car ls) wert) (list "Wert gefunden nach" k "Schritten" )] [(eq? (cadr ls) wert) ( list "Wert gefunden nach" k "Schritten" )] [(eq? (caddr ls) wert) (list "Wert gefunden nach" k "Schritten")] [else "Wert nicht Enthalten"] ))) (define Binaer-suche (lambda (groesse wert) (bin-such (mll groesse) 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) (list "Element nach 1 Schritten gefunden (Best Case)")] [else "Element Nicht vorhanden + Liste besteht aus max einem Wert."])] [else (bint-suc (sort < ls) wert (listen-lang ls) 0 )])] [Else "Ausschließlich Zahlen sind als Suchabfrage erlaubt."]))) (define bint-suc (lambda (ls wert i k) (cond [(eq? i 2)(isers ls wert k)] [(eq? i 3)(isers ls wert k)] [(< wert (car (liste-r ls))) (bint-suc (liste-l ls) wert (listen-lang (liste-l ls)) (+ k 1) ) ] [(>= wert (car (liste-r ls))) (bint-suc (liste-r ls) wert (listen-lang (liste-r ls)) (+ k 1)) ] ))) (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)] [(relatio wawert (car ls))(cons wawert ls)] [else (cons (car ls)(einf relatio (cdr ls) wawert))])))

Eingabe Beispiele:
bsp 1
(Binaer-suche 10000 7866)
(Linear-suche 10000 7866)
bsp 2
(Binaer-suche 10000 786)
(Linear-suche 100000 7866)
bsp 3
(Binaer-suche 100000 7866)
(Linear-suche 10000 786)

(Binaer-suche 10000 7866) (Linear-suche 10000 7866)

ausführen

Was stellen sie fest?

(Die Listen-Länge wird benötigt da automatisch eine Exemplarische Liste mit angegebener Länge erstellt wird mit der Eigenschaft das ihre Elemente die Zahlen von 0 bis zur angegebenen Zahl sind.)

Laden sie sich herfür nachfolgende Datei herunter und nutzen sie diese in Dr Scheme.

Simabrzo_Binaeresuche-versus-linearesuche.zip (0.1 MB)

Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN

Lösen Sie, unter Verwendung der Kenntnisse aus Teile und Herrsche 2: Der Algorithmus von KARATSUBA und OFMAN, folgende Rechenaufgaben:

1. 
2. 
3. 

Wie sinnvoll ist der Einsatz des Algorithmus bei kleinen Zahlen?

Schnelle Matrixmultiplikation nach STRASSEN

Gegeben sind folgende zwei Matrizen und

und

Berechnen Sie das Produkt der gegebenen Matrizen mithilfe des Algorithmus von Strassen.

Lösungen

Die Lösungen zu den Aufgaben findet man hier.