Superminimum

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2012-12-15T09:12:53+00:00. Aktuelle Version

Endständig rekursive Minimumsuche

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

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

Endständig rekursive Minimumsuche

Echt rekursive Minimumsuche

Suche