Verzögerte Evaluation und Streams-Loesung
Inhaltsverzeichnis |
Hilfsprozeduren
Die folgende Tabelle zeigt Ihnen Hilfsprozeduren, die Sie bei der Arbeit mit streams verwenden können. Machen Sie sich mit diesen Prozeduren vertraut.
| Bezeichnung | Parameter | Beschreibung |
|---|---|---|
| stream-car | stream | analog zu car |
| stream-cons | stream | analog zu car |
| stream? | parameter | testet, ob der Parameter ein Stream ist |
| make-stream | seed proc | gibt einen neuen Stream mit dem Anfangswert seed und der Prozedur proc zum Berechnen der Folgeglieder |
| stream->list | stream n | gibt eine Liste der ersten n Glieder des Streams |
| stream-item | stream n | gibt das n-te Element eines Streams zurück |
| stream-map | funktion stream | gibt einen Stream zurück, bei dem die Funktion auf alle Glieder des Streams angewendet wird |
Die im Folg. definierte Prozedur integer-stream-maker erzeugt einen Stream ganzer Zahlen, beginnend mit der als Argument übergebenen Zahl. Wir werden sie weiter unten benötigen.
<eval id="4b04f53cbf599">(stream->list integers 10)</eval>
Delay und Force
Machen Sie sich mit den Sprachelementen delay und force vertraut. Diskutieren Sie zu zweit darüber, warum Streams in Scheme als Paare dargestellt werden, und erläutern Sie die Verbindung zu den oben genannten Sprachelementen.
Schreiben Sie eine Prozedur stream+, welche zwei streams mit Zahlen als Parameter nimmt und deren Werte paarweise bis zum n-ten Element addiert und als Liste zurückgibt.
<eval id="4b04f53cbfd67">(print-stream (stream+ integers integers) 5) 0, 2, 4, 6, 8, ... </eval>
Zahlenfolgen
In den folgenden Aufgaben geht es um Zahlenfolgen. Folgende zwei Zahlenfolgen (a_n) und (b_n) sind gegeben:
(a_{n})=\frac{1}{\sqrt{2 + \bf{0}}}, {\frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + 0}}}}}, {\frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + \frac{1}{\sqrt{2 + 0 }}}}}}},\ldots (b_{n})=\frac{1}{\sqrt{1 + 0}}, {\frac{1}{1 + \frac{1}{1 + 0}}}, {\frac{1}{1 + {\frac{1}{1 + \frac{1}{1 + 0 }}}}},\ldotsVersuchen Sie das jeweilige Erzeugungsmuster in der jeweiligen Zahlenfolge zu erkennen. Beschreiben Sie die rekursive Gestalt dieser Ausdrücke.
Hinweis: Aus eigener Erfahrung weiß ich, dass es oft hilfreich ist, beim Programmieren einen Zettel und einen Stift parat zu haben, um sich einige Gedankengänge oder weiterführende Ideen zu notieren!
Implementieren Sie nun die oben definierten Zahlenfolgen mit Scheme unter Verwendung von Streams und Rekursion.
<eval id="4b04f53cc055a"> (define an (an-stream-maker 0))) (stream->list an 5) 0.7071067811865475, 0.6077812620656623, 0.6192477250610301,0.6178907764054561, 0.6180508933676908, ... </eval>
<eval id="4b04ff9685466"> (define bn (bn-stream-maker 0))) (stream->list bn 5) 1, 1/2, 2/3, 3/5, 5/8, ... </eval>
Grenzwerte
Schreiben Sie eine Prozedur grenzwert, die den Grenzwert einer Zahlenfolge bestimmt. Diese soll den Grenzwert einer als Stream repräsentierten Zahlenfolge stm zurückgeben, wenn dieser innerhalb einer hinreichend kleinen \varepsilon-Umgebung (eps) liegt. Falls nicht max Folgenglieder in dieser \varepsilon-Umgebung liegen, wird Divergenz vermutet und #f zurückgegeben.
Ermitteln und vergleichen Sie die Grenzwerte der Zahlenfolgen (a_{n}) und (b_{n} ).
<eval id="4b04f53cc149c">(grenzwert an 1/100 10)</eval> <eval id="4b04f53cc1ce6">(grenzwert bn 1/100 10)</eval>
Testen Sie ihre Grenzwert-Prozedur wenigstens mit folgenden Aufrufbeispielen. (Dabei wird nicht erwartet, dass Sie die Definition von tf wirklich verstehen):
<eval id="4b04f53cc249b">(grenzwert tf 1/110 10)</eval> <eval id="4b04f53cc2c6c">(grenzwert tf 1/110 9)</eval> <eval id="4b04f53cc3453">(grenzwert tf 1/111 11)</eval> <eval id="4b04f53cc3b91">(grenzwert tf 1/111 10)</eval>
Eulersche Zahl
Die Eulersche Zahl ist gegeben durch folgende Reihe
- e = \sum_{k=0}^{\infty}{\frac{1}{k!}} = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots.
Hinweis: 0! = 1
Schreiben Sie als eine Prozedur, die die Eulersche Zahl näherungsweise bis zum n-ten Glied berechnet. In der Sprache der Mathematik entspricht dies der Partialsummenfolge.
<eval id="4b04f53cc43be">(define en (en-stream-maker 0)) (stream->list en 5) 11, 1, 1/2, 1/6, 1/24, ... </eval>
Mit Hilfe der Prozeduren grenzwert und partialsummenfolge kann nun der Wert der unendlichen Reihe näherungsweise ermittelt werden. <eval id="4b04f53cc5b25">(grenzwert (partialsummenfolge en) 1/10 10)</eval> <eval id="4b04f53cc6300">(grenzwert (partialsummenfolge en) 1/100 10)</eval> <eval id="4b04f53cc6a69">(grenzwert (partialsummenfolge en) 1/1000 10)</eval>