Grundlagen der funktionsorientierten Programmierung mit SCHEME/Lotto 6 aus 49

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="53ebc626ea980" hidden>
;-- M. Hielscher / Chr. Wagenknecht --
(define random-maker
  (let* ((multiplier 48271)
         (modulus 2147483647)
         (apply-congruence
          (lambda (current-seed)
            (let ((candidate (modulo (* current-seed multiplier) modulus)))
              (if (zero? candidate)
                  modulus
                  candidate))))
         (coerce
          (lambda (proposed-seed)
            (if (integer? proposed-seed)
                (- modulus (modulo proposed-seed modulus)) 19880214))))
  (lambda (initial-seed)
    (let ((seed (coerce initial-seed)))
      (lambda args
        (cond ((null? args)
               (set! seed (apply-congruence seed))
               (/ (- modulus seed) modulus))
              ((null? (cdr args))
               (let* ((proposed-top
                       (ceiling (abs (car args))))
                      (exact-top
                       (if (inexact? proposed-top)
                           (inexact->exact proposed-top)
                           proposed-top))
                      (top
                       (if (zero? exact-top)
                           1
                           exact-top)))
                 (set! seed (apply-congruence seed))
                 (inexact->exact (floor (* top (/ seed modulus))))))
              ((eq? (cadr args) 'reset)
               (set! seed (coerce (car args))))
              (else
               (display "random: unrecognized message")
               (newline))))))))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)

(define random (random-maker (time-nanosecond (current-time))))
</code>

'''Autor: Berger, Veit'''

[[Bild:Lotto_Ziehungsgeraet1.jpg|miniatur|hochkant=1.5|Ziehungsgerät zum Lotto 6 aus 49]]

== Vorüberlegung ==

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 erinnern, dass diese Zahlen in einer korrekten Lottoziehung 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>

Zurück zum [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Der Algorithmusbegriff|Algorithmusbegriff]].