Aufgaben

Aus ProgrammingWiki

< AuK < Teile und Herrsche 2 SS10

Archivierte Version vom 2010-04-19T13:55:39+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Übungsaufgaben
2 Lösungen

Übungsaufgaben

Binäre Suche

Aufgabe 1 Binäresuche

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

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