AuK/Teile und Herrsche 1 SS10/Aufgaben

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== Computerübung ==

Hier habt Ihr die Möglichkeit, zu zeigen, dass Ihr unser Thema verstanden habt! :-)

=== Aufgabe 1 ===

Erstellen Sie mit Hilfe von Dr.Scheme eine Prozedur, welche es ermöglicht, Listen zu sortieren vom "kleinsten zum Größten" und vom "Größten zum kleinsten"!

<code id="4bbdf4d828399">(define (insert x l rel)
</code>

<eval id="4bbdf4d82934e">(sort '(12 3 5 29 -4 5 1 9 10) <)
(sort '(12 3 5 29 -4 5 1 9 10) >)</eval>

=== Aufgabe 2 ===

Wie lassen sich mit Hilfe einer Scheme-Prozedur, die Fibonacci Zahlen als Baum darstellen?

Vervollständigen Sie die Prozedur!
<code id="4bbdf4d828b68">(define (fibtree n)
</code>

<eval id="4bbdf4d829b08">(fibtree 5)</eval>


=== Aufgabe 3 ===

Schreiben Sie eine Scheme-Prozedur, die eine Zufallsliste erzeugt und diese sortiert!

<code id="4bbdf648df914">(define tl
  (lambda (ls v)
    (if (null? ls)
        (values '() '())
        (call-with-values
         (lambda () (tl (cdr ls) v))
         (lambda (li re)
           (let ((x (car ls)))
             (if (< x v)
                 (values (cons x li) re)
                 (values li (cons x re)))))))))

(define (zufallsliste n)


(define quicksort
  (lambda (ls)
    (if (or (null? ls)(null? (cdr ls)))
        ls
        (let ((v (car ls)))
          (call-with-values
           (lambda () (tl (cdr ls) v))
           (lambda (li re)
              (append
               (quicksort li)
               (list v)
               (quicksort re))))))))</code>

<eval id="4bbdf648e00c2">(quicksort (zufallsliste 20))</eval>

=== Aufgabe 4 ===

Schreiben Sie eine Klasse in Java zum Aufruf von Quicksort. Bauen Sie die math.random() Methode  für Zufallszahlen bis 10000 ein. Beachten Sie, das eine Wertanzahl eingeben können sollte( Stichwort read()). Der Code von dieser Seite darf und sollte verwendet werden!

=== Aufgabe 5 ===

Schreiben Sie ähnlich Aufgabe 4 , eine Klasse zum Aufruf von Mergesort.

== Zurück zur Hauptseite ==
*[http://www.michael-hielscher.de/wiki/index.php?title=Divide_and_Conquer_1 Divide and Conquer 1]