TuH2 scheme

Wiki-Quelltext dieser Seite.

<language>Scheme</language>

=== Scheme Programmbeispiele ===

Für die Ausführung der Hauptprogramme sind diverse Hilfsprozeduren nötig. 
*zzls - Erstellt eine Zufallszahlenliste
*mv-mergesort - Sortiert eine Liste 
*teillisten2 - teilt eine Liste; wird von mv-mergesort und binaersuche benötigt
*verbinden - verbindet zwei Listen; wird von mv-mergesort benötigt

Der Programmcode der Hilfsprozeduren ist am Schluss dieser Wikiseite zu finden.

=== Hilfsprozeduren ===

== zzls ==

<code>
;zzls für ZufallsZahlenListe. Generiert eine Liste mit n paarweise verschiedenen Ganzen Zahlen zwischen a und b.
;Beispielaufruf: 
;>(zzls 10 100 1000) ; Zufallszahlenliste mit 1000 Zufallszahlen zwischen 10 und 100

(define zzls
  (lambda (a b n)
    (if (= n 0)
        (list)
        (let ((x (random b)))
          (if (> x a)
              (append (list x)(zzls a b (- n 1)))
              (zzls a b n))))))
</code>


== mv-mergesort ==
Die Prozedur ist aus "Teilen und Herschen 1" bekannt. Sie sortiert eine gegebene Liste der Größe nach.

<code>
;mv-mergesort 
(define mv-mergesort
  (lambda (ls)
    (if (or (null? ls)(null? (cdr ls)))
        ls
        (call-with-values
         (lambda () (teillisten2 ls))
         (lambda (ls1 ls2)
           (verbinden
            (mv-mergesort ls1)
            (mv-mergesort ls2)))))))</code>


== teillisten2 ==
Teilt eine Liste in zwei Teillisten.

<code>
(define teillisten2
  (lambda (ls)
    (let ((k (floor (/ (length ls) 2))))
      (letrec
          ((helfer
            (lambda (ls i)
              (if (= i 0)
                  (values '() ls)
                  (call-with-values
                   (lambda ()(helfer (cdr ls)(- i 1)))
                   (lambda (links rechts)
                     (values (cons (car ls) links) rechts)))))))
        (helfer ls k)))))
</code>

== verbinden ==
Verbindet zwei Listen zu einer einzigen Liste
<code>
(define verbinden
  (lambda (lls rls)
    (cond
      ((null? lls) rls)
      ((null? rls) lls)
      (else
       (let ((x (car lls))(y (car rls)))
         (if (< x y)
             (cons x (verbinden (cdr lls) rls))
             (cons y (verbinden lls (cdr rls)))))))))
</code>