AuK/Teile und Herrsche 1 SS10/Aufgaben
Aus ProgrammingWiki
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>
<run id="4bbe828694012">(sort '(12 3 5 29 -4 5 1 9 10)<)</run>
<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>
<run id="4bbe8286947ae">(fibtree 5)</run>
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>
<run id="4bbe828694fa2">(quicksort (zufallsliste 20))</run>
=== 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;
}
<language>Scheme</language>
== Lösungen ==
=== zu Aufgabe 1 ===
Aufsteigende und absteigende Sortierung von Listen! <br>
<code id="4bcc1201e7c21">(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)])))</code>
<run id="4bcc1201e9398">
(sort '(12 3 5 29 -4 5 1 9 10)<)</run>
=== zu Aufgabe 2 ===
Fibonacci-Zahl wird berechnet: <br>
<code id="4bcc1201e83f1">
;Fibonacci-Zahl berechnen
(define fib
(lambda (n)
(cond [(= n 0) 0]
[(= n 1) 1]
[else (+ (fib (- n 1)) (fib (- n 2)))])))
</code>
<run id="4bcc1201e9b61">
(fib 10)
</run>
Fibonaccit Baumdarstellung
<code id="4bcc1201e8bc0">
;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)))])))
</code>
<run id="4bcc1201ea335">
(fibtree 5)
</run>
;(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: <br>
'''''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.'''''
<code>
(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)))))))
</code>
<run>
(quicksort (zufallsliste 20))
</run>
=== zur Zusatzaufgabe ===
Hier solltet Ihr ja mal versuchen den Quellcode zu lesen! Wir Ihr sicher bemerkt habt, war das nicht ganz so einfach. <br>
Nun die Auflösung: <br>
Bei diesem ''unbekannten'' Sortieralgorithmus, handelt es sich um den '''''Gnome-Sort'''''. <br>
Dieser besitzt im ''best-case'' einen Aufwand von <math>\mathcal{O} = n </math>. <br>
Jedoch beim ''worst-case'' einen Aufwand von <math>\mathcal{O} = n^2</math>, somit ist er identisch mit dem '''''Bubble-Sort'''''.