contest.tex

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

Maisk"ornern liegen, die zwischen 0 K"ornern (kein Maiskornhaufen)
und 255 K"ornern enthalten k"onnen.

Ein solches Labyrinth kann automatisch (und dann zuf"allig) "uber
den Men"ueintrag {\tt Actions > Randomize Maze...} (siehe
Abschnitt~\ref{sec.menu.actions}) oder manuell mit der Maus (siehe
Abschnitt~\ref{sec.mouse}) erzeugt werden. Erzeugt wird ein Labyrinth,
indem W"ande gesetzt und Maisk"orner verteilt werden.

Ein Feld des Labyrinthes ist ausgezeichnet --- im Labyrinthfenster
an der grauen Farbe erkennbar. Auf diesem Feld wird der Hamster in das
Labyrinth gesetzt. Auf dieses Feld mu\3 der Hamster auch die von ihm
gesammelten Maisk"orner ablegen. Erst wenn sie auf diesem Feld abgelegt
sind, gelten sie als f"ur den Wintervorrat gesammelt und werden in der
Punktzahl verbucht.

Der Hamster kann sich im Labyrinth bewegen, indem er in Blickrichtung
auf das n"achste Feld tritt (siehe Funktion {\tt hms\_move} bzw.\
Methode {\tt move}) und indem er sich um $90^o$ im oder gegen den
Uhrzeigersinn dreht (siehe Funktion {\tt hms\_turn} bzw.\ Methode
{\tt turn}). Damit man den Hamster nicht vor Labyrinthw"ande
steuert, kann man abfragen, was der Hamster vor sich sieht
(siehe Funktion {\tt hms\_look} bzw.\ Methode {\tt get\_look}).

Der Hamster kann sich im Labyrinth orientieren, indem er seine
Positionskoordinaten abfragt (siehe Funktion {\tt hms\_pos} bzw.\
Methoden {\tt get\_x} und {\tt get\_y}). Diese Koordinaten werden stets
relativ zum Ausgangsfeld angegeben, das die Koordinaten $(0,0)$ hat.
Die $x$-Koordinate ist westlich (links) vom Ausgangsfeld negativ und
"ostlich (rechts) positiv. Die $y$-Koordinate ist s"udlich (unterhalb)
des Ausgangsfeldes negativ und n"ordlich (oberhalb) positiv.
Die Blickrichtung des Hamsters kann ebenfalls ermittelt werden (siehe
Funktion {\tt hms\_dir} bzw.\ Methode {\tt get\_dir}).

Der Hamster kann auch die Anzahl Maisk"orner z"ahlen, die auf dem
Feld liegen, auf dem er sich gerade befindet (siehe Funktion
{\tt hms\_corn} bzw.\ Methode {\tt get\_corn}). Er kann von diesem
Feld Maisk"orner aufnehmen (siehe Funktion {\tt hms\_take} bzw.\
Methode {\tt take}) oder auf dieses Feld Maisk"orner ablegen (siehe
Funktion {\tt hms\_drop} bzw.\ Methode {\tt drop}).

Der Hamster kann nicht beliebig viele Maisk"orner tragen. Seine
Backen haben eine begrenzte Kapazit"at: nur zw"olf Maisk"orner
passen hinein. Wie viele K"orner der Hamster gerade tr"agt, kann
abgefragt werden (siehe Funktion {\tt hms\_load} bzw.\ Methode
{\tt get\_load}) Versucht der Hamster, mehr als zw"olf K"orner
aufzunehmen, werden die "uberz"ahligen K"orner liegengelassen (siehe
Funktion {\tt hms\_take} bzw.\ Methode {\tt take}). Gleiches gilt, wenn
er versucht, auf einem Feld des Labyrinthes mehr als 255 Maisk"orner
anzuh"aufen (siehe Funktion {\tt hms\_drop} bzw.\ Methode {\tt drop}).
Die nicht mehr auf das Feld passenden K"orner verbleiben in seinen
Backen. Diese Einschr"ankung gilt jedoch nicht f"ur das Ausgangsfeld.
Auf diesem Feld k"onnen beliebig viele K"orner abgelegt werden. Es ist
immer leer, da die hier abgelegten K"orner direkt in den Wintervorrat
aufgenommen werden.

Die zur Steuerung des Hamsters ben"otigten Funktionen sind in der
Datei {\tt hamster.h} bzw.\ in der Datei {\tt hamster.e} definiert.
Diese Dateien enthalten au\3erdem Definitionen von Konstanten, die
z.B.\ f"ur die Auswertung der R"uckgaben einiger Funktionen bzw.\
Methoden n"utzlich sein k"onnen. Im folgenden werden diese Definitionen
programmiersprachenabh"angig im einzelnen besprochen.

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

\subsection{Programmierschnittstelle f"ur C}
\label{sec.ctrl.c}

Die Programmierschnittstelle f"ur die Programmiersprache~C ist durch
die Header-Datei {\tt hamster.h} definiert. Diese Datei mu\3 mit
{\tt \#include \char34hamster.h\char34} in die Datei eingebunden
werden, die das (zu schreibende) Hamster-Steuerprogramm enth\"alt.

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

\subsubsection{Typdefinitionen}

In der Datei {\tt hamster.h} ist der Typ {\tt HAMSTER} definiert,
durch den ein Hamster dargestellt wird.
\begin{verbatim}
typedef struct hamster HAMSTER; /* a hamster */
\end{verbatim}
Die genaue Definition (welche Felder die Hamsterstruktur enth"alt)
ist jedoch verborgen. Erstens, weil die sich die Definition der
Hamsterstruktur f"ur das Labyrinth- und f"ur das Steuerprogramm
unterscheiden, und zweitens um jeder Versuchung, auf Felder der
Hamsterstruktur direkt zuzugreifen, von vornherein dadurch
vorzubeugen, da\3 diese Felder gar nicht bekanntgegeben werden.

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

\subsubsection{Konstanten}

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

\paragraph*{Labyrinthausdehnung}
\begin{verbatim}
#define HMS_MAXXEXT   64        /* maximal x-extension of maze */
#define HMS_MAXYEXT   64        /* maximal y-extension of maze */
\end{verbatim}
Das Labyrinth kann h"ochstens
{\tt HMS\_MAXXEXT} $\times$ {\tt HMS\_MAXYEXT} Felder gro\3 sein.

\paragraph*{Maishaufengr"o\3e}
\begin{verbatim}
#define HMS_MAXCORN  255        /* maximal size of corn heap */
\end{verbatim}
Die Gr"o\3e eines Maiskornhaufens auf einem Labyrinthfeld kann
h"ochstens {\tt HMS\_MAXCORN} 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}
#define HMS_MAXLOAD   12        /* maximal load of corn in cheeks */
\end{verbatim}
Der Hamster kann h"ochstens {\tt HMS\_MAXLOAD} Maisk"orner
gleichzeitig tragen.

\paragraph*{Ergebnisse der Funktion {\tt hms\_dir}}
\begin{verbatim}
#define HMS_EAST       0        /* hamster is looking east */
#define HMS_NORTH      1        /* hamster is looking north */
#define HMS_WEST       2        /* hamster is looking west */
#define HMS_SOUTH      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 Funktion {\tt hms\_look}}
\begin{verbatim}
#define HMS_EMPTY      0        /* there is an empty field ahead */
#define HMS_CORN       1        /* there is a field with corn ahead */
#define HMS_WALL       2        /* there is a wall ahead */
\end{verbatim}
Was der Hamster sieht, wird als ganze Zahl kodiert. Namen wie
{\tt HMS\_EMPTY} (das in Blickrichtung voraus liegende Feld ist
leer), {\tt HMS\_CORN} (auf dem in Blickrichtung voraus liegenden
Feld liegt Mais) und {\tt HMS\_WALL} (voraus liegt eine Wand)
sind jedoch sicherlich aussagekr"aftiger als Zahlen.

\paragraph*{Parameter der Funktion {\tt hms\_turn}}
\begin{verbatim}
#define HMS_POS        1        /* positive turn (counterclockwise) */
#define HMS_NEG       -1        /* negative turn (clockwise) */
#define HMS_LEFT       1        /* left     turn (counterclockwise) */
#define HMS_RIGHT     -1        /* right    turn (clockwise) */
\end{verbatim}
Der Funktion {\tt hms\_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 HMS\_POS}
(Drehen im mathematisch positiven Sinn), {\tt HMS\_NEG} (Drehen im
mathematisch negativen Sinn), {\tt HMS\_LEFT} (Drehen von der
Blickrichtung nach links) und {\tt HMS\_RIGHT} (Drehen von der
Blickrichtung nach rechts) aussagekr"aftiger als Zahlen. 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.

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

\subsubsection{Auskunftsfunktionen}

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

\begin{fndoc}{hms\_pos}
\name     ``get current hamster position'' ---
          Bestimmen der aktuellen Hamsterposition
\synopsis {\tt void hms\_pos (HAMSTER *hms, int *x, int *y); }
\descript Es wird die Labyrinthposition des Hamsters {\tt hms}
          ermittelt und die Positionskoordinaten werden in den
          Variablen abgelegt, auf die {\tt x} und {\tt y} zeigen.
          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)$.
\result   Die Funktion hat kein Ergebnis.
\end{fndoc}

\begin{fndoc}{hms\_dir}
\name     ``get current hamster direction'' ---
          Bestimmen der aktuellen Hamsterblickrichtung
\synopsis {\tt int hms\_dir (HAMSTER *hms); }
\descript Es wird die Blickrichtung des Hamsters {\tt hms} ermittelt
          und die Himmelsrichtung zur"uckgegeben, und zwar kodiert
          als ganze Zahl. F"ur diese Zahlen sind in der Headerdatei
          {\tt hamster.h} symbolische Konstanten definiert, und zwar:
          \\[1ex]
          \begin{tabular}{@{}ll}
          \tt HMS\_EAST  & Der Hamster {\tt hms} schaut nach Osten.  \\
          \tt HMS\_NORTH & Der Hamster {\tt hms} schaut nach Norden. \\
          \tt HMS\_WEST  & Der Hamster {\tt hms} schaut nach Westen. \\
          \tt HMS\_SOUTH & Der Hamster {\tt hms} schaut nach S"uden.
          \end{tabular}
\result   Einer der Werte {\tt HMS\_EAST}, {\tt HMS\_NORTH},
          {\tt HMS\_WEST} oder {\tt HMS\_SOUTH}.
\end{fndoc}

\begin{fndoc}{hms\_load}
\name     ``get current hamster load'' ---
          Bestimmen der aktuellen Maiskornlast des Hamsters
\synopsis {\tt int hms\_load (HAMSTER *hms); }
\descript Es wird die Anzahl der Maisk"orner ermittelt, die der
          Hamster {\tt hms} gerade tr"agt. Diese Zahl liegt zwischen 0
          (einschlie\3lich) und der in der Headerdatei {\tt hamster.h}
          definierten Zahl {\tt HMS\_MAXLOAD} (einschlie\3lich).
\result   Die Zahl der getragenen Maisk"orner.
\end{fndoc}

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

\begin{fndoc}{hms\_look}
\name     ``get hamster's current outlook'' ---
          Bestimmen des aktuellen Ausblicks des Hamsters
\synopsis {\tt int hms\_look (HAMSTER *hms); }
\descript Es wird der Ausblick des Hamsters {\tt hms} bestimmt und
          kodiert als ganze Zahl zur"uckgegeben. F"ur diese Zahlen sind
          in der Headerdatei {\tt hamster.h} symbolische Konstanten
          definiert, und zwar: \\[1ex]
          \begin{tabular}{@{}ll}
          \tt HMS\_EMPTY & Vor dem Hamster liegt ein leeres Feld. \\
          \tt HMS\_CORN  & Vor dem Hamster liegt ein Feld,
                           auf dem sich Mais befindet. \\
          \tt HMS\_WALL  & Vor dem Hamster steht eine Wand.
          \end{tabular}\\[1ex]
          Bei R"uckgabe des Wertes {\tt HMS\_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 hms\_corn} ermittelt werden.
\result   Einer der Werte {\tt HMS\_EMPTY}, {\tt HMS\_CORN} oder
          {\tt HMS\_WALL}.
\end{fndoc}

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

\subsubsection{Handlungsfunktionen}

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

\begin{fndoc}{hms\_move}
\name     ``move hamster forward'' --- Vorw"artsbewegen des Hamsters
\synopsis {\tt int hms\_move (HAMSTER *hms); }
\descript Der Hamster {\tt hms} wird in seiner aktuellen Blickrichtung
          um ein Feld vorw"arts bewegt. Dies gelingt nat"urlich nur,
          wenn sich vor dem Hamster keine Wand befindet.
\result   Falls sich vor dem Hamster keine Wand befindet und er folglich
          vorw"arts bewegt werden kann, ist das Ergebnis~0. Anderenfalls
          wird ein Wert ungleich 0 zur"uckgegeben.
\end{fndoc}

\begin{fndoc}{hms\_turn}