Aufgabenblatt 5

Die Bewertungsgrundlage ist auch hier anders. Bitte beachten Sie dies.

Abgabetermin ist der 19.06.2018

Aufgabe 0

Die Manhattan-Distanz bezeichnet den Abstand zwischen zwei Feldern auf einem zweidimensionalem Gitter. Eine Bewegungsschritt zu einem Nachbarfeld ist nur möglich, wenn man mindestens zwei gemeinsame Kanten hat. Für quadratische Felder sind dies die Bewegungen “Norden”, “Osten”, “Süden”, “Westen” und wurde beispielhaft schon in Aufgabenblatt 0 besprochen.

Gegeben sei nun ein sechseckiges Feldersystem:

  \ N  /
NW +--+ NO
  /    \
-+      +-
  \    /
SW +--+ SO
  / S  \

Auf einem Gitter von Sechsecken kann von jedem Feld in die Richtungen “Norden”, “Nordosten”, “Südosten”, “Süden”, “Südwesten und “Nordwesten” in einem Schritt gegangen werden.

Gegeben sei nun eine Wegbeschreibung (die Puzzleeingabe, siehe Beispiele). Wie lautet die Manhattandistanz zum Ursprungsfeld?

Beispiele

• N,N,N hat eine Distanz von 3.
• SW,SW,SW,NO hat eine Distanz von 2.
• SW,SO hat eine Distanz von 1.
• N,S hat eine Distanz von 0.
• SO,NO,NO,N,N,N,N,N,N,NW,NW,NW,SO,NW,NW,SW,SO,NW,SW,NW,SO,SW,S,SW,S,S,SW,S,SW,SW,NO,SW,S,SW,S,SW,NW,S,S,S,S,S,S,SW,S,S,N,NW,S,S,SO,SO,SO,S,NW,SO,S,SO,NW,SO,SO,N,SO,SO,SO,SO,SO hat eine Distanz von 18

Aufgabe 1

Unter Betrachtung der selben Wegbeschreibung, wie hoch ist der höchste Manhattan-Abstand, der auf dem Weg zwischendurch (oder auch am Ende) erreicht wird?

Beispiel

• N,N,S wäre dies 2, nachdem zweimal nach Norden gegangen wurde.

Ein- und Ausgabeform

Das Lösungsprogramm soll, wie immer, von der Standardeingabe lesen. In der ersten Zeile der Ausgabe soll die Lösung für Aufgabe 0 stehen, in der zweiten Zeile die für Aufgabe 1.

Bewertungsgrundlage

Diese Aufgabe stellt andere Anforderungen als die Vorangegangenen. Hier geht es darum, ein geeignetes mathematisches Modell zu finden und möglichst passende Werkzeuge der Informatik anzuwenden.

Die Bewertung der Abgabe besteht aus den unten folgenden Punkten, die ihr Lösungsprojekt enthalten muss. Nehmen Sie als Vorlage die Musterlösung zu Aufgabe 0 zur Hand.

• Eine schriftliche Ausarbeitung als PDF-Dokument in Ihrem GitLab-Projekt:
  • Analyse des Problems.
  • Beschreiben Sie Ihren Lösungsansatz
• Lösung der Problems in einem Projektordner in Ihrem GitLab-Projekt
  • Das ausschließlich von Ihnen allein geschriebene Programm soll die gestellte Aufgabe auf einem gewöhnlichen Laborrechner der Hochschule in unter einer Minute Laufzeit lösen.
  • Das Lösungsprojekt darf nur als Quellcode abgegeben werden.
  • Eine ausführliche Bau- und Ausführanleitung ist zwingender Bestandteil der Abgabe. Legen Sie gegebenenfalls Makefiles oder andere Bauskripte bei. Das Bauen und Ausführen des Lösungsprojekts muss in wenigen Schritten möglich sein und auf einem Laborrechner der Hochschule vorgeführt werden können.
  • Ihr Programm muss die Puzzleeingabe von der Standardeingabe einlesen.
  • Ihr Programm darf nur Ihre Lösung auf der Standardausgabe ausgeben. Die Lösung muss in der Form den mitgelieferten Beispielen entsprechen. Zusätzliche Ausgabe zu Debuggingzwecken sind aus der Abgabe vorher zu entfernen. Falls Ihr Programm hilfreiche Detailinformationen zur Lösungsfindung ausgeben kann, dokumentieren Sie, wie sie gesondert aktiviert werden kann.

Seien Sie außerdem darauf vorbereitet, Ihr Projekt während des Praktikumstermins vorzustellen und dazu Fragen zu beantworten.

Abgabemodalitäten

Zur Abnahme ist die persönliche Anwesenheit erforderlich. Ihr Lösungsprojekt muss zum Abgabetermin im vorher von Ihnen eingerichtetem persönlichen, privaten GitLab-Projekt abrufbar sein.