 |
Seit nunmehr 25 Jahren
besticht der Bundeswettbewerb Informatik mit einem wohldurchdachten
Aufgabenblock. Die Probleme sollten nicht zu einfach, aber wiederum vom
talentierten Programmierern prinzipiell lösbar sein. In sich gibt es im
Schwierigkeitsgrad wiederum Abstufungen. Nicht alle Aufgaben sind
gleichwertig. |
 |
|
|
|
Aufgabe 1 |
Früsport (nicht vergeben)
Die BWINF-Schlange Digitail wacht nach einer durchrechneten Nacht mit
heißen Algorhythmen und zuviel Soft Ware ganz verknäult auf und möchte
wieder ihr altes geradliniges Selbst werden. „Wie gut, dass ich in einer
zwei- und nicht dreidimensio- nalen Welt lebe“, denkt sie, „denn sonst
könnte ich echt ein Problem haben“. Auch so braucht sie aber deine
Hilfe, sich zu entknäulen.
Digitail besteht aus geraden Ringeln der Länge 1, die Gitterpunkte mit
ganzzahligen Koordinaten ver- binden. Sie ist normalerweise goldfarben;
aber sie kann sich vorübergehend strecken und wird dann stellenweise
rot: Aus einem oder zwei aufeinander folgenden goldenen Ringeln können
doppelt so viele rote Ringel werden. Wenn sich die Schlange wieder
zusammenzieht, werden aus zwei oder vier aufeinander folgenden roten
Ringeln halb so viele goldene Ringel. Außerdem kann die Schlange ein
oder zwei aufeinander folgende Ringel beliebiger Farbe ver- schieben,
und zwei aufeinander folgende Ringel können ihre Farben tauschen. Diese
akrobatischen Übungen sind allerdings alle nur möglich, wenn die dafür
benötigten Gitterpunkte vorher frei waren und die Schlange
zusammenhängend bleibt. Aufgabe:
Schreibe ein Programm, das eine beliebig verknäulte anfangs goldene
Schlange einliest und eine Folge von Schritten der beschriebenen Art
berechnet, nach deren Ausführung alle Ringel der Schlange auf einer
Geraden liegen und (wieder) golden sind. Visualisiere die Ausführung der
Schritte so, dass man sehen kann, wie sich die Schlange entknäult.
FrühsportVerbenSkyline Geldtransporter |
|
|
|
Aufgabe 2 |
Geldtransporter
(Michael Krasselt) Zum Transport von Geld werden schwer
bewachte Geldtransporter eingesetzt. In einem solchen Geldtransporter
können Koffer mit Münzen transportiert werden. Die Koffer enthalten
Münzen in unterschiedlicher Menge und mit unterschiedlichem Gesamtwert.
Entsprechend unterscheiden sich die Koffer in Gewicht und Wert.
Da kommt so einiges an Gewicht zusammen. Es ist daher notwendig, den
Transporter gleichmäßig zu beladen, so dass er nicht zu einer Seite
umkippen kann.
Unser Transporter hat links und rechts je einen Kofferraum. Für jeden
Kofferraum lassen sich Gesamtwert und Gesamtgewicht der darin
enthaltenen Koffer bestimmen. Damit der Transporter keine Schlagseite
bekommt, müssen die Koffer so eingeräumt werden, dass die Differenz
zwischen den beiden Gesamtgewichten minimal ist. Aus
versicherungstechnischen Gründen dürfen die beiden Gesamtwerte sich
außerdem um höchstens 10.000 Euro unterscheiden.
Aufgabe:
Schreibe ein Programm zur Verteilung der Geldkoffer auf die beiden
Kofferräume. Überprüfe dein Programm mit den auf
www.bundeswettbewerb-informatik.de abgelegten Beispielen mit Angaben
zu Werten und Gewichten der einzelnen Koffer. |
|
|
|
Aufgabe 3 |
Turn 90
(Lukas Jeziak)
Der Robotertyp „Turn90“ ist in seiner Bewegungsfähigkeit
eingeschränkt: Er kann sich nur vorwärts bewegen und um 90 Grad drehen.
Außerdem hat er keinerlei visuelle Sensoren, kann also nicht „sehen“.
Seine Kontaktsensoren und auch seine Rechenfähigkeiten sind aber sehr
ordentlich.
Ein neuer Auftrag zur Programmierung von Turn90- Robotern scheint darauf
Rücksicht zu nehmen: Der Roboter soll befähigt werden, in einem Raum mit
Hindernissen immer den einzigen Ausgang zu finden. Die Programmierer
sind erleichtert, als sie hören, dass dem Raum ein Raster aus Quadraten
zugrunde liegt. Die Wände füllen die äußeren Quadrate des Rasters, die
Hindernisse füllen rechteckige Gruppen von Rasterquadraten aus. Der
Roboter befindet sich zu Beginn in einem bestimmten Quadrat. Der Aus-
gang ist eine mindestens ein Quadrat breite Lücke in einer Raumwand. Das
Bild unten zeigt einen Beispielraum mit Wänden und Hindernissen. Der
Roboter ist als Kreis eingezeichnet.
Aufgabe:
Schreibe ein Programm, mit dem ein Turn90-Roboter unter den genannten
Bedingungen immer den Ausgang findet. Du kannst davon ausgehen, dass die
Räume so gestaltet sind, dass es einen Weg vom Roboter zum Ausgang gibt.
Schicke uns für die drei Räume, die auf den BwInf-Webseiten angegeben
sind, und für zwei weitere Räume je ein grafisches Protokoll des
Roboterweges. Lasse entweder dein Programm den Weg zeichnen, oder stelle
ein schriftliches Protokoll des Weges (das du dann bitte mit- schickst)
selbst grafisch dar. |
|
|
|
Aufgabe 4 |
SVG-Fraktale
(Paul Gerber)
Ein Fraktal ist eine selbstähnliche Figur. Es entsteht, indem, aus-
gehend von einer Grundfigur, geometrische Objekte schrittweise
verfeinert werden. Ein bekanntes Fraktal ist zum Beispiel der
Sierpinski-Teppich (s. Bild).
Scalable Vector Graphics (SVG) ist eine Sprache, in der sich
geometrische Objekte mit leicht lesbaren Sprachelementen beschreiben
lassen, um sie z. B. in Webbrowsern anzuzeigen. Eine Definition findet
man unter www.w3.org/TR/SVG11/ .
Für eine Lösung dieser Aufgabe genügen aber der „SVG- Rahmen“:
<?xml version="1.0"?> <svg xmlns="http://www.w3.org/2000/svg"> elemente
</svg>
und die folgenden Elemente: <rect x=" zahl " y=" zahl " width=" zahl "
height=" zahl " fill=" farbe "/> <circle cx=" zahl " cy=" zahl " r="
zahl " fill=" zahl "/> <line x1=" zahl " y1=" zahl " x2=" zahl " y2="
zahl " stroke=" farbe " stroke-width=" zahl "/>
Die Grundfigur (erste Stufe) des Sierpinski-Teppichs, ein einfaches
weißes Quadrat, wird in einer SVG-Datei so beschrieben: <?xml version="1.0"?>
<svg xmlns="http://www.w3.org/2000/svg"> <rect x="0" y="0" width="180"
height="180" fill="white"/> </svg>
Ein Verfeinerungsschritt besteht generell daraus, ein Objekt durch ein
oder mehrere neue Objekte zu erset- zen. Beim Sierpinski-Teppich wird
jedes weiße Quadrat durch neun kleinere, gleich große Quadrate ersetzt,
von denen das mittlere schwarz und alle anderen weiß sind. Die zweite
Stufe des Sierpinski-Teppichs wird also in einer SVG-Datei so
beschrieben: <?xml version="1.0"?> <svg xmlns="http://www.w3.org/2000/svg">
<rect x="0" y="0" width="60" height="60" fill="white"/> <rect x="60"
y="0" width="60" height="60" fill="white"/> <rect x="120" y="0" width="60"
height="60" fill="white"/> <rect x="0" y="60" width="60" height="60"
fill="white"/> <rect x="60" y="60" width="60" height="60" fill="black"/>
<rect x="120" y="60" width="60" height="60" fill="white"/> <rect x="0"
y="120" width="60" height="60" fill="white"/> <rect x="60" y="120" width="60"
height="60" fill="white"/> <rect x="120" y="120" width="60" height="60"
fill="white"/> </svg>
Das Bild oben zeigt die fünfte Stufe des Sierpinski-Teppichs.
Aufgabe:
Wähle eine der auf www.bundeswettbewerb-informatik.de bereit
gestellten Grundfiguren oder denke dir selbst eine Grundfigur aus.
Schreibe ein Programm, das die Grundfigur oder eine bereits berechnete
Verfeinerungsstufe aus einer SVG-Datei einliest und eine neue SVG-Datei
erzeugt, die die nächste Stufe beschreibt. Die SVG-Dateien sollen von
gängigen Web-Browsern (z. B. Firefox) angezeigt werden können.
Als Programmiersprache zur Verarbeitung von XML-Dialekten wie SVG eignet
sich XSLT, aber auch andere Sprachen sind zugelassen. Es genügt, wenn
eine Ausführung des Programms nur einen Verfeinerungsschritt vornimmt. |
|
|
|
Aufgabe 5 |
Kaffeerunde (Anja Leheis)
Die Inhaberin der Firma Nash GmbH wünscht sich glückliche Mitarbeiter
und möchte ihnen fürderhin kostenlos Kaffee anbieten. Hierzu wird Kaffee
zur Verfügung gestellt sowie eine Kaffeemaschine mit einer Kanne. Die
Mitarbeiter müssen die Maschine selbst bedienen (nach einer
Einführungszeit von zehn Tagen, in denen ein Assistent der Inhaberin
immer für eine volle Kanne sorgt). Abends wird die Kanne stets entleert.
Die Kanne fasst zehn Tassen und es gibt 15 Mitarbeiter.
Jeder Mitarbeiter möchte gern drei Tassen täglich trinken, und zwar je
eine vormittags (8–10 Uhr), mittags (12–14 Uhr) und nachmittags (15–17
Uhr). In jedem dieser zweistündigen Intervalle erscheinen die
Kaffeetrinker in einer zufälligen Reihenfolge in der Kaffeeküche. Sie
verhalten sich dann so:
Falls sich noch Kaffee in der Kanne befindet, nehmen sie sich eine
Tasse daraus und gehen wieder. Ist die Kanne aber leer, dann hängt ihr
weiteres Verhalten davon ab, ob sie glücklich sind. Falls ja, kochen sie
eine neue volle Kanne und nehmen sich davon selbst eine Tasse. Sind sie
aber nicht glücklich, dann haben sie keine Lust, für andere Kaffee
mitzukochen, und gehen unverrichteter Dinge wieder weg.
Ob eine Person an einem bestimmten Tag glücklich ist, entscheidet sich
direkt morgens nach dem Aufstehen und hängt davon ab, wie oft sie in den
letzten zehn Tagen selbst Kaffee kochte und wie viele Tassen Kaffee sie
in diesem Zeitraum trank. Die genaue Definition lautet:
Falls eine Person in den letzten zehn Tagen n Tassen trank und m-mal
Kaffee kochte, dann ist sie genau dann glücklich, wenn n ≥ 10 und m /n <
a ist, wobei ein persönlicher Schwellenwert ist.
Aufgabe:
Schreibe ein Programm, das die Kaffeetrinker simuliert, wobei a der
Einfachheit halber für alle identisch sein möge. Wie viele Tassen trinkt
ein Mitarbeiter täglich im Durchschnitt auf lange Sicht, abhängig von
verschiedenen Schwellenwerten a? Ist das Ergebnis so, wie du es
erwartetest?
|
|
Lösungskonzept von Anja Leheis zum Starten
