Prozeduren höherer Ordnung-Loesung

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Filter
2 Tabellieren
3 Compose
4 Primzahlen
- 4.1 Natürliche Zahlen
5 Filter-Out

Filter

Schreiben Sie eine Prozedur filter, die eine Liste und eine Filterprozedur nimmt, und eine "gefilterte" Liste zurückgibt.

Hinweis: Die Filterprozedur ist eine einstellige Prozedur, welche #t bzw. #f zurückgibt.

Aufrufbeispiele

>(filter '(1 2 3 4 5 6 7 8 9) even?)
(2 4 6 8)
>(filter '(1 2 3 4 5) (lambda (x) (not (or (= x 2) (= x 5)))))
(1 3 4)
>(filter '(#\a 276 "blubb" 5 blah 3 5 (4 995 54)) number?)
(276 5 3 5)

(define filter 
  (lambda (liste funktion)
    (cond
      ((null? liste) '())
      ((funktion (car liste)) (cons (car liste) (filter (cdr liste) funktion)))
      (else
        (filter (cdr liste) funktion)))))

(filter '(1 2 3 4 5 6 7 8 9) even?)

Tabellieren

Schreiben Sie eine Prozedur tabelliere zur Ausgabe einer Wertetabelle mit den Spalten x und f(x), wobei f eine einstellige Funktion ist, die für x=a,a+1,\ldots,b protokolliert werden soll. f, a und b sollen beim Aufruf als Parameter übergeben werden.

Hinweis: Testen Sie auch mit Lambda-Ausdrücken für f.

Aufrufbeispiel:

> (tabelliere (lambda (x) (* x x)) 0 5)
(0 1 4 9 16 25)

(define tabelliere
  (lambda (funktion untergrenze obergrenze)
    (display untergrenze) (display #\tab) (display (funktion untergrenze)) (newline)
    (if (>= untergrenze obergrenze)
      'schluss
      (tabelliere funktion (+ untergrenze 1) obergrenze))))

(tabelliere (lambda (x) (* x x)) 0 5)

Compose

Schreiben Sie eine Prozedur compose, die zwei einstellige Prozeduren proc1 und proc2 nimmt, diese verkettet und die Verkettungsprozedur "proc2 nach proc1" zurückgibt. Wenden Sie compose auf geeignete Argumente an.

Aufrufbeispiel:

> ((compose (lambda (n) (+ n n)) (lambda (n) (* n n))) 4)
64

Wichtig: Die Klammersetzung im Aufrufbeispiel ist korrekt!

(define compose 
  (lambda (proc1 proc2)
    (lambda (x) (proc2 (proc1 x)))))

((compose (lambda (n) (+ n n)) (lambda (n) (* n n))) 4)

Primzahlen

Verwenden Sie die oben definierte Prozedur filter, um aus der Liste der natürlichen Zahlen von 1 bis 1000 alle Primzahlen herauszusieben. Die verbleibenden Primzahlen sollen als Liste zurückgegeben werden.

Natürliche Zahlen

Sie benötigen eine Hilfsprozedur nliste, die eine Liste mit natürlichen Zahlen von 1 bis n erzeugt.

Aufrufbeispiel:

> (nliste 5)
(1 2 3 4 5)

(define nliste 
  (lambda (zahl)
    (if (= zahl 0)
       '()
       (append (nliste (- zahl 1)) (list zahl)))))

(nliste 1000)

Außerdem benötigen Sie eine Prozedur prim?, die für eine gegebene natürliche Zahl n feststellt, ob sie eine Primzahl ist oder nicht. Verwenden Sie die folgende Prozedur alle-teiler zur Definition von prim?.

(define alle-teiler
  (lambda (n t)
    (cond
      ((= t 1) '())
      ((zero? (remainder n t)) (cons t (alle-teiler n (- t 1))))
      (else
       (alle-teiler n (- t 1))))))

(alle-teiler 24 24)

Beachten Sie, dass die Prozedur alle-teiler die Zahl 1 nicht enthält. Mathematisch ist 1 Teiler jeder Zahl.

(define prim?
  (lambda (n)
    (if (< n 2) 
        #f
        (equal? (list n)(alle-teiler n n)))))

(prim? 11)

Nun kann die Liste der Primzahlen berechnet werden:

Aufrufbeispiel:

(filter (nliste 1000) prim?)
>(2 3 5 7 11 13 17 19 ...)

(filter (nliste 1000) prim?)

Filter-Out

Schreiben Sie analog zu filter eine Prozedur filter-out, die statt der Liste mit Primzahlen die Restliste ohne Primzahlen liefert. Die Primzahlen werden sozusagen herausgefiltert und aus der Ursprungsliste entfernt.

Aufrufbeispiel:

> (filter-out (nliste 1000) prim?)
(1 4 6 8 9 10 12 14 15 ...)

(define filter-out
  (lambda (ls pred)
    (cond
      ((null? ls) '())
      ((pred (car ls)) (filter-out (cdr ls) pred))
      (else
        (cons (car ls) (filter-out (cdr ls) pred))))))

(filter-out (nliste 1000) prim?)

zur Übungsübersicht

Prozeduren höherer Ordnung-Loesung

Inhaltsverzeichnis

Filter

Tabellieren

Compose

Primzahlen

Natürliche Zahlen

Filter-Out

Suche