P1-WS04-MusterLoesung13.txt

Aus Fachschaft_Informatik
Version vom 5. November 2007, 06:50 Uhr von PatrickFey (Diskussion | Beiträge) (2 Versionen)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen
;;                          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).