Superminimum

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Minimumsuche bei unverschachtelten Listen 2 Minimumsuche mit Hilfe der Glättungsprozedur 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))

ausführen

(define glaetten (lambda (ls) (cond [(null? ls) ls] [(list? (car ls)) (append (glaetten (car ls)) (glaetten (cdr ls)))] [else (cons (car ls) (glaetten (cdr ls)))])))

Minimumsuche mit Hilfe der Glättungsprozedur

Zunächst greifen wir einen naheliegenden Gedanken auf: Da für die Minimumsuche die Struktur der Liste nicht relevant ist, glätten wir sie, um sie dann der Minimumsuche unverschachtelter Listen zu unterziehen.

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

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

ausführen

Endständig rekursive Minimumsuche

Nun wollen wir die oben angegebene endständig rekursive Prozedur minimum1 zur (Super-)Minimumsuche in verschachtelte numerische Listen erweitern:

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

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

ausführen

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

ausführen

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

ausführen

Zurück zu Mehrfachrekursionen.