AuK/Teile und Herrsche 1 SS10/Aufgaben

Wiki-Quelltext dieser Seite.

<language>Scheme</language>


== Computerübung ==

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


=== Aufgabe 1 ===

Erstelle mit Hilfe von Dr.Scheme eine Prozedur, die es ermöglicht, Listen zu sortieren vom "aufsteigend" und vom "absteigend"!

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

(define sort
  (lambda (l rel)
</code>

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

<language>Scheme</language>
=== Aufgabe 2 ===

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

Vervollständige die Prozedur!
<code id="4bbe82869303b">(define fibtree
  (lambda (n)
</code>

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

Hier eine mögliche Ausgabe - es handelt sich um das gleiche Ergebnis!

 Unformatierter Baum
 ;(5 (3 (1) (2 (0) (1))) (4 (2 (0) (1)) (3 (1) (2 (0) (1)))))

 Formatierter Baum
 ;(list 5
 ;(list 3 (list 1)
 ;        (list 2 (list 0) (list 1)))
 ;(list 4 (list 2 (list 0) (list 1))
 ;        (list 3 (list 1) (list 2 (list 0) (list 1)))))

=== Aufgabe 3 ===

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

<code id="4bbef7047beb8" 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 id="4bbef7047c688">(define zufallsliste
    (lambda (n)
</code>

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

=== Aufgabe 4 ===

Schreibe eine Klasse in Java zum Aufruf von Quicksort. Baue die '''math.random( )''' Methode  für Zufallszahlen bis 10000 ein. Beachte, dass eine Wertanzahl eingegeben werden soll (Stichwort '''read( )'''). Der Code von dieser Seite darf und sollte verwendet werden!

=== Aufgabe 5 ===

Schreibe, ähnlich der Aufgabe 4, eine Klasse zum Aufruf von Mergesort.

=== Zusatzaufgabe ===

Gegeben ist nachfolgender unbekannter Sortieralgorithmus in Java. Versuche den Aufwand des Verfahrens abzuschätzen (worst-case und best-case).  

 static int[] sortiere( int[] a) { 
      for ( int index = 1; index < a.length; ) { 
         if ( a[index - 1] <= a[index] ) { 
            ++index; 
         } else { 
            int tempVal = a[index]; 
            a[index] = a[index - 1]; 
            a[index - 1] = tempVal; 
            --index; 
            if ( index == 0 ) { 
               index = 1; 
            }           
         } 
      } 
      return a;
 }