P1-WS04-MusterLoesung13.txt: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
fsrwiki_>Oddmuse Import K (link fix) |
K (2 Versionen) |
(kein Unterschied)
|
Aktuelle Version vom 5. November 2007, 07:50 Uhr
;; P1 [[WiSe]] 2004/2005 ;; Musterlösung Blatt 13 ;; ;;----------------------------------------------------------------- ;; Aufgabe 1 (define *fang-tabelle* '(("Simon Sonntagsangler" "Hering" 1.2) ("Karl Kabeljau" "Dorsch" 8) ("Marietta Mogel" "Thunfisch" 30) ("Kapitaen Ahab" "Pottwal" 2500) ("Britta Besser" "Dorsch" 15.2) ("Paul Pechvogel" "Tauchlehrer" 91.6))) ;; (a) i. ;; Konstruktor: neuer-eintrag (define (neuer-eintrag teilnehmer fang gewicht) (list teilnehmer fang gewicht)) ;; Test: (neuer-eintrag "Ulli Ungeschickt" "Sardine" 0.5) ;; => ("Ulli Ungeschickt" "Sardine" 0.5) ;; ii. Selektoren: teilnehmer, fang, gewicht (define (teilnehmer eintrag) (first eintrag)) (define (fang eintrag) (second eintrag)) (define (gewicht eintrag) (third eintrag)) ;; wer es lieber kryptisch mag, macht das so: ; (define teilnehmer car) ; (define fang cadr) ; (define gewicht caddr) ;; (b) einfache Versionen von compose und curry für Leute, die ;; tools.scm nicht laden wollen (define (compose f g) (lambda (x) (f (g x)))) (define (curry f x1) (lambda (x2) (f x1 x2))) (define (bereinigen liste) (filter (compose (curry equal? "Dorsch") fang) liste)) ;; das Ganze geht auch mit lambda: ; (define (bereinigen liste) ; (filter (lambda (eintrag) (equal? (fang eintrag) "Dorsch")) ; liste)) ;; Test: (bereinigen *fang-tabelle*) ;; => (("Karl Kabeljau" "Dorsch" 8) ("Britta Besser" "Dorsch" 15.2)) ;; (c) i./ii. ;; Damit wir die sort-Funktion benutzen können, brauchen wir zunächst ;; ein paar Vergleichsprädikate, die ähnlich wie string<? oder < ;; funktionieren. (define (teilnehmer<? eintrag1 eintrag2) (string<? (teilnehmer eintrag1) (teilnehmer eintrag2))) (define (gewicht<? eintrag1 eintrag2) (< (gewicht eintrag1) (gewicht eintrag2))) ;; [[DrScheme]] hat sort in einem Zusatzmodul, das wir erst laden müssen. (require (lib "compat.ss")) (define (nachTeilnehmer liste) (sort teilnehmer<? liste)) (define (nachGewicht liste) (sort gewicht<? liste)) ;; Test: (nachTeilnehmer *fang-tabelle*) ;; => (("Britta Besser" "Dorsch" 15.2) ;; ("Kapitaen Ahab" "Pottwal" 2500) ;; ("Karl Kabeljau" "Dorsch" 8) ;; ("Marietta Mogel" "Thunfisch" 30) ;; ("Paul Pechvogel" "Tauchlehrer" 91.6) ;; ("Simon Sonntagsangler" "Hering" 1.2)) (nachGewicht (bereinigen *fang-tabelle*)) ;; => (("Karl Kabeljau" "Dorsch" 8) ("Britta Besser" "Dorsch" 15.2)) ;; (c) iii. (define (groesstes-gewicht liste) (apply max (map gewicht liste))) ;; Die folgende Funktion bestimmt die Liste aller Leute, die grösste ;; Fische gefangen haben (es kann ja auch zwei Walfänger geben) und ;; gibt dann den ersten aus der Liste zurück. (define (sieger-eintrag liste) (let ((maxgewicht (groesstes-gewicht liste))) (car (filter (compose (curry equal? maxgewicht) gewicht) liste)))) ;; Test: (groesstes-gewicht *fang-tabelle*) ;; => 2500 ;; (c) iv. (define (mittleres-gewicht liste) (let ((gewichte (map gewicht liste))) (/ (apply + gewichte) (length gewichte)))) ;; Test: (mittleres-gewicht *fang-tabelle*) ;; => 440.99999999999994 ;;----------------------------------------------------------------- ;; Aufgabe 2 ;; (a) allgemein rekursiv: (define (mymap1 f xs ys) (cond ((null? xs) ()) ((null? ys) ()) (else (cons (f (car xs) (car ys)) (mymap1 f (cdr xs) (cdr ys)))))) ;; (b) endrekursiv: (define (helper f xs ys accu) (cond ((null? xs) accu) ((null? ys) accu) (else (helper f (cdr xs) (cdr ys) (cons (f (car xs) (car ys)) accu))))) (define (mymap2 f xs ys) (reverse (helper f xs ys ()))) ;; (c) mymap2 ist effizienter, weil nur Endrekursionen benutzt werden. ;; Der zusätzliche Aufruf von reverse ist notwendig, weil Listen über ;; Endrekursion nur rückwärts bearbeitet/ausgegeben werden können; ;; allerdings läßt sich dieses reverse daher wieder mit einer trivialen ;; Endrekursion erledigen, und zwei aufeinanderfolgende Endrekursionen ;; sind immer noch als effizienter anzusehen als eine allgemeine ;; Rekursion. mymap1 mag allerdings trotzdem für kleine Listen ;; schneller sein, und ist zudem lesbarer. ;; Endrekursion bedeutet, daß der Rekursionsaufruf als allerletztes in ;; der Funktion passiert (vgl. "tail context / tail recursion" im ;; [[R5RS]], Abschnitt 3.5, Seite 7) und ist deswegen effizienter, weil es ;; bei einem solchen Aufruf nicht mehr notwendig ist, den aktuellen ;; Zustand der aufrufenden Funktion zu sichern. Normalerweise müßten ;; z.B. lokale Variablenbelegungen auf dem Stack gesichert werden, ;; aber in diesem Fall kann dies unterlassen werden, weil die Vari- ;; ablen eh nicht mehr verwendet werden (können). Im Gegensatz zu ;; anderen Lisp-Varianten kann man sich bei Scheme sogar darauf ;; verlassen, daß diese Optimierung geschieht, weil der [[R5RS]] dieses ;; verlangt. Der Unterschied zwischen Endrekursion und allgemeiner ;; Rekursion wird in imperativen Programmiersprachen üblicherweise ;; vernachlässigt, weil man dort statt Endrekursion Schleifen- ;; konstrukte (wie z.B. "for" oder "while") verwenden kann. ;;----------------------------------------------------------------- ;; Aufgabe 3 ;; (a) ;; In dieser Aufgabendefinition liegt eine indirekt geschachtelte Baumrekursion vor. ;; (b) (define *fg (/ 1 51)) (define *fs (/ 1 153)) (define *f0 2001) (define *pf0 6120000000) (define (p j) (cond ((eq? j *f0) *pf0) ((> j *f0) (+ (p (- j 1)) (- (g (- j 1)) (s (- j 1))))) ((< j *f0) (- (p (+ j 1)) (- (g (+ j 1)) (s (+ j 1))))))) (define (g j) (* *fg (p j))) (define (s j) (* *fs (p j))) ;; (c) P(J-1) steht jeweils in den Formeln für P(J), G(J-1), S(J-1). ;; Bei naiver Berechnung ergibt sich eine Baumrekursion mit einem ;; Verzweigungsfaktor von 3 (also ziemlich schlimm). ;; Setzt man die Gleichungen für G(J-1) und S(J-1) in die für P(J) ;; ein, so bekommt man eine einfachere Rekursionsgleichung: (define (pop j j0 p0 fg fs) (if (= j j0) p0 (pop j (+ j 1) (* p0 (+ 1 fg (- fs))) fg fs))) ;;----------------------------------------------------------------- ;; Aufgabe 4 (define (andere von nach) (modulo (- 6 von nach) 3)) (define (scheiben von nach wieviele) (if (= wieviele 0) () (append (scheiben von (andere von nach) (- wieviele 1)) (list (list 'Scheibe wieviele 'von von 'nach nach)) (scheiben (andere von nach) nach (- wieviele 1))))) ;; Behauptung: ;; Unter der Annahme, dass die Scheiben bis zur Dicke <wieviele> auf ;; dem Stab <von> liegen, führt die Anweisungsfolge dazu, dass die ;; Scheiben bis zur Dicke <wieviele> auf dem Stab <nach> liegen. ;; Andere Scheiben mit einer grösseren Dicke werden nicht bewegt. ;; Beweis: ;; Für n=0 braucht man nichts zu tun. ;; Angenommen, die Scheiben bis zur Dicke <wieviele> liegen auf dem ;; Stab <von>. Wir können nun die Scheiben bis zur Dicke ;; <wieviele>-1 auf den anderen (d.h. nicht <von> oder <nach>) Stab ;; verschieben (Induktionsannahme). Dann können wir die Scheibe der ;; Dicke <wieviele> auf den Stab <nach> verschieben (den die ;; Scheiben mit kleinerer Dicke sind alle auf dem anderen Stab), und ;; dann die Scheiben mit kleinerer Dicke auf den <nach>-Stab ;; verschieben (Induktionsannahme).