Grundlagen der funktionsorientierten Programmierung mit SCHEME/Superminimum

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
== Minimumsuche bei unverschachtelten Listen ==
Eine endständig rekursive  Minimumsuche haben wir bei den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Numerische Listen#Kleinstes Listenelement|komplexen Anwendungen zu (unverschachtelten) numerischen Listen]] kennen gelernt:

<code id="50c91a91b1878">
(define minimum1
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [(< (car ls) (cadr ls)) (minimum1 (cons (car ls) (cddr ls)))]
      [else
       (minimum1 (cdr ls))])))
</code>

<run id="50c91a91b1b62">
(minimum1 '(22 35 45 13 8 7 8 6 14 12 47))
</run>

<code id="5c4b04780426c" hidden>
(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)))])))
</code>

== Minimumsuche mit Hilfe der Glättungsprozedur ==

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

<code id="5c4b10807c0c3">
(define superminimum-easy
  (lambda (ls)
    (minimum1 (glaetten ls))))
</code>

<run id="5c4b10807c1bd">
(superminimum-easy '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))
</run>

== Endständig rekursive Minimumsuche ==

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

<code id="50c91a91b199a">
(define superminimum1
  (lambda (ls)
    ...))
</code>

<check>
(and (= (superminimum1 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47))) 6)
     (= (superminimum1 '(22 35 45 13 8 7 8 6 14 12 47)) 6)
     (= (superminimum1 '(22)) 22))
</check>

<run id="50c91a91b1bc9">
(superminimum1 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))
</run>

== Echt rekursive Minimumsuche ==

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

<code id="50c91a91b1a10">
(define minimum2
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [else
       (let ([min (minimum2 (cdr ls))])
         (if (< (car ls) min)
             (car ls)
             min))])))
</code>

<run id="50c91a91b1c33">
(minimum2 '(22 35 45 13 8 7 8 6 14 12 47))
</run>

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

<code id="50c91a91b1a77">
(define superminimum2
  (lambda (ls)
    ...))
</code>  

<check>
(and (= (superminimum2 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47))) 6)
     (= (superminimum2 '(22 35 45 13 8 7 8 6 14 12 47)) 6)
     (= (superminimum2 '(22)) 22))
</check>

<run id="50c91a91b1cd0">
(superminimum2 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))
</run>

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen|Mehrfachrekursionen]].