P1-WS04-MusterLoesung10.txt

2007-11-05T05:50:15Z

81.177.14.26:

<pre>
P1 Übungen WS2004/2005
Musterlösung 10 (Martin Burmester)

Aufgabe 1.)

; (a)

(define (ostersonntag j)
(let*
; 1. Argument vom let*. Berechnen wir a,b,c,d,e,m,

((a (remainder j 19) )
(b (remainder j 4) )
(c (remainder j 7) )
(m (cond ((<= 1800 j 1899) 23)
((<= 1900 j 2099) 24)
((<= 2100 j 2199) 24)
(else (error "year out of range!"))))
(n (cond ((<= 1800 j 1899) 4)
((<= 1900 j 2099) 5)
((<= 2100 j 2199) 6)
(else (error "year out of range!"))))
(d (remainder (+ (* 19 a) m)
30))
(e (remainder (+ (* 2 b)
(* 4 c)
(* 6 d)
n)
7))
(april_day0 (+ d e -9))
(april_day (cond ((= april_day0 26) 19)
((and (= april_day0 25)
(= d 28)
(= e 6)
(>= a 10))
18)
(else april_day0)))
(march_day (+ 22 d e)))

; 2. Argument vom let*. Nun haben wir alles!
;
; 1. Versuch:
; (list march_day 'maerz j 'oder april_day 'april j)
; bekommen wir komisches datum, z.B. (-8 april ...) oder (54 maerz ...)
;
; 2. Versuch
; kontrolliere ob april_day und march_day gültig sind...

(if (> march_day 31) (list april_day 'April j)
(list march_day 'Maerz j))))

; (b)

;;
;; Jedem Monat ist die Anzahl der Tage im Monat und der
;; Folgemonat zugeordnet.
;;
(define maerz (cons 31 'april))
(define april (cons 30 'mai))
(define mai (cons 31 'juni))
(define juni (cons 30 'juli))

(define tage-im-monat car)
(define folgemonat cdr)

;;
;; Fuegt zu einem Datum d eine Anzahl von
;; Tagen t hinzu und gibt ein gueltiges
;; Datum zurück
;;
(define (datum+tage d t)
(define (korrigiere-datum d)
(let ((tag (car d))
(monat (eval (cadr d)))
(jahr (caddr d)))
(if (> tag (tage-im-monat monat))
(korrigiere-datum (list (- tag (tage-im-monat monat))
(folgemonat monat)
jahr))
d)))
(korrigiere-datum (cons (+ (car d) t)
(cdr d))))

(define (himmelfahrt j)
(datum+tage (ostersonntag j) 39))

; (c)

(define (pfingsten j)
(datum+tage (ostersonntag j) 49))

; Tes

P1-WS04-MusterLoesung12.txt

2006-12-12T20:42:07Z

81.177.14.26:

<pre>
;; Musterloesung Aufgabenblatt 12
;; P1 WiSe 04/05
;; Henrich Pöhls
;; Daniel Schreckling

;; In diesem Aufgabenblatt werden Funktionen aus der Datei tools.scm
;; verwendet. Deshalb wird sie an dieser Stelle eingebunden.

(load "tools.scm")

;; Aufgabe 1

;; 1 a) Funktionen höherer Ordnung sind Funktionen, deren
;; Argumente bzw. Funktionsparameter wiederum Funktionen darstellen
;; oder deren Rückgabewerte Funktionen sind.

;; So muß z.B. "map" eine Funktion als Parameter haben und ist daher von
;; höherer Ordnung. Dagegen ist "eq" keine Funktion höherer Ordnung,
;; obwohl man den Aufruf "(eq + -)" ausführen kann (Ergebnis #f).

;; 1 b)

;; "map" ist eine Funktion höherer Ordnung, weil der erste Parameter eine
;; einstellige Funktion sein muß.

;; "plus-oder-minus" ist eine Funktion höherer Ordnung, weil der
;; Rückgabewert immer - oder + ist.

;; "pepper" ist eine Funktion höherer Ordnung, weil das erste Argument "f"
;; eine zweistellige Funktion sein muß.

;; "my-tan" ist keine Funktion höherer Ordnung, weil sowohl das Argument
;; als auch der Rückgabewert Zahlen sein müssen.

;; 1 c)

;; Die globale Umgebung wird verwendet, um das Argument "3" des
;; Funktionsaufrufes zu reduzieren. (Da es eine Zahl ist, findet keine
;; Reduktion statt.) Der Wert des Symbols pepper wird ebenfalls in der
;; globalen Umgebung aufgelöst zu dem Lambda-Ausdruck

;; (lambda (f arg1) (lambda (arg2) (f arg1 arg2)))

;; Bei der Anwendung dieser anonymen Funktion auf + und 1 entsteht eine
;; neue Umgebung mit den Bindungen f = + und arg1 = 1. Nach der
;; Funktionanwendung entsteht also der Ausdruck

;; (lambda (arg2) (+ 1 arg2))

;; Erst bei der Anwendung dieser anonymen Funktion auf das ursprüngliche
;; Argument 3 entsteht eine weitere Umgebung, in der die Bindung arg2 = 3
;; gilt. Der Gesamtausdruck wird also reduziert zu

;; (+ 1 3)

;; und weiter zum Ergebnis 4.

;; 1 d)

;; (map (curry * 2) '(1 2 3))
;;
;; Jedes Element der Liste wird mit zwei multipliziert.
;;
;; Ergebnis: (2 4 6)

;; (map cons '(1 2 3) '(1 2 3))
;;
;; Aus den Elementen beider Listen werden jeweils paarweise und in der
;; entsprechenden Reihenfolge Paare gebildet. Hierfür wird der
;; "Paarkonstruktor" cons verwendet
;;
;; Ergebnis: ((1 . 1) (2 . 2) (3 . 3))

;; (filter pair? '((a b ) () 1 (())))
;;
;; filter pred list => list
;;
;; Filtert genau die Elemente aus der übergebenen Liste, die das
;; Prädikat pred erfüllen. Hier bedeutet dies, dass genau die Elemente
;; herausgefiltert werden, die vom Typ pair sind.
;;
;; Da die leere Liste '()' und die Zahl '1' nicht vom Typ pair sind,
;; werden sie nicht in die Ergebnismenge übernommen.
;;
;; (()) ist im Unterschied zu () vom Typ pair?, da (()) eine abgekürzte
;; Schreibweise für ( () . () ) ist.
;;
;; Ergebnis: ((a b) (()))

;; Aufgabe 2)

;; Zum Testen unserer Funktionen verwenden
;; wir folgende Liste

(define xs '(1 -2 -3 4 5 6 -7 8 -9 10))

;; 2 a)

;; Verwende die Funktion reduce

(reduce
(lambda (x y)
;; Summiere die Absolutbeträge zweier Zahlen
(+ (abs x) (abs y))
) ;; lambda
xs 0
) ;; reduce

;; Eine zweite mögliche Lösung unter Verwendung einer
;; rekursiven Funktion wäre:

;; Rekursionsabschluss: Sollte die Liste die
;; Länge null haben, so ist die Summe der
;; Absolutbeträge auch null

;; Rekursionsschritt: Addiere zum Absolutbetrag
;; des ersten Elementes die Summe der Absolutbeträge
;; der Restliste

(define (sum-abs xs)
(cond ((null? xs) 0)
(else (+ (abs(car xs))
(sum-abs (cdr xs))
)
)
)
)

;; Ergebnis bei Anwendung auf unsere Beispielliste: 55

;; 2 b)

;; Verwende die Funktion Filter und selektiere alle
;; Elemente der Liste, die kleiner 0 sind

(filter
;; #t, wenn x kleiner 0 ist, #f sonst
(lambda (x) (< x 0))
;; die Liste
xs
) ;; filter

;; Verwendet man außerdem curry, so wird die
;; Lösung noch kürzer. Beachte: bei dieser
;; Lösung muss aufgrund der Argumentpositionen
;; > verwendet werden.

(filter (curry > 0) xs)

;; Alternative wäre:

(filter (rcurry < 0) xs)

;; Ergebnis bei Anwendung auf unsere Beispielliste:
;; (-2 -3 -7 -9)

;; 2 c)

;; Zunächst werden alle Zahlen aus xs gefiltert, die ungerade sind,
;; also das Prädikat odd? erfüllen. Die Länge der resultierenden
;; Liste entspricht dann der Anzahl der ungeraden Zahlen in der Liste xs.

(length (filter odd? xs))

;; Ergebnis bei Anwendung auf unsere Beispielliste: 5

;; 3)

;; Hier wird ein Beispiellagerstand definiert

(define *Lagerbestand*
'((Gummibaerchen . 100)
(Lakritzschnecken . 30)
(Wundertueten . 300)
(Brausepulver . 1000)
(Schokolade . 350)
(Zahnpasta . 30)))

;; 3 a)

;; anzahl-von artikel => Anzahl

;; Bestimmt zum Namen eines Artikels die Anzahl
;; des Artikels, die im *Lagerbestand* aufgeführt
;; ist.

(define (anzahl-von artikel)
;; hole den Wert zum ersten Element in der Liste
(cdar
;; filtere genau die Elemente, deren Schlüssel
;; gleich dem Argument artikel ist
(filter
;; #t, wenn der Schlüssel von x = artikel, #f sonst
(lambda (x) (eqv? (car x) artikel))
*Lagerbestand*
) ;; filter
) ;; cdar
)

;; Verwendet man die Operation assq für assoziative
;; Listen, so erhält man folgende Lösung:

(define (anzahl-von2 artikel)
(cdr (assq artikel *Lagerbestand*)))

;; Ergebnis bei Anwendung auf unseren Beispielbestand:

;; > (anzahl-von 'Lakritzschnecken)
;; 30
;; > (anzahl-von2 'Lakritzschnecken)
;; 30

;; Hier wird natürlich davon ausgegangen, dass die
;; assoziative Liste konsistent ist und jeder Schlüssel
;; nur einmal vorkommt. Sollte dies nicht so sein, so
;; kann man zusätzlich über die Liste der Paare summieren
;; und man erhält folgende Lösung:

(define (anzahl-von3 artikel)
;; summiere die Elemente der Liste
(reduce +
;; Reduziere anhand von cdr die Elemente dieser
;; Liste (die Artikel) nur auf deren Anzahl
(map cdr
;; Ermittle alle Elemente von *Lagerbestand2*
;; deren Schlüsselwert gleich dem Argument artikel ist
(filter (lambda (x) (eqv? (car x) artikel)) *Lagerbestand2*)
) ;; map
0) ;; reduce
)

;; mit folgendem nicht ganz konsistenten Lagerbestand

(define *Lagerbestand2*
'((Gummibaerchen . 100)
(Lakritzschnecken . 30)
(Lakritzschnecken . 32)
(Wundertueten . 300)
(Brausepulver . 1000)
(Schokolade . 350)
(Zahnpasta . 30)))

;; erhält man für
;; > (anzahl-von3 'Lakritzschnecken)
;; 62

;; 3 b)

;; Definiere zunächst eine Hilfsfunktion, die
;; zu zwei Artikeln, den Artikel ermittelt, der
;; die kleinere Anzahl aufweist. Bei Gleichheit
;; wird der erste Artikel zurückgegeben

(define (min_artikel x y)
(cond ((<= (cdr x) (cdr y)) x)
(else y)))

;; Unter Verwendung von reduce wird zunächst der
;; Artikel in unserer assozativen Liste ermittelt,
;; der den kleinsten Wert hat. Die seed muss dem
;; ersten Element entsprechen. Abschließend wird
;; der Schlüssel des resultierenden Paars ermittelt,
;; in unserem Fall der Artikelname.
;; Falls in der Liste mehrere Artikel mit minimaler
;; Anzahl vorkommen, so wird nur der erste Artikel
;; ausgegeben.

(define (minimum alist)
(car (reduce min_artikel alist (car alist))))

;; Ergebnis bei Anwendung auf Beispielliste:
;; > (minimum *Lagerbestand*)
;; lakritzschnecken

;; Zweite Lösungsmöglichkeit:

;; Definiere eine Hilfsfunktion, die rekursiv den Artikel
;; ermittelt, der die geringste Menge aufweist.

;; Rekursionsabbruch: Die Liste hat nur ein Element. Der
;; Artikel mit der kleinsten Anzahl ist genau das Element
;; dieser einelementigen Liste

;; Rekursionsschritt: Der Artikel mit der geringsten Anzahl
;; an Elementen ist das Minimum aus dem Kopf und dem Minimum
;; der Restliste.

(define minimum_kv
(lambda (alist)
(if (= (length alist) 1)
(car alist)
(if (<= (cdr (car alist)) (cdr (minimum_kv (cdr alist))))
(car alist)
(minimum_kv (cdr alist))
)
)
)
)

(define (minimum2 alist)
(car (minimum_kv alist)))

;; Ergebnis bei Anwendung auf Beispielliste:
;; > (minimum2 *Lagerbestand*)
;; lakritzschnecken

;; Dritte erweiterte Lösungsmöglichkeit:

;; Problem: Obige Funktionen liefern nur EIN Minimum, d.h. falls
;; zwei oder mehr Artikel die minimale Anzahl aufweisen, wird nur
;; der erste Artikel angezeigt.

;; minimum3 bestimmt zunächst das Minimum mit einer ähnlichen
;; Funktion, die in der ersten Lösungsmöglichkeit verwendet wurde
;; und filtert dann die Elemente aus der Liste, die genau diese
;; minimale Anzahl haben. Abschließend werden mit map die Namen
;; der Artikel extrahiert. Ergebnis ist eine Liste von Namen, die
;; Artikel bezeichnen, die eine minimale Anzahl aufweisen.

(define (minimum3 alist)
(let
;; berechne zunächst die minimale Artikelanzahl,
;; die in a list zu finden ist
((mini (cdr (reduce min_artikel alist (car alist)))))
;; extrahiere die Namen der Artikel (schlüsselwerte)
(map car
;; filtere die Artikel heraus, die die minimale
;; Anzahl aufweisen
(filter
;; #t, wenn dieser Artikel auch die minimale Anzahl
;; aufweist
(lambda (x)
(= (cdr x) mini)
) ;; lambda
alist
) ;; filter
) ;; map
) ;; let
)

;; Ergebnis bei Anwendung auf unsere Beispielliste
;; > (minimum3 *Lagerbestand*)
;; (lakritzschnecken zahnpasta)

;; 3 c)

(define *sollbestand* 1000)

;; nachbestellung artikel => artikel

;; Ermittelt zu einem Artikel die Anzahl der Einheiten,
;; die nachbestellt werden müssen, um den Vorrat auf
;; den Sollbestand zu erhöhen. Sind mehr Einheiten von
;; diesem Artikel vorhanden, so wird 0 ausgegeben.

(define (nachbestellung artikel)
(cons (car artikel) (if (< (cdr artikel) *sollbestand*)
(- *sollbestand* (cdr artikel))
0)))

;; Ergebnis bei Anwendung auf Beispielliste:

;; > (nachbestellung '(Lakritzschnecken . 800))
;; (lakritzschnecken . 200)

;; 3 d)

;; Generiert eine Liste, die die Anzahl an Einheiten enthält,
;; die für einen bestimmten Artikel nachbestellt werden müssen.

(define (bestelliste bestand)
(map nachbestellung bestand))

;; Ergebnis bei Anwendung auf Beispielliste:

;; > (bestelliste *Lagerbestand*)
;; ((gummibaerchen . 900)
;; (lakritzschnecken . 970)
;; (wundertueten . 700)
;; (brausepulver . 0)
;; (schokolade . 650)
;; (zahnpasta . 970))

</pre>
297850591943426100394568

Fachschaft Informatik - Benutzerbeiträge [de]

P1-WS04-MusterLoesung10.txt

P1-WS04-MusterLoesung12.txt