Aufgaben

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Computerübung 1.1 Aufgabe 1 1.2 Aufgabe 2 1.3 Aufgabe 3 1.4 Aufgabe 4 1.5 Aufgabe 5 1.6 Zusatzaufgabe 2 Lösungen 2.1 zu Aufgabe 1 2.2 zu Aufgabe 2 2.3 zu Aufgabe 3 2.4 zur Zusatzaufgabe

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

(define insert (lambda (x l rel) (define sort (lambda (l rel)

(sort '(12 3 5 29 -4 5 1 9 10)<)

ausführen

Aufgabe 2

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

Vervollständige die Prozedur!

(define fibtree (lambda (n)

(fibtree 5)

ausführen

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!

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

(define zufallsliste (lambda (n)

(quicksort (zufallsliste 20))

ausführen

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!

(define insert (lambda (x l rel) (cond [(eq? '() l) (list x)] [(rel x (car l)) (cons x l)] [else (cons (car l) (insert x (cdr l) rel))]))) (define sort (lambda (l rel) (cond [(eq? '() l) ()] [else (insert (car l) (sort (cdr l) rel) rel)])))

(sort '(12 3 5 29 -4 5 1 9 10)<)

ausführen

zu Aufgabe 2

Fibonacci-Zahl wird berechnet:

;Fibonacci-Zahl berechnen (define fib (lambda (n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fib (- n 1)) (fib (- n 2)))])))

(fib 10)

ausführen

Fibonaccit Baumdarstellung

;Baumdarstellung der Fibonacci-Zahl 5 (define fibtree (lambda (n) (cond [(= n 0) (list 0)] [(= n 1) (list 1)] [else (list n (fibtree (- n 2)) (fibtree (- n 1)))])))

(fibtree 5)

ausführen

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

(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)))))))) (define zufallsliste (lambda (n) (cond ((zero? n) ()) (else (cons (random 1000) (zufallsliste (- n 1)))))))

(quicksort (zufallsliste 20))

ausführen

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.