Aufgaben

Aus ProgrammingWiki

< AuK < Teile und Herrsche 2 SS10

Archivierte Version vom 2010-04-19T16:43:30+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 gibt 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)

!!!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 "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 "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 Tip: gib 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 empfehlen 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.