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>


<language>Scheme</language>
=== Aufgabe 3 ===

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

<code hidden>(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)
(time-second (current-time))

(define random-maker
 (let* ((multiplier 48271)
        (modulus 2147483647)
        (apply-congruence
         (lambda (current-seed)
           (let ((candidate (modulo (* current-seed multiplier) modulus)))
             (if (zero? candidate)
                 modulus
                 candidate))))
        (coerce
         (lambda (proposed-seed)
           (if (integer? proposed-seed)
               (- modulus (modulo proposed-seed modulus))
               19860617))))  ;; an arbitrarily chosen birthday
 (lambda (initial-seed)
   (let ((seed (coerce initial-seed)))
     (lambda args
       (cond ((null? args)
              (set! seed (apply-congruence seed))
              (/ (- modulus seed) modulus))
             ((null? (cdr args))
              (let* ((proposed-top
                      (ceiling (abs (car args))))
                     (exact-top
                      (if (inexact? proposed-top)
                          (inexact->exact proposed-top)
                          proposed-top))
                     (top
                      (if (zero? exact-top)
                          1
                          exact-top)))
                (set! seed (apply-congruence seed))
                (inexact->exact (floor (* top (/ seed modulus))))))
             ((eq? (cadr args) 'reset)
              (set! seed (coerce (car args))))
             (else
              (display "random: unrecognized message")
              (newline))))))))

(define random (random-maker (time-nanosecond (current-time))))

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

<code>(define zufallsliste
    (lambda (n)
</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.