 |
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. |
 |
hier
bekommt man das zentrale Aufgabenblatt für die 1. Runden des Jahres 2007
|
|
|
Aufgabe 1 |
Prämienjagd (Eric Kreller, Richard Friedrich)
Supermärkte geben oft Prämien. Eine oft gesehene Möglichkeit ist
„drei kaufen – eins umsonst”, was aber auch als „weniger als vier kaufen
– mehr zahlen” interpretiert werden kann. Im vorliegenden Fall sind die
Regeln aber viel komplizierter:
Liebe Kundschaft,
wenn Sie an der Kasse zwei Gegenstände, die Sie kaufen wollen,
nebeneinander hinlegen und der Centbetrag der Summe beider Preise 11,
33, 55, 77 oder 99 betragen sollte, dann erhalten Sie eine Prämie in
Form eines kleinen Geschenks. Sie können Ihr Geschenk aus einem
reichhaltigen Angebot auswählen. Selbstverständlich können Sie bei einem
Einkauf mehrere Prämien einfordern. Jeder Gegenstand kann aber nur zur
Erlangung einer Prämie verwendet werden. Wir freuen uns, wenn Sie die
Herausforderung annehmen, Ihren Einkauf entsprechend auf dem Band
anzuordnen.
Will man tatsächlich die Anzahl der Prämien maximieren, wenn man mit
gefülltem Einkaufswagen an die Kasse kommt, dann lohnt es sich, ein
wenig nachzudenken: Hat man Gegenstände mit den Preisen c 4,13, c 6,64,
c 8,98 und c 9,91, ist es keine gute Idee, die ersten beiden zu paaren,
da dann nur eine Prämie winkt. Aufgabe:
Schreibe ein Programm, das hilft, dieses verflixte Problem zu lösen. Es
sollte die Preise einlesen und dann die entsprechenden Paarungen
ausgeben.
Für die Eingabe 1.99 4.13 6.64 8.98 9.91 1.99 wäre beispielsweise die
Ausgabe ( 4.13 8.98 ) ( 6.64 9.91 ) angemessen. Das genaue Format der
Ausgabe kannst du auch selbst wählen. Du solltest aber unbedingt darauf
achten, dass deine Lösung immer so viele Prämien wie möglich erwirkt.
Demonstriere dein Programm an aussagekräftigen, selbst gewählten Fällen
und teste es auch an den auf der Webseite des BWINF vorgegebenen
Beispieldaten.
http://www.bwinf.de/aufgaben/material/ |
|
|
|
Aufgabe 2 |
Perlenketten (Bennet Berger) Eine Schulklasse möchte eine
Spende von Geld machen, das sie mit dem Verkauf von Perlenketten
verdient. Eine Perlenkette ist eine geschlossene Folge von farbigen
Holzperlen. Es gibt nur Perlen von sechs verschiedenen Farben; aber
dafür reichen die längsten Ketten den Leuten vom Hals viermal hinunter
bis zum Bauchnabel. Der Verkauf läuft gut.
Eine etwas spleenige Stammkundin ist aber unglücklich.
Sie hat die beiden Ketten gekauft und erst hinterher festgestellt, dass
sie in Wirklichkeit „gleich” sind, d. h. dieselbe Folge von Farben
aufweisen, wenn man nur richtig anfängt und die richtige
Durchlaufrichtung wählt – sie wollte aber immer nur verschiedene Ketten
kaufen.
Nun gut, sie kann eine ihrer Ketten umtauschen.
Aber um zu verhindern, dass so etwas noch einmal passiert, soll jede
Kette von nun an mit einem Schaubild verkauft werden, das die Kette in
einer „Normalform” zeigt, und zwar so, dass zwei Ketten genau dann
dieselbe Normalform haben, wenn sie dieselbe Farbenfolge besitzen. Zum
Beispiel könnten die obigen Ketten beide durch die folgende Normalform
dargestellt werden:
Aufgabe:
Überlege dir und beschreibe, wie die Normalformen beschaffen sein
könnten, und schreibe ein Programm, das die Normalform einer beliebigen
Perlenkette berechnen kann. Zeige die Ausgabe deines Programms für
sinnvoll gewählte Beispielketten. |
|
|
|
Aufgabe 3 |
Winddiagramme (Erik Voigt)
Wetterstationen erfassen unter anderem Windrichtungen und
Windgeschwindigkeiten. Die Windrichtungen werden in Grad angegeben: 0°
steht für Wind aus Nord, 90° für Ostwind, 180° für Südwind, 270° für
Westwind. Die Windgeschwindigkeiten werden in Meter pro Sekunde
angegeben. Die Wetterdaten liegen in Tabellenform vor.
Zur Darstellung der Winddaten sollen Windrichtungsdiagramme erstellt
werden, die einerseits die Häufigkeiten bestimmter Windrichtungen
verdeutlichen und andererseits die bei den jeweiligen Windrichtungen
aufgetretenen Windgeschwindigkeiten veranschaulichen.
Aufgabe:
Formuliere zwei Fragestellungen, die mit Hilfe der Winddaten aus der
Tabelle beantwortet werden können, die auf den Webseiten des BWINF
vorliegt. Finde jeweils grafische Darstellungen, welche die Beantwortung
der Fragen gut unterstützen. In mindestens einer der Grafiken sollen die
Windrichtungen als von einem gemeinsamen Punkt ausgehende Strahlen
dargestellt werden, wie in einer Wind- oder Kompassrose.
- Stunde
- Windrichtung
- Windgeschwindigkeit
- Außentemperatur
- Luftfeuchtigkeit
- Luftdruck
- ...
- Datum
|
|
|
|
Aufgabe 4 |
Pass-Algorithmen (Marcel
Pfeifer, André Neubert)
Zugriffe zu technischen Geräten werden oft erst nach einer
Authentifizierung gewährt. Beispiele sind der Passwortschutz eines
Schulcomputers oder die PIN-Eingabe in Verbindung mit einer Magnetkarte
am Geldautomaten.
Ein Sicherheitsnachteil dieser Zugriffsschutzverfahren ist ihre
Wiederholbarkeit: Wird das Eingeben des Passworts oder der PIN
beobachtet (und die Magnetkarte entwendet), kann auch eine unbefugte
Person Zugang erhalten.
Entwirf ein System, das diesen Nachteil vermeidet.
Anstatt eines statischen Passworts aus einer großen Menge möglicher
Passwörter soll ein Pass-Algorithmus aus einer großen Menge möglicher
Pass-Algorithmen als Nachweis der Identität vergeben werden. Dieser
Pass-Algorithmus kann eine Eingabe eindeutig in eine Ausgabe überführen,
berechnet also eine Funktion f: X Y. Eine Authentifizierung läuft nun so
ab: Das System bietet ein zufälliges x X an, und der Benutzer oder die
Benutzerin muss selbst f(x) berechnen und dem System mitteilen. Ist das
Ergebnis korrekt, dann geht das System davon aus, dass er oder sie im
Besitz des korrekten Algorithmus f ist, und gewährt den Zugang.
Beobachtet jemand den Vorgang, werden im schlimmsten Fall x und f(x)
bekannt, aber nicht f. Eine gute Klasse von Pass-Algorithmen sollte
mindestens folgende Eigenschaften haben:
- die Anzahl möglicher Pass-Algorithmen ist groß
- ein Pass-Algorithmus kann mit wenig Mühe im Kopf in kurzer Zeit
ausgeführt werden
- die Beobachtung weniger Paare (x,f(x)) erlaubt kaum Rückschlüsse
auf den benutzten Pass-Algorithmus f
- welche dieser Punkte am wichtigsten sind, hängt sehr vom Kontext
ab
Hier ein (sicher nicht perfektes) Beispielsystem: Die Eingabe ist ein
5 x 5 Feld von zweistelligen Zahlen.
Ein Pass-Algorithmus sieht so aus: „Addiere die Zahlen an den Positionen
(a,b) und (c,d) zu einer Zahl n”.
Hierbei gilt 1 <_ a,b,c,d <_ 5, und 1 <_ n <_ 99.
Konkret könnte ein Pass-Algorithmus also „Addiere die Zahlen an den
Positionen (3,4) und (1,5) zur Zahl 42” lauten.
Das konkrete System könnte
23 34 23 89 45
10 23 64 74 87
38 93 52 97 47
32 98 23 29 31
87 38 97 12 32
präsentieren, wobei mit 97 + 45 + 42 = 184 geantwortet werden muss.
Aufgabe:
- Überlege, warum die genannten Eigenschaften wünschenswert sind.
Welche weiteren Eigenschaften sollte ein solches System haben?
- Wie bewertest du das Beispielsystem?
- Entwirf selbst zwei solche Systeme für zwei unterschiedliche
Szenarien, implementiere eines davon und beurteile kritisch die
Vorteile und Nachteile beider. Erläutere auch, in welchen Situationen
deine Systeme gut eingesetzt werden können.
|
|
|
|
Aufgabe 5 |
Kosmischer Tanz (Johannes
Uhlig, Friedrich Salzer)
Ein Stern S mit Masse M kann als punktförmig und unbeweglich
angesehen werden. Ein kleinerer punktförmiger Himmelskörper K mit Masse
m in Abstand r von S wird von S mit einer Kraft der Größe G M m/ r 2
angezogen, wobei G eine Gravitationskonstante ist. Außerdem gilt das
zweite Newtonsche Gesetz
Beschleunigung = Kraft /Masse.
Aufgabe:
Erstelle ein Simulationssystem, das geeignet ist, experimentell zu
untersuchen, wie sich K unter dem Einfluss der Anziehung durch S bewegen
kann (andere Himmelskörper werden außer Acht gelassen).
Es soll dabei möglich sein, die Masse des Körpers K sowie seine
Anfangsposition und Anfangsgeschwindigkeit zu variieren. Finde eine gute
Art, wie man das Ergebnis einer Simulation auf einem Blatt Papier
darstellen kann, und zeige das Ergebnis von mindestens zwei möglichst
unterschiedlichen und interessant verlaufenden Simulationen.
|
|
|
|
Zugegeben: man hatte die
Pistole etwas sehr unmittelbar auf der Brust, dafür hat man sich mal
überwunden und am Informatikwettbewerb teilgenommen. Da wir als
Gruppenprojekt eingereicht haben, kommt keiner im Wettbewerb weiter, aber
eine Urkunde für die dargestellten Lösungen sowie eine entsprechende
Punktewertung für den Kurs stehen in jedem Fall in Aussicht. |
|
|
|
|
zu den
Lösungen im ZIP-Format |
|
 Aufgabe 1 |
Programmablauf: Man gibt
die Preise im dafür vorgesehenen Feld ein und trennt sie durch ein Komma
und ein Leerzeichen. Die Menge der Preise ist auf rund 20.000 begrenzt.
Die Preise sollten alle das Format x,xx haben, das heißt maximal zwei
Nachkommastellen haben. (Punkt als Trennzeichen ist auch legitim)
Mit dem "Preispaare maximieren"-Button wird der Algorithmus gestartet
und die Preispaare in die Tabelle geschrieben. Alternativ können die
Preise auch einzeln eingegeben werden und mit dem "Hinzufügen"-Button in
eine Liste geschrieben werden. Wenn man dann auf den Button "Preispaare
optimieren" klickt werden auch Preispaare gebildet. In der
Ergebnistabelle kann man sich die Preispaare anschauen und einsehen wie
viele der eingegebenen Preise für die Paarbildung verwendet wurden.
Richard Friedrich & Eric Kreller |
| |
|
| |
|
| |
|
|
Aufgabe 5 |
Programmablauf: Nach
Starten des Programms erhält man eine weiße Zeichenfläche und ein paar
Schaltflächen. Zu Beginn muss man die Position des Sterns auf der
Zeichenfläche auswählen. Hat man sich eine Position für den Stern
ausgewählt (durch darüber bewegen des Mauszeigers) klickt man einfach
auf die Zeichenfläche und es erscheint ein Kreuz mit der Beschriftung
„S“ für Stern. Danach hat man die gleiche Prozedere für den Planeten.
Man muss nur beachten, dass die Stellung von Stern und Planet zueinander
nicht mehr ändern kann, nur durch einen Neustart des Programms, z.B.
über den Button „Zurücksetzen (=Neustart)“ oben rechts. Hat man die
Position des Planeten festgelegt erscheint ein Eingabefeld im unteren
Teil der Anwendung. Dort muss man den realen Abstand von Planet und
Stern in Kilometern angeben (maximal 1e17). Hat man dies getan und mit
Enter (oder einem Klick auf „weiter“) bestätigt wird in der Simulation
ein Strich angezeigt. Dieser hat genau den x-Unterschied zwischen Stern
und Planet als Länge und die reale Länge steht darunter. Dieser soll als
Maßstab dienen. Weiterhin erscheint ein weiteres Eingabefeld, in welches
man die Masse des Sterns in Tonnen eingeben muss. Ist dies erfolgt und
mit Enter bestätigt erscheint das Eingabefeld für die Masse des Planeten
in Tonnen. Ist dieses eingegeben und mit Enter bestätigt erschient als
letztes Eingabefeld das Feld für die Anfangsgeschwindigkeit. Hat man
diese eingegeben und mit Enter bestätigt sieht man die erste Simulation
in der Zeichnung. Zusätzlich werden bei den Eingabefeldern die
kosmischen Geschwindigkeiten angegeben. Gibt man die erste (kleinere)
als Anfangsgeschwindigkeit ein erhält man eine Kreisbahn. Gibt man eine
Anfangsgeschwindigkeit ein, die mindestens so groß ist, wie die zweite
(größere) kosmische Geschwindigkeit erhält man eine Parabelbahn.
Nachdem alle Eingaben getätigt wurden, erscheinen am rechten Rand 4
Schaltflächen, mit denen man die Simulation auf der Zeichenfläche
verschieben kann. Diese Verschiebung ist gleichzeitig die Vorbereitung
zum Ausdrucken über die integrierte Druckroutine. Beachten Sie dabei,
dass alle eingegebenen Werte auf der gedruckten Seite oben links
aufgeführt werden.
Beispielergebnisse finden Sie angehängt. Diese wurden mit der
integrierten Druckroutine ausgedruckt und simulieren (A) die Kreisbahn
eines Satelliten um die Erde in einer Höhe von 230 km über der Erd
Friedrich Salzer &
Johannes Uhlig |
|
