PatrickFey: 2 Versionen

2007-11-05T05:50:05Z

2 Versionen

← Nächstältere Version	Version vom 5. November 2007, 05:50 Uhr
(kein Unterschied)

fsrwiki_>Oddmuse Import: link fix

2007-11-05T05:49:25Z

link fix

← Nächstältere Version		Version vom 5. November 2007, 05:49 Uhr
Zeile 1:		Zeile 1:
	<pre>		<pre>
	;; P1 WiSe 2004/2005		;; P1 [[WiSe]] 2004/2005
	;; Musterlösung Blatt 13		;; Musterlösung Blatt 13
	;;		;;
Zeile 68:		Zeile 68:
	(< (gewicht eintrag1) (gewicht eintrag2)))		(< (gewicht eintrag1) (gewicht eintrag2)))

	;; DrScheme hat sort in einem Zusatzmodul, das wir erst laden müssen.		;; [[DrScheme]] hat sort in einem Zusatzmodul, das wir erst laden müssen.
	(require (lib "compat.ss"))		(require (lib "compat.ss"))

Zeile 146:		Zeile 146:
	;; Endrekursion bedeutet, daß der Rekursionsaufruf als allerletztes in		;; Endrekursion bedeutet, daß der Rekursionsaufruf als allerletztes in
	;; der Funktion passiert (vgl. "tail context / tail recursion" im		;; der Funktion passiert (vgl. "tail context / tail recursion" im
	;; R5RS, Abschnitt 3.5, Seite 7) und ist deswegen effizienter, weil es		;; [[R5RS]], Abschnitt 3.5, Seite 7) und ist deswegen effizienter, weil es
	;; bei einem solchen Aufruf nicht mehr notwendig ist, den aktuellen		;; bei einem solchen Aufruf nicht mehr notwendig ist, den aktuellen
	;; Zustand der aufrufenden Funktion zu sichern. Normalerweise müßten		;; Zustand der aufrufenden Funktion zu sichern. Normalerweise müßten
Zeile 153:		Zeile 153:
	;; ablen eh nicht mehr verwendet werden (können). Im Gegensatz zu		;; ablen eh nicht mehr verwendet werden (können). Im Gegensatz zu
	;; anderen Lisp-Varianten kann man sich bei Scheme sogar darauf		;; anderen Lisp-Varianten kann man sich bei Scheme sogar darauf
	;; verlassen, daß diese Optimierung geschieht, weil der R5RS dieses		;; verlassen, daß diese Optimierung geschieht, weil der [[R5RS]] dieses
	;; verlangt. Der Unterschied zwischen Endrekursion und allgemeiner		;; verlangt. Der Unterschied zwischen Endrekursion und allgemeiner
	;; Rekursion wird in imperativen Programmiersprachen üblicherweise		;; Rekursion wird in imperativen Programmiersprachen üblicherweise

fsrwiki_>1illig: antispam

2006-12-22T05:48:10Z

antispam

Neue Seite

<pre>
;; 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).

</pre>

P1-WS04-MusterLoesung13.txt - Versionsgeschichte

PatrickFey: 2 Versionen

fsrwiki_>Oddmuse Import: link fix

fsrwiki_>1illig: antispam