Grundlagen der funktionsorientierten Programmierung mit SCHEME/Lotto 6 aus 49
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>SchemeJS</language>
[[Bild:Lotto_Ziehungsgeraet1.jpg|miniatur|hochkant=2|Ziehungsgerät zum Lotto 6 aus 49]]
'''Autor: Veit Berger (2014)'''
== Vorüberlegungen ==
In einer beliebigen Anzahl sollen Lottoziehungen 6 aus 49 simuliert werden.<br />
Zunächst ist es kein Problem, Zufallszahlen zwischen 1 und 49 zu bestimmen (s. [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Prozeduren mit Zeichenketten und Listen|Prozeduren mit Zeichenketten und Listen]]).<br />
Wir sollten aber daran denken, dass diese Zahlen ohne Zurücklegen gezogen werden und damit paarweise verschieden sein müssen.
== Algorithmus ==
Wir wollen uns für eine endständig rekursive Problemlösung entscheiden, in der wir eine Liste mit korrekten Lottozahlen im rekursiven Abstieg einer entsprechenden Prozedur bilden. Mit einer Zählvariablen steuern wir den Ablauf:
* Falls der Zähler Null ist, gib die vollständige Liste einer Lottoziehung zurück.
* Anderenfalls lege eine Zufallszahl zwischen 1 und 49 fest.
* Prüfe, ob sie bereits Element der aktuellen Teilziehung ist.
* Trifft dieser Fall zu, wiederhole die Ziehung bei unverändertem Zählerstand.
* Anderenfalls füge die Zufallszahl zur Teilziehung hinzu und führe die Ziehung bei dem um 1 verminderten Zähler fort.
== Implementation ==
Um eine aufsteigend sortierte Lottoziehung zu ermitteln, modifizieren wir den Listen-Konstruktor <tt>cons</tt> geringfügig zu <tt>cons-sort</tt>.
<code id="53ebc626eaa08">
(define lottozahl
(lambda (max)
(+ 1 (random max))))
(define lottoziehung
(lambda (n max)
(letrec
([element?
(lambda (el ls)
(cond
[(null? ls) #f]
[(eqv? el (car ls)) #t]
[else
(element? el (cdr ls))]))]
[cons-sort
(lambda (el ls)
(cond
[(null? ls) (list el)]
[(< el (car ls)) (cons el ls)]
[else
(cons (car ls) (cons-sort el (cdr ls)))]))]
[ziehung
(lambda (n ls)
(if (= n 0)
ls
(let ([z (lottozahl max)])
(if (element? z ls)
(ziehung n ls)
(ziehung (- n 1) (cons-sort z ls))))))])
(ziehung n ()))))
(define lottoziehungen
(lambda (n max anz)
(if (= anz 0)
()
(cons (lottoziehung n max) (lottoziehungen n max (- anz 1))))))
</code>
<run id="53ebc626eaacc">
(lottoziehungen 6 49 5)
</run>
== Gleichverteilung der Lottozahlen ==
Wir wollen uns von einer hinreichenden Güte der Lottozahlen überzeugen.<br />
Dazu zählen wir das Auftreten jeder gezogenen Lottozahl in einer 49-elementigen Liste. Bei einer großen Anzahl von Ziehungen müsste sich eine Gleichverteilung der Lottozahlen ergeben. Diese visualisieren wir in einem Balkendiagramm (s. [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen|Mehrfachrekursionen]]).<br />
Zur Erinnerung sei nachfolgend die Syntax der Prozedur <tt>balkendiagramm</tt> für numerische Listen angegeben:
(balkendiagramm <ls>) ; <ls> ... Liste mit Zahlenwerten
<code id="53ec6802bf478" hidden>
(define rand 50)
(define maxbreite (- 400 (* 2 rand)))
(define maxhoehe (- 300 (* 2 rand)))
(define minmax
(lambda (ls)
(letrec
([extremsuche
(lambda (extrem ls op)
(cond
[(null? ls) extrem]
[(op extrem (car ls)) (extremsuche (car ls) (cdr ls) op)]
[else
(extremsuche extrem (cdr ls) op)]))])
(cons (extremsuche 0 ls >)
(extremsuche 0 ls <)))))
(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 (ls)
(let* ([breite (/ maxbreite (length ls))]
[extremwerte (minmax ls)]
[min (car extremwerte)] [max (cdr extremwerte)])
(letrec
([zeichnen
(lambda (min max ls)
(if (null? ls)
'ok
(begin
(balken (floor (* (/ (car ls) (- max min)) maxhoehe)) (floor breite))
(zeichnen min max (cdr ls)))))])
(clear canvas)
(hide turtle)
(move turtle rand (+ rand (* (/ max (- max min)) maxhoehe))) (right turtle 90)
(zeichnen min max ls)))))
</code>
<code id="53ec6802bf509">
(define verteilung
(lambda (min max ls)
(letrec
([startliste
(lambda (pos)
(if (< pos min)
()
(cons 0 (startliste (- pos 1)))))]
[poszaehlen
(lambda (pos erg-ls)
(if (= pos 1)
(cons (+ 1 (car erg-ls)) (cdr erg-ls))
(cons (car erg-ls) (poszaehlen (- pos 1) (cdr erg-ls)))))]
[zaehlen
(lambda (ls erg-ls)
(cond
[(null? ls) erg-ls]
[(list? (car ls)) (zaehlen (car ls) (zaehlen (cdr ls) erg-ls))]
[else
(zaehlen (cdr ls) (poszaehlen (car ls) erg-ls))]))])
(zaehlen ls (startliste max)))))
</code>
<canvas w="400" h="300"></canvas>
<run id="5bb3c99d386b2">
(balkendiagramm (verteilung 1 49 (lottoziehungen 6 49 1000)))
</run>
== Gewinnchancen ==
Welche Gewinnchancen haben wir beim Lotto?<br />
Zu einem eigenen Tipp wollen wir zählen, wie oft eine Zahl, zwei Zahlen, drei Zahlen usw. übereinstimmen. Wir beachten dabei, dass im mathematischen Sinne ein "Sechser" auch ein "Fünfer" ist, da zur Übereinstimmung von sechs Zahlen natürlich erst recht fünf Zahlen richtig sein müssen.
<code id="5bb3c99d38610">
(define vergleich
(lambda (tipp-ls ls)
(letrec
([startliste '(0 0 0 0 0 0)]
[poszaehlen
(lambda (pos erg-ls)
(if (= pos 1)
(cons (+ 1 (car erg-ls)) (cdr erg-ls))
(cons (car erg-ls) (poszaehlen (- pos 1) (cdr erg-ls)))))]
[element?
(lambda (el ls)
(cond
[(null? ls) #f]
[(eqv? el (car ls)) #t]
[else
(element? el (cdr ls))]))]
[teil-zaehlen
(lambda (ls1 ls2 pos erg-ls)
(cond
[(null? ls1) erg-ls]
[(element? (car ls1) ls2) (teil-zaehlen (cdr ls1) ls2 (+ 1 pos) (poszaehlen pos erg-ls))]
[else
(teil-zaehlen (cdr ls1) ls2 pos erg-ls)]))]
[zaehlen
(lambda (ls erg-ls)
(if (null? ls)
erg-ls
(zaehlen (cdr ls) (teil-zaehlen tipp-ls (car ls) 1 erg-ls))))])
(zaehlen ls startliste))))
(define auswertung
(lambda (tipp-ls n max anz)
(letrec
([ergebnis (vergleich tipp-ls (lottoziehungen n max anz))]
[ausgabe
(lambda (ls)
(cond
[(null? ls) 'ok]
[(= (length ls) 6)
(display (- 7 (length ls)) " Zahl richtig: " (car ls))
(ausgabe (cdr ls))]
[else
(display (- 7 (length ls)) " Zahlen richtig: " (car ls))
(ausgabe (cdr ls))]))])
(ausgabe ergebnis))))
</code>
<run id="5bb3c99d3872c">
(auswertung '(3 8 7 17 21 41) 6 49 1000)
</run>
Erstaunlicherweise ist die Wahrscheinlichkeit, ''eine'' Zahl richtig zu haben, höher als die, bei der ''keine'' Zahl übereinstimmt!
Zurück zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Algorithmusbegriff]].