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 "aufsteigend" und vom "absteigend"!

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

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;
}

Lösungen

zu Aufgabe 1

Aufsteigende und absteigende Sortierung von Listen!

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

zu Aufgabe 2

Fibonacci-Zahl wird berechnet:

<eval id="4bcc1201e9b61"> (fib 10) </eval>

Fibonaccit Baumdarstellung

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

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