\documentclass{bschlangaul-aufgabe}
\bLadePakete{java}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Greedy-Münzwechsler},
  Thematik = {Münzwechsler},
  Referenz = AUD.Algorithmenmuster.Greedy-Algorithmen.Muenzwechsler,
  RelativerPfad = Module/30_AUD/60_Algorithmenmuster/20_Greedy-Algorithmen/Aufgabe_Muenzwechsler.tex,
  ZitatSchluessel = aud:ab:3,
  ZitatBeschreibung = {Seite 1, Greedy-Münzwechsler, Aufgabe 1},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Greedy-Algorithmus},
}

\begin{enumerate}

%%
% (a)
%%

\item Nehmen Sie an, es stehen beliebig viele 5-Cent, 2-Cent und
1-Cent-Münzen zur Verfügung. Die Aufgabe besteht darin, für einen
gegebenen Cent-Betrag möglichst wenig Münzen zu verbrauchen. Entwerfen
Sie eine Methode\index{Greedy-Algorithmus}
\footcite[Seite 1, Greedy-Münzwechsler, Aufgabe 1]{aud:ab:3}

\begin{minted}{java}
public void wechselgeld (int n)
\end{minted}

die diese Aufgabe mit einem Greedy-Algorithmus löst und für den Betrag
von $n$ Cent die Anzahl $c5$ der 5-Cent-Münzen, die Anzahl $c2$ der
2-Cent-Münzen und die Anzahl $c1$ der 1-Cent-Münzen berechnet und diese
auf der Konsole ausgibt. Sie können dabei den Operator \texttt{/} für
die ganzzahlige Division und den Operator $\%$ für den Rest bei der
ganzzahligen Division verwenden.
\footnote{Quelle möglicherweise von \url{https://www.yumpu.com/de/document/read/17936760/ubungen-zum-prasenzmodul-algorithmen-und-datenstrukturen}}

\begin{bAntwort}
\bJavaDatei[firstline=19,lastline=28]{aufgaben/aud/muster/greedy/Muenzwechsler}
\end{bAntwort}

%%
% (b)
%%

\item Es kann gezeigt werden, dass der Greedy-Algorithmus für den obigen
Fall der Münzwerte 5, 2 und 1 optimal ist, \dh dass er immer die
Gesamtzahl der Münzen minimiert. Nehmen Sie nun an, es gibt die
Münzwerte 5 und 1. Ist es dann möglich, einen dritten Münzwert so zu
wählen, dass der Greedy-Algorithmus mit den drei Münzen nicht mehr
optimal ist? Begründen Sie Ihre Antwort.

\begin{bAntwort}
Falls der dritte Münzwert 4 ist, ist der Greedy-Algorithmus nicht mehr
optimal. Der Greedy-Algorithmus benutzt zunächst so viele 5-Cent-Münzen
wie möglich und dann so viele 4-Cent-Münzen wie möglich. Ein Betrag von
8 Cent wird also in eine 5-Cent und drei 1-Cent-Münzen aufgeteilt.
Optimal ist aber die Aufteilung in zwei 4-Cent-Münzen.
\end{bAntwort}
\end{enumerate}

\begin{bAdditum}
\bJavaDatei{aufgaben/aud/muster/greedy/Muenzwechsler}
\end{bAdditum}
\end{document}