contest.tex

数据挖掘中de一个算法 hamster的实例

\name     ``turn hamster'' --- Drehen des Hamsters
\synopsis {\tt void hms\_turn (HAMSTER *hms, int turn); }
\descript Der Hamster {\tt hms} wird um $90^o$ in die Richtung gedreht,
          die der Parameter {\tt turn} angibt. F"ur diesen Parameter
          sind in der Headerdatei {\tt hamster.h} folgende symbolische
          Konstanten definiert: \\[1ex]
          \begin{tabular}{ll}
          \tt HMS\_POS   & Drehen im mathematisch positiven Sinn.   \\
          \tt HMS\_NEG   & Drehen im mathematisch negativen Sinn.   \\
          \tt HMS\_LEFT  & Drehen von der Blickrichtung aus
                           nach links. \\
          \tt HMS\_RIGHT & Drehen von der Blickrichtung aus
                           nach rechts.
          \end{tabular}\\[1ex]
          Die Werte {\tt HMS\_POS} und {\tt HMS\_LEFT} entsprechen
          (bei Blick von oben) einem Drehen gegen den Uhrzeigersinn,
          die Werte {\tt HMS\_NEG} und {\tt HMS\_RIGHT} einem Drehen
          im Uhrzeigersinn.
\result   Die Funktion hat kein Ergebnis.
\end{fndoc}

\begin{fndoc}{hms\_take}
\name     ``take some corn'' --- Aufnehmen einiger Maisk"orner
\synopsis {\tt int hms\_take (HAMSTER *hms, int amount); }
\descript Der Hamster {\tt hms} nimmt so viele Maisk"orner auf, wie
          der Parameter {\tt amount} angibt. Dazu m"ussen nat"urlich
          auf dem aktuellen Feld gen"ugend viele Maisk"orner liegen,
          sonst werden entsprechend weniger Maisk"orner aufgenommen.
          Au\3erdem mu\3 der Hamster noch mindestens {\tt amount}
          Maisk"orner aufnehmen k"onnen. Ist die aktuelle Maiskornlast
          des Hamsters vermehrt um {\tt amount} gr"o\3er als die in der
          Datei {\tt hamster.h} definierte Konstante {\tt HMS\_MAXLOAD},
          so werden ebenfalls entsprechend weniger K"orner aufgenommen.
\result   Die Zahl der tats"achlich aufgenommenen Maisk"orner.
\end{fndoc}

\begin{fndoc}{hms\_drop}
\name     ``drop some corn'' --- Ablegen einiger Maisk"orner
\synopsis {\tt int hms\_drop (HAMSTER *hms, int amount); }
\descript Der Hamster {\tt hms} legt so viele Maisk"orner ab, wie
          der Parameter {\tt amount} angibt. Dazu mu\3 der Hamster
          nat"urlich mindestens {\tt amount} Maisk"orner tragen.
          Tr"agt er weniger, werden auch entsprechend weniger
          Maisk"orner abgelegt. Au\3erdem darf durch die abgelegten
          K"orner der Maiskornhaufen auf dem aktuellen Feld nicht
          gr"o\3er als {\tt HMS\_MAXCORN} Maisk"orner werden
          ({\tt HMS\_MAXCORN} ist in der Headerdatei {\tt hamster.h}
          definiert). Anderenfalls werden entsprechend weniger K"orner
          abgelegt. Letztere Regelung gilt nicht f"ur das Startfeld.
          Auf diesem k"onnen beliebig viele Maisk"orner abgelegt
          werden.
\result   Die Zahl der tats"achlich abgelegten Maisk"orner.
\end{fndoc}

%-----------------------------------------------------------------------

\subsubsection{Die Steuerfunktion}

Die in diesem Abschnitt beschriebene Funktion ist nicht vorgegeben,
sondern vom Wettbewerbsteilnehmer zu schreiben. Sie soll den Hamster
durch das Labyrinth steuern.

\begin{fndoc}{hms\_ctrl}
\name     ``control hamster'' --- Steuern des Hamsters
\synopsis {\tt void hms\_ctrl (HAMSTER *hms); }
\descript Diese Funktion soll den Hamster steuern. Sie ist vom
          Wettbewerbsteilnehmer zu schreiben. Sie wird aufgerufen,
          wenn der Hamster auf dem Startfeld im Labyrinth ausgesetzt
          wurde und "ubernimmt damit die Stelle der Funktion {\tt main}
          in einem normalen C-Programm. Ein Zeiger auf den zu steuernden
          Hamster wird im Funktionsparameter {\tt hms} "ubergeben. Er
          ist den in den beiden vorhergehenden Abschnitten beschriebenen
          Funktionen zu "ubergeben, wenn Informationen "uber den Hamster
          oder das Feld, auf dem er sich befindet, geholt werden sollen,
          oder wenn der Hamster eine Handlung ausf"uhren soll.
          Die Funktion sollte erst dann beendet werden, wenn so viele
          Maisk"orner gesammelt wurden wie m"oglich.
\result   Die Funktion hat kein Ergebnis.
\end{fndoc}

%-----------------------------------------------------------------------

\subsection{Programmierschnittstelle f"ur Eiffel}
\label{sec.ctrl.eiffel}

Die Programmierschnittstelle f"ur die Programmiersprache Eiffel besteht
aus der Datei {\tt hamster.e}, die die Klasse {\tt HAMSTER} definiert,
und der Datei {\tt client.e}, die eine Basis-Steuerklasse zur
Verf"ugung stellt. Um ein eigenes Hamster-Steuerprogramm zu schreiben,
mu\3 letztere Klasse beerbt und die Methode {\tt control} redefiniert
werden. Aus dieser Methode k"onnen dann die Methoden der Hamsterklasse
{\tt HAMSTER} aufgerufen werden, um den Hamster zu steuern.

%-----------------------------------------------------------------------

\subsubsection{Konstanten}

In der Datei {\tt hamster.e} sind folgende Konstanten definiert,
die Eigenschaften des Hamsters und des Labyrinthes festlegen, sowie
R"uckgabewerte und Parameter von Hamstermethoden leichter verst"andlich
machen.

\paragraph*{Labyrinthausdehnung}
\begin{verbatim}
max_x:      INTEGER is  64;     -- maximal x-extension of maze
max_y:      INTEGER is  64;     -- maximal y-extension of maze
\end{verbatim}
Das Labyrinth kann h"ochstens
{\tt max\_x} $\times$ {\tt max\_y} Felder gro\3 sein.

\paragraph*{Maishaufengr"o\3e}
\begin{verbatim}
max_corn:   INTEGER is 255;     -- maximal size of corn heap
\end{verbatim}
Die Gr"o\3e eines Maiskornhaufens auf einem Labyrinthfeld kann
h"ochstens {\tt max\_corn} Maisk"orner betragen. Dies gilt
jedoch nur f"ur "`normale"' Labyrinthfelder. Auf dem Startfeld
k"onnen beliebig viele K"orner abgelegt werden.

\paragraph*{Tragkapazit"at des Hamsters}
\begin{verbatim}
max_load:   INTEGER is  12;     -- maximal load of corn in cheeks
\end{verbatim}
Der Hamster kann h"ochstens {\tt max\_load} Maisk"orner
gleichzeitig tragen.

\paragraph*{Ergebnisse der Methode {\tt get\_dir}}
\begin{verbatim}
east:       INTEGER is   0;     -- hamster is looking east
north:      INTEGER is   1;     -- hamster is looking north
west:       INTEGER is   2;     -- hamster is looking west
south:      INTEGER is   3;     -- hamster is looking south
\end{verbatim}
Die Blickrichtung des Hamsters wird als ganze Zahl kodiert. Namen von
Himmelsrichtungen sind jedoch sicherlich aussagekr"aftiger als Zahlen.

\paragraph*{Ergebnisse der Methode {\tt get\_look}}
\begin{verbatim}
empty:      INTEGER is   0;     -- there is an empty field ahead
corn:       INTEGER is   1;     -- there is a field with corn ahead
wall:       INTEGER is   2;     -- there is a wall ahead
\end{verbatim}
Der Ausblick des Hamsters wird als ganze Zahl kodiert. Namen wie
{\tt empty} (das in Blickrichtung voraus liegende Feld ist leer),
{\tt corn} (auf dem in Blickrichtung voraus liegenden Feld liegt Mais)
und {\tt wall} (voraus liegt eine Wand) sind jedoch sicherlich
aussagekr"aftiger als Zahlen.

\paragraph*{Parameter der Methode {\tt turn}}
\begin{verbatim}
pos:        INTEGER is   1;     -- positive turn (counterclockwise)
neg:        INTEGER is  -1;     -- negative turn (clockwise)
left:       INTEGER is   1;     -- left     turn (counterclockwise)
right:      INTEGER is  -1;     -- right    turn (clockwise)
\end{verbatim}
Der Methode {\tt turn} mu\3 als Parameter die Richtung angegeben
werden, in die sich der Hamster drehen soll. Dies geschieht durch
eine positive oder negative Zahl. Auch hier sind Namen wie {\tt pos}
(Drehen im mathematisch positiven Sinn), {\tt neg} (Drehen im
mathematisch negativen Sinn), {\tt left} (Drehen von der
Blickrichtung nach links) und {\tt right} (Drehen von der
Blickrichtung nach rechts) aussagekr"aftiger als Zahlen.
Die Werte {\tt pos} und {\tt left} entsprechen (bei Blick von oben)
einem Drehen gegen den Uhrzeigersinn, die Werte {\tt neg} und
{\tt right} einem Drehen im Uhrzeigersinn.

%-----------------------------------------------------------------------

\subsubsection{Auskunftsfunktionen}

Mit den in diesem Abschnitt beschriebenen Methoden k"onnen Informationen
"uber den Hamster und die Lage, in der er sich befindet, geholt werden.

\begin{fndoc}{get\_x}
\name     ``get current hamster x-position'' ---
          Bestimmen der aktuellen $x$-Position des Hamsters
\synopsis {\tt get\_x: INTEGER}
\descript Es wird die $x$-Position des Hamsters im Labyrinth
          relativ zum Startfeld bestimmt.
\result   Die $x$-Position des Hamsters relativ zum Startfeld. 
\end{fndoc}
          
\begin{fndoc}{get\_y}
\name     ``get current hamster y-position'' ---
          Bestimmen der aktuellen $y$-Position des Hamsters
\synopsis {\tt get\_y: INTEGER}
\descript Es wird die $y$-Position des Hamsters im Labyrinth
          relativ zum Startfeld bestimmt.
\result   Die $y$-Position des Hamsters relativ zum Startfeld.
\end{fndoc} 

\bigskip\bigskip\noindent
{\tt get\_x} und {\tt get\_y} liefern die Labyrinthposition des
Hamsters. Die Koordinaten wachsen von West nach Ost und von S"ud
nach Nord. Sie beziehen sich {\em nicht\/} auf die linke untere Ecke
des Labyrinthes, sondern auf das Startfeld des Hamsters. Die Koordinaten
k"onnen also auch negativ werden, n"amlich dann, wenn sich der Hamster
westlich und/oder s"udlich des Startfeldes befindet. Das Startfeld
selbst hat die Koordinaten $(0,0)$.

\begin{fndoc}{get\_dir}
\name     ``get current hamster direction'' ---
          Bestimmen der aktuellen Hamsterblickrichtung
\synopsis {\tt get\_dir: INTEGER }
\descript Es wird die Blickrichtung des Hamsters ermittelt
          und die Himmelsrichtung zur"uckgegeben, und zwar kodiert
          als ganze Zahl. F"ur diese Zahlen sind in der Datei
          {\tt hamster.e} symbolische Konstanten definiert, und zwar:
          \\[1ex]
          \begin{tabular}{@{}ll}
          \tt east  & Der Hamster  schaut nach Osten.  \\
          \tt north & Der Hamster  schaut nach Norden. \\
          \tt west  & Der Hamster  schaut nach Westen. \\
          \tt south & Der Hamster  schaut nach S"uden.
          \end{tabular}
\result   Einer der Werte {\tt east}, {\tt north},
          {\tt west} oder {\tt south}.
\end{fndoc}

\begin{fndoc}{get\_load}
\name     ``get current hamster load'' ---
          Bestimmen der aktuellen Maiskornlast des Hamsters
\synopsis {\tt get\_load: INTEGER}
\descript Es wird die Anzahl der Maisk"orner ermittelt, die der
          Hamster  gerade tr"agt. Diese Zahl liegt zwischen 0
          (einschlie\3lich) und der in der Datei {\tt hamster.e}
          definierten Zahl {\tt max\_load} (einschlie\3lich).
\result   Die Zahl der getragenen Maisk"orner.
\end{fndoc}

\begin{fndoc}{get\_corn}
\name     ``get amount of corn on current field'' ---
          Bestimmen der Kornmenge auf dem aktuellen Feld
\synopsis {\tt get\_corn: INTEGER }
\descript Es wird die Anzahl der Maisk"orner bestimmt, die auf dem
          Feld liegen, auf dem sich der Hamster gerade befindet.
\result   Die Zahl der Maisk"orner auf dem aktuellen Feld.
\end{fndoc}

\begin{fndoc}{get\_look}
\name     ``get hamster's current outlook'' ---
          Bestimmen des aktuellen Ausblicks des Hamsters
\synopsis {\tt get\_look: INTEGER }
\descript Es wird der Ausblick des Hamsters bestimmt und kodiert als
          ganze Zahl zur"uckgegeben. F"ur diese Zahlen sind in der Datei
          {\tt hamster.e} symbolische Konstanten definiert, und zwar:
          \\[1ex]
          \begin{tabular}{@{}ll}
          \tt empty & Vor dem Hamster liegt ein leeres Feld. \\
          \tt corn  & Vor dem Hamster liegt ein Feld, 
                      auf dem sich Mais befindet. \\
          \tt wall  & Vor dem Hamster steht eine Wand.
          \end{tabular}\\[1ex]
          Bei R"uckgabe des Wertes {\tt corn} erf"ahrt man nur, da\3
          auf dem voraus liegenden Feld Mais liegt, nicht jedoch (da
          der Hamster kurzsichtig ist), wieviel dort liegt. Um die
          Anzahl der Maisk"orner auf dem Feld zu bestimmen, mu\3 der
          Hamster es betreten. Dann kann die Zahl der Maisk"orner mit
          Hilfe der Funktion {\tt get\_corn} ermittelt  werden.
\result   Einer der Werte {\tt empty}, {\tt corn} oder {\tt wall}.
\end{fndoc}

%-----------------------------------------------------------------------

\subsubsection{Handlungsfunktionen}

Mit den in diesem Abschnitt beschriebenen Methoden k"onnen Handlungen
des Hamster ausgel"ost werden.