Grundlagen der funktionsorientierten Programmierung mit SCHEME/Projekt Zahlenfolgen
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
<code id="5ba73f59a1537" hidden>
;-- 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)))))
</code>
== Einführung ==
Unter einer unendlichen Zahlenfolge verstehen wir eine Funktion, deren Defintionsbereich die Menge der natürlichen Zahlen ist.<br />
Damit bieten sich ''Streams'' zur Repräsentation dieser Zahlenfolgen im Computer an.<br />
Wir können uns davon überzeugen, dass die erforderlichen Stream-Sprachelemente sowie der Stream natürlicher Zahlen bereits definiert sind:
<run id="4b37cae744bb6">
(show-stream (natstream 0) 30)
</run>
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:
<blockquote>$e_n=(1+\frac{1}{n})^n\hspace{0.3em},\hspace{0.3em}\mbox{für}\hspace{0.3em}n=1, 2, 3, ...$</blockquote>
In einfacher Weise definieren wir diese explizite Bildungsvorschrift als Prozedur, um sie mit <tt>stream-map</tt> auf die Elemente des Streams natürlicher Zahlen anzuwenden.<br />
'''Hinweis:''' Der Startindex für die natürlichen Zahlen muss hier $1$ betragen!
<code id="4b37cae743c13">
(define fkt
(lambda (n)
(expt (+ 1 (/ 1 n)) n)))
(define en (stream-map fkt (natstream 1)))
</code>
<run id="4b37cae745b51">
(show-stream en 30)
</run>
Um diese Zahlenfolge besser analysieren zu können, wollen wir sie in einem Balkendiagramm visualisieren. Dazu muss die Syntax der Prozedur <tt>balkendiagramm</tt> für den Gebrauch von Streams angepasst werden:
(balkendiagramm <stm> <anz>) ; <stm> ... Stream mit Zahlenwerten
; <anz> ... Anzahl der darzustellenden Elemente
<canvas w="400" h="300"></canvas>
<run id="4b37cae746af2">
(balkendiagramm en 30)
</run>
Es ist anzunehmen, dass die Zahlenfolge $(e_n)$ konvergiert.<br />
Deshalb wäre auch ein Werkzeug zur Suche von Grenzwerten beliebiger Zahlenfolgen wünschenswert.
== Aufgaben ==
<ol>
<li>
=== 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:
<table border="1" cellspacing="1" cellpadding="8">
<tr>
<th> </th>
<th>arithmetische Zahlenfolgen</th>
<th>geometrische Zahlenfolgen</th>
</tr>
<tr>
<th>rekursive Bildungsvorschrift</th>
<td align="center">$a_{n+1}=a_n+d \hspace{0.3em}, \hspace{0.3em} \mbox{mit} \hspace{0.3em} a_1$</td>
<td align="center">$a_{n+1}=a_n \cdot q \hspace{0.3em}, \hspace{0.3em} \mbox{mit} \hspace{0.3em} a_1$</td>
</tr>
<tr>
<th>explizite Bildungsvorschrift</th>
<td align="center">$a_n=a_1+(n-1) \cdot d \hspace{0.3em}, \hspace{0.3em} \mbox{für} \hspace{0.3em} n=1,2,3,...$</td>
<td align="center">$a_n=a_1 \cdot q^{n-1} \hspace{0.3em}, \hspace{0.3em} \mbox{für} \hspace{0.3em} n=1,2,3,...$</td>
</tr>
</table>
Neben der Ausgabe mit <tt>show-stream</tt> soll es zwei weitere Ausgabeprozeduren geben, die
* das n-te Folgenglied sowie
* die Summe aller Glieder bis zum n-ten Folgenglied
zurückgeben.
</li>
<li>
=== Spezielle Zahlenfolgen ===
Gegeben sind Zahlenfolgen mit den nachfolgenden Beschreibungen:
<table border="1" cellspacing="1" cellpadding="8">
<tr>
<th rowspan="2" valign="top">rekursive Beschreibung</th>
<td>
$
(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}}}, ...
$
</td>
</tr>
<tr>
<td>
$
(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}}}}}}, ...
$
</td>
</tr>
<tr>
<th rowspan="2" valign="top">explizite Beschreibung</th>
<td>$z_n=\frac{1}{n!} \hspace{0.3em}, \hspace{0.3em}\mbox{für} \hspace{0.3em} n=0,1,2,...$</td>
</tr>
<tr>
<td>$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,...$</td>
</tr>
</table>
Implementieren Sie je eine der beiden rekursiv bzw. explizit beschriebenen Zahlenfolgen.
</li>
<li>
=== Grenzwert einer Zahlenfolge ===
Schreiben Sie eine Prozedur, die den Grenzwert einer Zahlenfolge (mit beliebiger Genauigkeit) ermittelt, falls dieser existiert.<br />
'''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.
</li>
<li>
=== Zusatzaufgabe ===
Die Partialsummenfolge $(s_n)$ einer Zahlenfolge $(a_n)$ enthält die Teilsummen, die aus den Folgengliedern $a_n$ gebildet werden. Es gilt:<br />
<blockquote>$(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$</blockquote>
Implementieren Sie eine entsprechende Prozedur.<br \>
Ermitteln Sie den Grenzwert der Partialsummenfolge von $(z_n)$ aus Aufgabe 2.
</li>
</ol>
== Allgemeine Hinweise zum Projekt ==
* Die Implementation der Zahlenfolgen sowie aller erforderlichen Prozeduren soll unter ''DrRacket'' erfolgen.
* Sie können dazu die Datei <tt>zahlenfolgen_vorlage.rkt</tt> (Sprache: <tt>racket</tt>) im Archiv <document>Zahlenfolgen.zip</document> 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 [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Projekt Zahlenfolgen/Schülerlösungen 2023 Jahrgangsstufe 11|Schülerlösungen (2023)]] zusammengestellt.<br />
Sie sollen Anregungen für eigene Implementationen liefern und '''keine''' effizienten Musterlösungen darstellen.