TuH2 scheme

Aus ProgrammingWiki

Archivierte Version vom 2009-04-06T10:00:37+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Scheme Programmbeispiele
2 Hilfsprozeduren
3 zzls
4 mv-mergesort
5 teillisten2
6 verbinden

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

;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))))))

mv-mergesort

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

;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)))))))

teillisten2

Teilt eine Liste in zwei Teillisten.

(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)))))

verbinden

Verbindet zwei Listen zu einer einzigen Liste

(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)))))))))

TuH2 scheme

Inhaltsverzeichnis

Scheme Programmbeispiele

Hilfsprozeduren

zzls

mv-mergesort

teillisten2

verbinden

Suche