Superminimum

Aus ProgrammingWiki

< Grundlagen der funktionsorientierten Programmierung mit SCHEME

Archivierte Version vom 2012-12-14T23:29:28+00:00. Aktuelle Version

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

Die Prozedur minimum2 stellt eine weitere Implementation der Minimumsuche in unverschachtelten numerischen Listen dar. Sie demonstriert die Leistungsstärke echtrekursiver 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

Suche