Aufgaben

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Loading


Inhaltsverzeichnis

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


Aufgabe 2

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

Vervollständige die Prozedur!

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!

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!

zu Aufgabe 2

Fibonacci-Zahl wird berechnet:

Fibonaccit Baumdarstellung

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

zu Aufgabe 3

Zufallsliste erzeugen:
Hinweise: Unsere Scheme Library ist nicht Up-to-date. D.h. wir müssen im Netz nachschauen welches "package" noch fehlt, deshalbt steht im folgenden Code die import Anweisung.

zur Zusatzaufgabe

Hier solltet Ihr ja mal versuchen den Quellcode zu lesen! Wir Ihr sicher bemerkt habt, war das nicht ganz so einfach.
Nun die Auflösung:
Bei diesem unbekannten Sortieralgorithmus, handelt es sich um den Gnome-Sort.
Dieser besitzt im best-case einen Aufwand von .
Jedoch beim worst-case einen Aufwand von , somit ist er identisch mit dem Bubble-Sort.

Persönliche Werkzeuge