\documentclass{bschlangaul-aufgabe}
\bLadePakete{mathe}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 1},
  Thematik = {Cent-Münzen},
  Referenz = 66115-2007-F.T2-A1,
  RelativerPfad = Examen/66115/2007/03/Thema-2/Aufgabe-1.tex,
  ZitatSchluessel = examen:66115:2007:03,
  ZitatBeschreibung = {Thema 1 Aufgabe 1},
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Greedy-Algorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2007,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 1,
}

\begin{enumerate}

%%
% a)
%%

\item Beschreiben Sie in Pseudocode oder einer Programmiersprache Ihrer
Wahl einen Greedy-Algorithmus, der einen Betrag von $n$ Cents mit
möglichst wenigen Cent-Münzen herausgibt. Bei $n = 29$ wäre die
erwartete Antwort etwa $1 \times 20 \text{ct}$, $1 \times 5 \text{ct}$,
$2 \times 2 \text{ct}$.
\index{Greedy-Algorithmus}
\footcite[Thema 1 Aufgabe 1]{examen:66115:2007:03}

%%
% b)
%%

\item Beweisen Sie die Korrektheit Ihres Verfahrens, also dass
tatsächlich die Anzahl der Münzen minimiert wird.

%%
% c)
%%

\item Nehmen wir an, Bayern führe eine Sondermünze im Wert von 7ct ein.
Dann liefert der naheliegende Greedy-Algorithmus nicht immer die
minimale Zahl von Münzen. Geben Sie für dieses Phänomen ein konkretes
Beispiel an und führen Sie aus, warum Ihr Beweis aus Aufgabenteil a) in
dieser Situation nicht funktioniert.
\end{enumerate}

\end{document}