Superminimum

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2019-01-25T13:32:12+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Minimumsuche bei unverschachtelten Listen
2 Minimumsuche mit Hilfe der glätten Funktion
3 Endständig rekursive Minimumsuche
4 Echt rekursive Minimumsuche

Minimumsuche bei unverschachtelten Listen

Eine endständig rekursive Minimumsuche haben wir bei den komplexen Anwendungen zu (unverschachtelten) numerischen Listen kennen gelernt:

(define minimum1
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [(< (car ls) (cadr ls)) (minimum1 (cons (car ls) (cddr ls)))]
      [else
       (minimum1 (cdr ls))])))

(minimum1 '(22 35 45 13 8 7 8 6 14 12 47))

Minimumsuche mit Hilfe der glätten Funktion

Da für das Finden eines Minimums in einer verschachtelten Liste die Struktur der Liste nicht relevant ist, ist es möglich, diese vor dem Berechnen zu glätten.

(define minimum-easy
  (lambda (ls)
    (minimum1 (glaetten ls))))

(minimum-easy '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))

Endständig rekursive Minimumsuche

Dieser Algorithmus lässt sich mit Mehrfachrekursionen auf verschachtelte numerische Listen anwenden:

(define superminimum1
  (lambda (ls)
    ...))

(superminimum1 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))

Echt rekursive Minimumsuche

Die Prozedur minimum2 stellt eine weitere Implementation der Minimumsuche in unverschachtelten numerischen Listen dar. Sie demonstriert die Leistungsstärke echt rekursiver Problemlösungen:

(define minimum2
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [else
       (let ([min (minimum2 (cdr ls))])
         (if (< (car ls) min)
             (car ls)
             min))])))

(minimum2 '(22 35 45 13 8 7 8 6 14 12 47))

Auf dieser Basis lässt sich das "Superminimum" noch einfacher und eleganter realisieren:

(define superminimum2
  (lambda (ls)
    ...))

(superminimum2 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))

Zurück zu Mehrfachrekursionen.

Superminimum

Inhaltsverzeichnis

Minimumsuche bei unverschachtelten Listen

Minimumsuche mit Hilfe der glätten Funktion

Endständig rekursive Minimumsuche

Echt rekursive Minimumsuche

Suche