AuK/Teile und Herrsche 1 SS10/Aufgaben

Wiki-Quelltext dieser Seite.

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

Hier habt Sie die Möglichkeit etwas zu Üben und sich im Thema zu festigen.


=== 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="4bbe828692039" hidden>(define (insert x l rel)
  (cond [(empty? l) (list x)]
        [(rel x (car l)) (cons x l)]
        [else (cons (car l) (insert x (cdr l) rel))]))
(define (sort l rel)
  (cond [(empty? l) empty]
        [else (insert (first l) (sort (rest l) rel) rel)]))</code>

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

<eval id="4bbe828694012">(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="4bbe82869303b">(define (fibtree n)
</code>

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


=== Aufgabe 3 ===

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

<code id="4bbe82869380e">(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="4bbe828694fa2">(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]