Von Fröschen und Tischlampen

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2010-05-09T08:13:39+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Der Lampen-Stream
2 Frosch-Sprünge mit verschiedenen Weiten
3 Unendlich viele Frösche springen über unendlich viele Tischlampen
4 Auswertung

Der Lampen-Stream

Zunächst definieren wir den Stream (abzählbar) unendlich vieler Tischlampen, die alle ausgeschaltet sind.
Jede Lampe ist mit einem Schalter ausgestattet, mit dem die Lampe entsprechend ihres Betriebszustandes entweder ein- oder ausgeschaltet werden kann:

(define lamp-stream
  (stream-cons 'off lamp-stream))

(define switch
  (lambda (lamp)
    (if (eqv? lamp 'off)
        'on
        'off)))

<eval id="4b52203279c19"> (show-stream lamp-stream 18) </eval>

Frosch-Sprünge mit verschiedenen Weiten

Um jede n-te Lampe schalten zu können, erweitern wir die Stream-Sprachelemente mit der Prozedur stream-map-n.
In Analogie zu stream-map bewirkt stream-map-n eine Prozeduranwendung auf jedes n-te Element eines Streams:

(define stream-map-n
  (lambda (proz stm n)
    (letrec
        ([help-stream
          (lambda (stm s)
            (if (= s n)
                (stream-cons (proz (stream-car stm)) (help-stream (stream-cdr stm) 1))
                (stream-cons (stream-car stm) (help-stream (stream-cdr stm) (+ s 1)))))])
      (help-stream stm 1))))

Nun können wir Frosch-Sprünge mit aufsteigenden Sprungweiten definieren:

(define jump
  (lambda (stm w)
    (stream-cons (switch (stream-car stm))
      (jump (stream-map-n (lambda (lamp) (switch lamp)) (stream-cdr stm) w) (+ w 1)))))

Unendlich viele Frösche springen über unendlich viele Tischlampen

(define frog-lamp-stream
  (jump lamp-stream 1))

<eval id="4b52259a80ac2"> (show-stream frog-lamp-stream 18) </eval>

Auswertung

Um das Resultat besser verallgemeinern zu können, fassen wir die Nummern der Lampen zusammen, die nach allen Frosch-Sprüngen eingeschaltet sind. In der Vermutung, dass das (abzählbar) unendlich viele Lampen sind, soll dieses Ergebnis wiederum als Stream repräsentiert werden:

(define result-stream
  (lambda (stm)
    (letrec
        ([help-stream
          (lambda (stm i)
            (if (eqv? (stream-car stm) 'on)
                (stream-cons i (help-stream (stream-cdr stm) (+ i 1)))
                (help-stream (stream-cdr stm) (+ i 1))))])
      (help-stream stm 1))))

<eval id="4b52259a81a5e"> (show-stream (result-stream frog-lamp-stream) 18) </eval>

Ergebnis: Offensichtlich sind nach den Frosch-Sprüngen alle Lampen eingeschaltet, deren Nummern Quadratzahlen sind.

Zurück zu Streams.

Von Fröschen und Tischlampen

Inhaltsverzeichnis

Der Lampen-Stream

Frosch-Sprünge mit verschiedenen Weiten

Unendlich viele Frösche springen über unendlich viele Tischlampen

Auswertung

Suche