Aufgaben

Aus ProgrammingWiki

< AuK < Teile und Herrsche 2 SS10

Archivierte Version vom 2010-04-19T15:51:55+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Übungsaufgaben
2 Lösungen

Übungsaufgaben

Binäre Suche

Aufgabe 1 Binäresuche

Etwas stimmt beim nachfolgenden Code nicht, es giebt einen Fehler, finden, bennenen 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)

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
wenn die unterste teilliste eine Linke-Liste ist entsteht ein Fehler!

(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))) ;Fehler Lokaliesiert irgend wo hier
      (bint-suc (liste-r ls) wert (listen-lang (liste-r ls))); oder eher hier
      ]
     )))

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"]
     )))

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

;;;;;Hilfe anfragen
;;;eingabe hilfe
(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
  "für hilfe: hilfe-bin-suche eingeben / oder: 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 Ziffern: 1, 2, 3, 4 

die Zahlen stehen für die Tipp-stufe")

;;;Random
(define hilfe-zufalls-liste
  "Faule Sau! Schreib selber ne' Liste!!!!")
(define hilfe-zufallsliste
  hilfe-zufalls-liste)

;;;Tipps
(define tipp-a1 "für Tippfaule es giebt 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 (einschließlich) 96 bis 232 hmpf...")
(define tipp-b3 "Die Funktionen mit einer Zahl am ende ihres Namens sind irrelevant, konzentration auf die direkten 

Funktionen der binären Suche")
(define tipp-b4 "der Fehler ist eine Fehlende(!) Zeile")


(define tipp-c1 "gieb ein (bin-suche c2 100)")
(define tipp-c2 "bleib beim wert 100 und versuche die anderen Testlisten und vergleiche die Reaktionen von Dr 

Scheme!")
(define tipp-c3
  "du Willst einen Tip: gieb ein (sort < c2) und untersuche die letzten drei Zahlen")
(define tipp-c4 "ernsthaft... versuch es nochmal, denke darüber 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 Dreie-Elemente-Listen 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 empfehtlen die Datei Herunter zu laden und in Dr.Scheme zu verwenden.

Simabrzo_Fehler-Binaersuche.zip

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:
(bin-suche <listen-l> <zu-suchender-wert>)<br> (lin-suche <listen-l> <zu-suchender-wert>)<br><br></zu-suchender-wert></listen-l></zu-suchender-wert></listen-l>

Eingabe Beispiele:
bsp 1
(bin-suche 10000 7866)
(lin-suche 10000 7866)
bsp 2
(bin-suche 10000 786)
(lin-suche 100000 7866)
bsp 3
(bin-suche 100000 7866)
(lin-suche 10000 786)

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

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:

3812 \cdot 3264
837147 \cdot 479253
34 \cdot 56

Wie sinnvoll ist der Einsatz des Algorithmus bei kleinen Zahlen?

Schnelle Matrixmultiplikation nach STRASSEN

Gegeben sind folgende zwei Matrizen A und B

A=\begin{pmatrix} 3 & 4 & 8 & 9\\ 1 & 5 & 9 & 2\\ 5 & 7 & 4 & 3\\ 2 & 3 & 8 & 1 \end{pmatrix} und

B=\begin{pmatrix} 3 & 2 & 8 & 6\\ 1 & 4 & 9 & 5\\ 7 & 6 & 4 & 3\\ 2 & 9 & 2 & 3 \end{pmatrix}

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

Lösungen

Die Lösungen zu den Aufgaben findet man hier.