Schülerlösungen 2023 Jahrgangsstufe 11

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 <))))) (define balken (lambda (hoehe breite turtle) (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 nr) (let* ([breite (/ maxbreite n)] [extremwerte (minmax stm n)] [min (car extremwerte)] [max (cdr extremwerte)] [canvas (eval (string->symbol (string-append "canvas" (number->string nr))))] [turtle (eval (string->symbol (string-append "turtle" (number->string nr))))]) (letrec ([zeichnen (lambda (min max stm n) (if (= n 0) 'ok (begin (balken (floor (* (/ (stream-car stm) (- max min)) maxhoehe)) (floor breite) turtle) (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)))))

Voraussetzungen

Für das Projekt sind bereits die bekannten Stream-Sprachelemente definiert:

Weiterhin steht bereit:

(define natstream (lambda (n) (stream-cons n (natstream (+ n 1)))))

Syntax-Erweiterungen

Es ist sinnvoll, die Glieder einer Zahlenfolge sinnvoll zu runden. Deshalb soll die Stream-Ausgabe um die schon bekannte Prozedur runden erweitert werden:

(define runden (lambda (x anz) (/ (round (* x (expt 10 anz))) (expt 10 anz)))) (set! show-stream (lambda (stm n anz) (letrec ([show (lambda (stm m ls) (cond [(> m n) (apply display (append ls (list "...")))] [(= (modulo m 20) 0) (apply display (append ls (list (stream-car stm) ", "))) (show (stream-cdr stm) (+ m 1) ())] [else (show (stream-cdr stm) (+ m 1) (append ls (list (runden (stream-car stm) anz) ", ")))]))]) (show stm 1 ()))))

Um mehrere Balkendiagramme grafisch darstellen zu können, ist weiterhin die nachfolgende geringfügige Syntax-Erweiterung der Prozedur balkendiagramm notwendig:

(balkendiagramm <stm> <anz> <nr>) ; <stm> ... Stream mit Zahlenwerten
                                  ; <anz> ... Anzahl der darzustellenden Elemente
                                  ; <nr>  ... fortlaufende Nummerierung des Balkendiagramms

Beispiel:

Gegeben ist die 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, ...$

Explizite Bildungsvorschrift:

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

(show-stream en 15 3)

ausführen

(balkendiagramm en 30 1)

ausführen

Die Collatz-Folge

Autor: Mathias Heyder Avalos (2023)

Lothar Collatz,
Foto aus der Sammlung des Mathematischen Forschungsinstituts Oberwolfach

Lothar Collatz (* 6. Juli 1910; † 26. September 1990) veröffentlichte die Zahlenfolge im Jahr 1937.

Definition:

$a_1 \longrightarrow a_{n+1}=\begin{cases}\dfrac{a_n}{2},\mbox{wenn}\hspace{0.3em}a_n\hspace{0.3em}\mbox{gerade}\\\\3 \cdot a_n + 1,\mbox{sonst}\end{cases}$

Implementation:

(show-stream (collatz-folge 19) 30 0)

ausführen

(balkendiagramm (collatz-folge 19) 30 2)

ausführen

Collatz-Problem:

Die Folge tritt somit in einen Zyklus ein, in dem die Glieder $4$, $2$, $1$ ab einem bestimmten Folgenglied ständig wiederholt werden.
Mit den folgenden Prozeduren wird geprüft, ob diese Periode eintritt und ggf. gezählt, ab welchem Folgenglied das erfolgt.

(define collatz-grenze? (lambda (stm) (equal? (list (stream-car stm) (stream-car (stream-cdr stm)) (stream-car (stream-cdr (stream-cdr stm)))) '(4 2 1)))) (define collatz-zaehler (lambda (stm n maximum) (cond [(= n maximum) #f] [(collatz-grenze? stm) n] [else (collatz-zaehler (stream-cdr stm) (+ n 1) maximum)])))

(define a1 83) (show-stream (collatz-folge a1) 120 0) (collatz-zaehler (collatz-folge a1) 1 1000)

ausführen

Bis heute ist nicht geklärt, ob diese Periode bei jedem beliebigen Startglied $a_1$ eintritt.