i1rek2.tex

% Diese Datei ist Teil des Buchs "Schreibe Dein Programm!"
% Das Buch ist lizensiert unter der Creative-Commons-Lizenz
% "Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International (CC BY-SA 4.0)"
% https://creativecommons.org/licenses/by-sa/4.0/deed.de

\chapter{Fortgeschrittenes Programmieren mit Rekursion}
\label{cha:recursion-advanced}

FIXME: Vielleicht sowas wie Mergesort, parallele Listenverarbeitung

\section{Lastwagen optimal beladen}

FIXME: Backtracking sagen

Hier ist ein weiteres Problem, zu dessen Lösung 
Listen hervorragend taugen:
Die Aufgabe ist, einen Lastwagen optimal auszulasten: Aus einem Lager mit zu
transportierenden Artikeln, jeder mit einem bestimmten Gewicht, sind solche Artikel
auszuwählen, dass die Tragfähigkeit des Lastwagens möglichst gut ausgeschöpft
wird.

Für die Lösung muss erst einmal festgelegt werden, wie Ein- und Ausgabe
des Programms aussehen sollen.  Die elementare Größe im Problem ist
ein \textit{Artikel}, der aus einer Artikelnummer und seinem Gewicht
besteht.  Folgende Daten- und Record-Definition passen dazu:\index{title@\texttt{title}}
%
\begin{alltt}
; Ein Artikel ist ein Wert
;  (make-article n w)
; wobei n die Nummer des Artikels ist
; und w das Gewicht des Artikels in Kilo
(define-record-procedures article
  make-article article?
  (article-number article-weight))
\end{alltt}
%
Ein Beispiel-Lager wird durch die folgende
Liste beschrieben:
%
\begin{alltt}
; Ein Beispiel-Lager
(: stock (list(article))
(define stock
  (list (make-article 1 274)
        (make-article 2 203)
        (make-article 3 268)
        (make-article 4 264)
        (make-article 5 229)
        (make-article 6 406)
        (make-article 7 220)
        (make-article 8 232)
        (make-article 9 356)
        (make-article 10 197)
        (make-article 11 207)
        (make-article 12 373)))
\end{alltt}
%
Die Lösung des Problems soll eine Funktion \texttt{load-list}
sein, welche eine Liste der Artikel zurückliefert, die in den Lastwagen geladen
werden sollen.  Neben der Liste der Artikel braucht
\texttt{load-list} auch noch die Tragfähigkeit eines Lastwagens.  Die
Funktion soll Kurzbeschreibung und Signatur wie folgt haben:\index{load-list@\texttt{load-list}}
%
\begin{alltt}
; Maximale Liste von Artikeln berechnen, 
; die auf einen Lastwagen passen
(: load-list (list(article) number -> list(article))
\end{alltt}
%
Im Fall des Beispiel-Lagers und eines Lastwagens mit 1800 kg Tragfähigkeit
soll folgendes
passieren, wenn das Programm fertig ist:
%
\begin{alltt}
(load-list stock 1800)
\evalsto{} #<list #<record:article 1 274> #<record:article 2 203>
          #<record:article 3 268> #<record:article 6 406>
          #<record:article 7 220> #<record:article 8 232> 
          #<record:article 10 197>>
\end{alltt}
%
Die Funktion arbeitet auf Listen, was folgende Schablone nahelegt:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) ...)
     ((cons? articles)
      ... (first articles) ...
      ... (load-list (rest articles) capacity) ...))))
\end{alltt}
%
Wenn keine Artikel da sind, kommen
auch keine in den Lastwagen.  Die Liste im ersten Zweig ist also leer.  Der
zweite Fall ist etwas komplizierter.
Das liegt daran, dass es dort
eine weitere Fallunterscheidung gibt, je nach dem ersten Artikel
\texttt{(first articles)}:
die Funktion muss entscheiden, ob dieser erste
Artikel schließlich in den Lastwagen kommen soll oder nicht.
Ein erstes Ausschlußkriterium ist, wenn der Artikel schwerer ist als die
Tragfähigkeit erlaubt:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) empty)
     ((cons? articles)
        (if (> (article-weight (first articles)) capacity)
            (load-list (rest articles) capacity)
            ... (load-list (rest articles) capacity) ...)))))
\end{alltt}
%
Damit ist die Frage, ob der erste Artikel im Lastwagen landet, aber immer
noch nicht abschließend beantwortet.  Schließlich muss
\texttt{load-list} noch entscheiden, ob unter Verwendung dieses
Artikels der Lastwagen optimal vollgepackt werden
kann.  Dazu muss die Funktion vergleichen, wie ein Lastwagen \emph{mit}
dem ersten Artikel und wie er \emph{ohne} diesen Artikel am besten
vollgepackt werden würde.   Die Variante "<ohne"> wird mit folgendem
Ausdruck ausgerechnet:
%
\begin{alltt}
  (load-list (rest articles) capacity)
\end{alltt}
%
Die Variante "<mit"> ist etwas trickreicher~-- sie entsteht, wenn im
Lastwagen der Platz für den ersten Artikel reserviert wird und
der Rest der Tragfähigkeit mit den restlichen Artikeln optimal gefüllt wird.
Die optimale Füllung für den Rest wird mit folgendem Ausdruck
berechnet, der die Induktionsannahme für \texttt{load-list} benutzt:
%
\begin{alltt}
  (load-list (rest articles) 
                 (- capacity (article-weight (first articles))))
\end{alltt}
%
Die vollständige Artikelliste entsteht dann durch nachträgliches
Wieder-Anhängen des ersten Artikels:
%
\begin{alltt}
  (cons (first articles)
             (load-list (rest articles)
                            (- capacity (article-weight (first articles)))))
\end{alltt}
%
Diese beiden Listen müssen jetzt nach ihrem Gesamtgewicht verglichen
werden.  Die Liste mit dem größeren Gewicht gewinnt.  Als erster
Schritt werden die beiden obigen Ausdrücke in die Schablone eingefügt:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) empty)
     ((cons? articles)
        (if (> (article-weight (first articles)) capacity)
            (load-list (rest articles) capacity)
            ... (load-list (rest articles) capacity) ...
            ... (cons (first articles)
                           (load-list
                             (rest articles)
                             (- capacity
                                (article-weight (first articles)))))
            ...)))))
\end{alltt}
%
Die Ausdrücke für die beiden Alternativen sind in dieser Form 
unhandlich groß, was die Funktion schon unübersichtlich macht, bevor
sie überhaupt fertig ist.
Es lohnt sich also, ihnen Namen zu geben:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) empty)
     ((cons? articles)
        (if (> (article-weight (first articles)) capacity)
            (load-list (rest articles) capacity)
            (let ((articles-1 (load-list (rest articles) capacity))
                  (articles-2
                    (cons (first articles)
                               (load-list
                                 (rest articles)
                                 (- capacity 
                                    (article-weight (first articles)))))
              ...))))))))
\end{alltt}
%
Der Ausdruck
\texttt{(article-weight (first articles))} kommt zweimal vor.  Die Einführung einer
weiteren lokalen Variable macht die Funktion noch übersichtlicher:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) empty)
     ((cons? articles)
      (let ((first-weight (article-weight (first articles))))
        (if (> first-weight capacity)
            (load-list (rest articles) capacity)
            (let ((articles-1 (load-list (rest articles) capacity))
                  (articles-2
                    (cons (first articles)
                               (load-list
                                 (rest articles)
                                 (- capacity first-weight)))
              ...)))))))))
\end{alltt}
%
Zurück zur eigentlichen Aufgabe: \texttt{articles-1} und
\texttt{articles-2} sollen hinsichtlich ihres Gewichts verglichen werden.
Dies muss natürlich berechnet werden.  Da dafür noch eine Funktion
fehlt, kommt Wunschdenken zur Anwendung:\index{articles-weight@\texttt{articles-weight}}
%
\begin{alltt}
; Gesamtgewicht einer Liste von Artikeln berechnen
(: articles-weight (list(article) -> number)
\end{alltt}
% 
Damit kann \texttt{load-list} vervollständigt werden:
%
\begin{alltt}
(define load-list
  (lambda (articles capacity)
    (cond
     ((empty? articles) empty)
     ((cons? articles)
      (let ((first-weight (article-weight (first articles))))
        (if (> first-weight capacity)
            (load-list (rest articles) capacity)
            (let ((articles-1 (load-list (rest articles) capacity))
                  (articles-2
                   (cons (first articles)
                              (load-list
                                (rest articles) 
                                (- capacity first-weight)))))
              (if (> (articles-weight articles-1)
                     (articles-weight articles-2))
                  articles-1
                  articles-2))))))))
\end{alltt}
%
Es fehlt noch \texttt{articles-weight}, die wieder streng nach Anleitung
geht und für welche die Schablone folgendermaßen aussieht:
%
\begin{alltt}
(define articles-weight
  (lambda (articles)
    (cond
     ((empty? articles) ...)
     ((cons? articles)
      ... (first articles) ...
      ... (articles-weight (rest articles)) ...))))
\end{alltt}
%
Das Gesamtgewicht der leeren Liste ist 0~-- der erste Fall ist also
wieder einmal einfach.  Im zweiten Fall interessiert vom ersten
Artikel nur das Gewicht:
%
\begin{alltt}
(define articles-weight
  (lambda (articles)
    (cond
     ((empty? articles) 0)
     ((cons? articles)
      ... (article-weight (first articles)) ...
      ... (articles-weight (rest articles)) ...))))
\end{alltt}
%
Nach Induktionsannahme liefert \texttt{(articles-weight (rest articles))} das
Gewicht der restlichen Artikel.  Das Gewicht des ersten Artikels muss also
nur addiert werden:
%
\begin{alltt}
(define articles-weight
  (lambda (articles)
    (cond
     ((empty? articles) 0)
     ((cons? articles)
      (+ (article-weight (first articles))
         (articles-weight (rest articles)))))))
\end{alltt}
%
Mit \texttt{articles-weight} lässt sich bestimmen, wie voll der
Lastwagen beladen ist.  Im Falle von \texttt{stock} ist das
Ergebnis sehr erfreulich; kein Platz wird verschenkt:
%
\begin{alltt}
(articles-weight (load-list stock 1800))
\evalsto{} 1800
\end{alltt}

\section*{Aufgaben}

\begin{aufgabe}\label{ex:coke-finances}
  Schreiben Sie eine Funktion \texttt{drink-machine}, die das
  Finanzmanagement eines Getränkeautomaten durchführt.
  
  \texttt{Drink-machine} soll drei Argumente akzeptieren: den Preis eines
  Getränks (in Euro-Cents), eine Liste der Centbeträge der
  Wechselgeldmünzen, die noch im Automaten sind, und den Geldbetrag,
  den der Kunde eingeworfen hat.  (Also gibt es ein Listenelement pro
  Münze. Falls z.B.\ mehrere Groschen im Automaten sind, finden sich
  in der Liste mehrmals die Zahl 10.)  Herauskommen soll eine Liste
  der Centbeträge der Münzen, welche die Maschine herausgibt oder
  \verb|#f|, falls die Maschine nicht herausgeben kann.
  %
\begin{alltt}
(drink-machine 140 (list 50 100 500 10 10) 200)
\evalsto{} #<list 50 10>
(drink-machine 140 (list 50 20 20 20) 200)
\evalsto{} #<list 20 20 20>
\end{alltt}
\end{aufgabe}


\begin{aufgabe}
  Schreiben Sie eine Funktion \texttt{backlog-list}, welche die
  gleichen Eingaben wie \texttt{load-list} akzeptiert, aber die
  nach dem Beladen eines Lastwagens im Lager zurückbleibenden Artikel
  zurückgibt.  Die Funktion soll 
  \texttt{load-list} als Hilfsfunktion verwenden.
\end{aufgabe}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "i1"
%%% End: