Projekt Zahlenfolgen

Aus ProgrammingWiki

;-- Stream-Sprachelemente -- (define stream-car car) (define stream-cdr (lambda (stm) (force (cdr stm)))) (define-macro (stream-cons head tail) `(cons ,head (delay ,tail))) (define stream? (lambda (stm) (and (pair? stm) (promise? (cdr stm))))) (define stream-map (lambda (proz stm) (stream-cons (proz (stream-car stm)) (stream-map proz (stream-cdr stm))))) (define show-stream (lambda (stm n) (letrec ([show (lambda (stm n ls) (if (= n 0) (apply display (append ls (list "..."))) (show (stream-cdr stm) (- n 1) (append ls (list (stream-car stm) ", ")))))]) (show stm n ())))) ;-- Stream-Balkendiagramm -- (define rand 50) (define maxbreite (- 400 (* 2 rand))) (define maxhoehe (- 300 (* 2 rand))) (define minmax (lambda (stm n) (letrec ([extremsuche (lambda (extrem stm n op) (cond [(= n 0) extrem] [(op extrem (stream-car stm)) (extremsuche (stream-car stm) (stream-cdr stm) (- n 1) op)] [else (extremsuche extrem (stream-cdr stm) (- n 1) op)]))]) (cons (extremsuche 0 stm n >) (extremsuche 0 stm n <))))) ;-- Stream-Balkendiagramm -- (define rand 50) (define maxbreite (- 400 (* 2 rand))) (define maxhoehe (- 300 (* 2 rand))) (define minmax (lambda (stm n) (letrec ([extremsuche (lambda (extrem stm n op) (cond [(= n 0) extrem] [(op extrem (stream-car stm)) (extremsuche (stream-car stm) (stream-cdr stm) (- n 1) op)] [else (extremsuche extrem (stream-cdr stm) (- n 1) op)]))]) (cons (extremsuche 0 stm n >) (extremsuche 0 stm n <))))) (define balken (lambda (hoehe breite) (forward turtle breite) (left turtle 90) (forward turtle hoehe) (left turtle 90) (forward turtle breite) (left turtle 90) (forward turtle hoehe) (left turtle 90) (forward turtle breite))) (define balkendiagramm (lambda (stm n) (let* ([breite (/ maxbreite n)] [extremwerte (minmax stm n)] [min (car extremwerte)] [max (cdr extremwerte)]) (letrec ([zeichnen (lambda (min max stm n) (if (= n 0) 'ok (begin (balken (floor (* (/ (stream-car stm) (- max min)) maxhoehe)) (floor breite)) (zeichnen min max (stream-cdr stm) (- n 1)))))]) (clear canvas) (hide turtle) (move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90) (zeichnen min max stm n))))) ;-- Stream natürlicher Zahlen -- (define natstream (lambda (n) (stream-cons n (natstream (+ n 1)))))

Inhaltsverzeichnis 1 Einführung 2 Beispiel 3 Aufgaben 3.1 Arithmetische und geometrische Zahlenfolgen 3.2 Spezielle Zahlenfolgen 3.3 Grenzwert einer Zahlenfolge 3.4 Zusatzaufgabe 4 Allgemeine Hinweise zum Projekt 5 Lösungen

Einführung

Unter einer unendlichen Zahlenfolge verstehen wir eine Funktion, deren Defintionsbereich die Menge der natürlichen Zahlen ist.
Damit bieten sich Streams zur Repräsentation dieser Zahlenfolgen im Computer an.
Wir können uns davon überzeugen, dass die erforderlichen Stream-Sprachelemente sowie der Stream natürlicher Zahlen bereits definiert sind:

(show-stream (natstream 0) 30)

ausführen

Nun wollen wir arithmetische, geometrische sowie weitere ausgewählte Zahlenfolgen aufstellen und untersuchen.

Beispiel

Gegeben ist eine Zahlenfolge $(e_n)$ mit der nachfolgenden expliziten Bildungsvorschrift:

$e_n=(1+\frac{1}{n})^n\hspace{0.3em},\hspace{0.3em}\mbox{für}\hspace{0.3em}n=1, 2, 3, ...$

In einfacher Weise definieren wir diese explizite Bildungsvorschrift als Prozedur, um sie mit stream-map auf die Elemente des Streams natürlicher Zahlen anzuwenden.
Hinweis: Der Startindex für die natürlichen Zahlen muss hier $1$ betragen!

(define fkt (lambda (n) (expt (+ 1 (/ 1 n)) n))) (define en (stream-map fkt (natstream 1)))

(show-stream en 30)

ausführen

Um diese Zahlenfolge besser analysieren zu können, wollen wir sie in einem Balkendiagramm visualisieren. Dazu muss die Syntax der Prozedur balkendiagramm für den Gebrauch von Streams angepasst werden:

(balkendiagramm <stm> <anz>) ; <stm> ... Stream mit Zahlenwerten
                             ; <anz> ... Anzahl der darzustellenden Elemente

(balkendiagramm en 30)

ausführen

Es ist anzunehmen, dass die Zahlenfolge $(e_n)$ konvergiert.
Deshalb wäre auch ein Werkzeug zur Suche von Grenzwerten beliebiger Zahlenfolgen wünschenswert.

Aufgaben

1. Arithmetische und geometrische Zahlenfolgen

   Implementieren Sie als Streams arithmetische oder geometrische Zahlenfolgen, die sowohl in einer rekursiven Bildungsvorschrift mit dem Anfangsglied $a_1$ als auch in einer expliziten Bildungsvorschrift gegeben sein können:

   	arithmetische Zahlenfolgen	geometrische Zahlenfolgen
   rekursive Bildungsvorschrift	$a_{n+1}=a_n+d \hspace{0.3em}, \hspace{0.3em} \mbox{mit} \hspace{0.3em} a_1$	$a_{n+1}=a_n \cdot q \hspace{0.3em}, \hspace{0.3em} \mbox{mit} \hspace{0.3em} a_1$
   explizite Bildungsvorschrift	$a_n=a_1+(n-1) \cdot d \hspace{0.3em}, \hspace{0.3em} \mbox{für} \hspace{0.3em} n=1,2,3,...$	$a_n=a_1 \cdot q^{n-1} \hspace{0.3em}, \hspace{0.3em} \mbox{für} \hspace{0.3em} n=1,2,3,...$

   Neben der Ausgabe mit show-stream soll es zwei weitere Ausgabeprozeduren geben, die

   • das n-te Folgenglied sowie
   • die Summe aller Glieder bis zum n-ten Folgenglied

   zurückgeben.

2. Spezielle Zahlenfolgen

   Gegeben sind Zahlenfolgen mit den nachfolgenden Beschreibungen:

   rekursive Beschreibung	$ (gs_1):\hspace{0.3em}1, \frac{1}{1+1}, \frac{1} {1+ \frac{1}{1+1}}, \frac{1} {1+ \frac{1}{1+ \frac{1}{1+1}}}, ... $
   	$ (gs_2):\hspace{0.3em} \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2+ \frac{1}{\sqrt{2}}}}, \frac{1}{\sqrt{2+ \frac{1}{\sqrt{2+ \frac{1}{\sqrt{2}}}}}}, ... $
   explizite Beschreibung	$z_n=\frac{1}{n!} \hspace{0.3em}, \hspace{0.3em}\mbox{für} \hspace{0.3em} n=0,1,2,...$
   	$f_n=\frac{\mbox{fibo}(n)}{\mbox{fibo}(n+1)} \hspace{0.3em}, \hspace{0.3em} \mbox{für} \hspace{0.3em} n=1,2,3,...$

   Implementieren Sie je eine der beiden rekursiv bzw. explizit beschriebenen Zahlenfolgen.

3. Grenzwert einer Zahlenfolge

   Schreiben Sie eine Prozedur, die den Grenzwert einer Zahlenfolge (mit beliebiger Genauigkeit) ermittelt, falls dieser existiert.
   Hinweis: Die Prozedur zur Grenzwertbestimmung könnte folgende Struktur haben:

   (grenzwert <stm> <eps> <min> <max>) 
   
   <stm> ... Zahlenfolge als Stream
   <eps> ... Epsilon-Umgebung als hinreichend kleiner Wert, der über die Konvergenz entscheidet
   <min> ... Anzahl von Folgengliedern, die bei Konvergenz in der Epsilon-Umgebung liegen müssen
   <max> ... maximale Anzahl von Folgengliedern, bei deren Überschreitung
             die Divergenz der Zahlenfolge vermutet und #f zurückgegeben wird
   

   Wenden Sie diese Prozedur auf die implementierten Zahlenfolgen an.

4. Zusatzaufgabe

   Die Partialsummenfolge $(s_n)$ einer Zahlenfolge $(a_n)$ enthält die Teilsummen, die aus den Folgengliedern $a_n$ gebildet werden. Es gilt:
   

   $(s_n):\hspace{0.3em}s_1, s_2, s_3, ...\hspace{0.6em}\mbox{mit}\hspace{0.3em} s_n=\sum\limits_{i=1}^n a_i=a_1+a_2+a_3+ ... +a_n$

   Implementieren Sie eine entsprechende Prozedur.
   Ermitteln Sie den Grenzwert der Partialsummenfolge von $(z_n)$ aus Aufgabe 2.

Allgemeine Hinweise zum Projekt

• Die Implementation der Zahlenfolgen sowie aller erforderlichen Prozeduren soll unter DrRacket erfolgen.
• Sie können dazu die Datei zahlenfolgen_vorlage.rkt (Sprache: racket) im Archiv

  Zahlenfolgen.zip (0.1 MB)

  nutzen, in der die Stream-Sprachelemente sowie die Prozeduren zur grafischen Darstellung im Balkendiagramm definiert sind.
• Zur Interaktion kann der vorgegebene einfache Bildschirmdialog weiterentwickelt werden.

Lösungen

Hier sind ausgewählte Schülerlösungen (2023) zusammengestellt.
Sie sollen Anregungen für eigene Implementationen liefern und keine effizienten Musterlösungen darstellen.