Aufgaben

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 "kleinsten zum größten" und vom "größten zum kleinsten"!

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

Aufgabe 2

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

Vervollständige die Prozedur!

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

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

Aufgabe 6

Gegeben ist nachfolgender unbekannter Sortieralgorithmus in Java. Versuchen Sie 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;
}