 |
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 2006
|
|
|
Aufgabe 1 |
Närrische Wirtschaft
Ein Karnevalsverein nimmt monatlich € 1000 an Mitgliedsbeiträgen ein.
Davon will der Verein verschiedene Anschaffungen tätigen. Leider ist der
Schatzmeister an unangenehme närrische Regeln gebunden: Er kann
monatlich bis zu € 1000 ausgeben.
Gibt er weniger aus, wird für den Rest Eis gekauft; sein Budget für den
nächsten Monat ist dann leider wieder nur € 1000, da ja der Rest für
Eisessen verschwendet wurde. Er möchte nun zunächst Gegenstände mit
folgenden Preisen kaufen:
- € 340,
- € 670,
- € 790,
- € 1320,
- € 2100 und
- € 5200.
Es sieht so aus, als hätte er keine Chance, die letzten drei
Gegenstände zu besorgen. Zum Glück kann er sich mit einem erlaubten
Trick behelfen:
Er hat gute Beziehungen zum Geschäft, in welchem er alle Einkäufe zu
tätigen gedenkt. Der Verkäufer ist stets bereit, bereits verkaufte
Gegenstände zurückzunehmen und dafür andere Gegenstände entsprechend
billiger zu verkaufen. Hat der Schatzmeister beispielsweise schon
Gegenstände im Werte von € 800 und € 1100, so kann er diese zurückgeben,
€ 900 zuzahlen und auf diese Weise einen Gegenstand für € 2800 erwerben,
ohne das monatliche Budget zu überschreiten.
Tatsächlich kann er durch geschicktes Handeln alle sechs gewünschten
Gegenstände in 13 Monaten beschaffen.
Aufgabe:
Schreibe ein Programm, das Menschen in ähnlicher Situation helfen kann.
Es soll zunächst das monatliche Budget und die Preise aller Gegenstände
ein lesen. Dann muss es berechnen, welche der Ge gen stände besorgt
werden können, und einen Plan ausgeben, welche Gegenstände in jedem
Monat gekauft beziehungsweise zurückgegeben werden sollen. Dabei muss
eine kleinstmögliche Anzahl von Monaten verwendet werden.
Lasse Dein Programm mit den Daten des Karnevalsvereins laufen.
Dokumentiere auch seine Ergebnisse für die Beispiele, die unter:
http://www.bwinf.de/aufgaben/material/
zu finden sind. |
|
|
|
Aufgabe 2 |
Robot Dressing
Elba, eine humanoide Roboterin, soll nicht nur sicher auf zwei
Beinen, sondern auch gut gekleidet umhergehen. Ihre Erfinderinnen können
sie deswegen mit Kleidungsstücken versorgen sowie mit einigen Angaben
über die Reihenfolge, in der diese angezogen werden sollten.
Beispiel
Kleidungsstücke: Bluse, Handschuhe, Hose, Jacke, Mütze, Pullover,
Schal, Schuhe, Strümpfe
Angaben zur Reihenfolge:
- die Strümpfe vor den Schuhen
- die Strümpfe vor der Hose
- die Hose vor den Schuhen
- die Hose vor dem Pullover
- die Bluse vor der Hose
- die Bluse vor dem Pullover
- der Pullover vor der Jacke
- die Hose vor der Jacke
- der Schal vor der Jacke
- die Jacke vor den Handschuhen
- der Pullover vor dem Schal
- keine Angabe für die Mütze
Damit alles klappt, muss Elba also zuerst Strümpfe und Bluse
anziehen. Dann ist die Hose dran. Die Mütze könnte zum Schluss kommen,
aber auch zu jedem anderen Zeitpunkt. Leider kommt Elba damit nicht
zurecht und kratzt sich zwischen den Antennen. Ihr fehlt der richtige
Algorithmus!
Aufgabe:
Entwickle und schreibe ein Programm, das Elba hilft. Es soll
Folgendes leisten:
- Die Menge der Kleidungsstücke und die Angaben zur Reihenfolge
einlesen. Überlege dir dazu für die Eingabedaten ein einfach einzulesendes
Beschreibungsformat.
- Eine Gesamtreihenfolge bestimmen, in der Elba ihre Sachen anziehen
kann, ohne dass irgendeine der Angaben zur Reihenfolge verletzt wird.
Dazu ist es wichtig, die Angaben geschickt zu modellieren.
- Alle solche Ankleidereihenfolgen bestimmen.
- Dokumentiere die Ergebnisse deines Programms für die Beispieldaten
sowie für zwei weitere Mengen von Kleidungsstücken und den dazu
gehörigen Angaben zur Reihenfolge.
|
|
|
|
Aufgabe 3 |
HTML-Mobiles
Sandy würde es so beschreiben: „Man nehme die Definition einer
Webpage und lasse ihre Attributgewichte und Syntaxstrukturen im Wind des
Zufalls sanft wehen.“ Etwas nüchterner liest sich das als ...
Aufgabe:
- Schreibe ein Programm, das elementare Änderungen in einem reinen
HTML-Dokument vornehmen kann.
- Elementare Änderungen können inhaltlich sein, z.B. Ändern eines
Farbwerts, Verschieben einer xy-Position, usw.
- Elementare Änderungen können auch strukturell sein, z.B. Ändern
der Reihenfolge von Teilen der Seite, Vertauschen von
Tabellenelementen usw.
- Beschränke dein Programm auf drei Arten von inhaltlichen und drei
Arten von strukturellen Änderungen.
- Dein Mobile-Programm soll nun interessante Bildfolgen erzeugen,
indem es die elementaren Änderungen in zufälliger Reihenfolge und mit
zu fällig gewählten Parametern anwendet.
- Um das Programm zu testen, schreibe sechs optisch interessante
HTML-Dokumente für den nur 225 x100 Pixel großen Bildschirm des Handy
von Sandy.
- Sieh dir an, wie dein Mobile sich bewegt.
- Dokumentiere für jede Änderungsart ihren Effekt durch je ein
Bildpaar „vorher“ – „nachher“.
|
|
|
|
Aufgabe 4 |
Supermarkt
Der Supermarkt Kundenfreund verkauft Lebensmittel. Beim Einkauf
werden alle ausgezeichneten Waren von dem Scanner der Kasse erfasst. Bei
nicht abgepackter Ware wie Obst und Gemüse muss
der Kassierer eine Produktnummer eingeben und die Ware wird gewogen.
Folgende Geschäfts fälle sollen bewältigt werden:
- Erstellen eines Kassenbons.
- Ausdruck einer Liste aller Artikel, deren Bestand einen Wert
unterschreitet.
- Ausdruck einer Hitliste verkaufter Artikel innerhalb eines Monats,
geordnet nach Produktgruppen.
- Ausdruck von Adressetiketten für den Versand eines Werbebriefes an
Kunden, die mit Kundenkarte bezahlt und viel Wein gekauft haben.
Aufgabe:
- Beschreibe, wie du die Daten strukturieren kannst. Begründe deine
Entscheidungen.
- Gib auf der Basis deiner Lösung an, wie die geforderten Ausdrucke
erstellt werden können.
- Bewerte den Geschäftsfall Nr. 4.
|
|
|
|
Aufgabe 5 |
Die Paderbox
Die PB hat innen drei Zustände und außen drei Lampen. Jeder Zustand
ist mit zwei Lampen verbunden, jede Lampe ist mit zwei Zuständen verbunden.
Die PB hat auch zwei Eingabetasten '0' und '1'. Drückt man eine Taste,
geht die PB in einen neuen Zustand über, abhängig vom alten Zustand und
der gedrückten Taste. Der neue Zustand kann der gleiche sein wie der
alte.
Geht die PB in einen neuen Zustand über, werden die damit verbundenen
zwei Lampen umgeschaltet (wenn AN, dann AUS; wenn AUS, dann AN).
Die Programmierung der Tasten – also der Zustandsübergänge, die von
ihnen bewirkt werden – ist geheim.
Aufgabe:
- Programmiere ein PB-Spiel mit den Funktionen:
- Erzeugen einer PB mit einer zufälligen Programmierung der Tasten,
einer zufälligen Verbindung von Zuständen mit Lampen, einer zufälligen
AN/AUS-Schaltung der Lampen und einem zufälligen
Anfangszustand.
- Eingabetaste '0' drücken, Übergang in den entsprechend neuen
Zustand.
- Eingabetaste '1' drücken, Übergang in den entsprechend neuen
Zustand.
- Rücksetzen der PB in den Anfangszustand.
- Verraten der geheimen Programmierung.
- Stelle die drei Lampen der PB auf dem Bildschirm dar.
Was soll das? Der Zweck des PB-Spiels ist es, die geheime
Programmierung zu erforschen. Viel Spaß beim Knobeln! |
|
|
|
Junior-Aufgabe |
HTML-Mobiles
In der mexikanischen Provinz Yucatan erinnern viele historische
Stätten an das Volk der Maya.
Die Kultur der Maya spielt auch heute noch eine wichtige Rolle in
Yucatan, und viele Einwohner sprechen noch die Sprache der Maya – manche
sogar ausschließlich!
Auch das System, das die Maya zur Zahlendarstellung benutzten, ist noch
bekannt. Sie verwen deten die Basis 20 und benutzten zur Dar stellung
der Ziffern für die Werte 0 bis 19 drei verschiedene
grafische Symbole: Eine Muschel für die Null, einen Punkt für die Eins
und einen waagerechten Strich für die Fünf. Für die anderen Werte
stapelten sie die nötigen Striche übereinander und legten auf diesen
Stapel die benötigten Punkte nebeneinander.
Beispiel
ist die Maya-Ziffer, die mit unserer Zahl 12 gleichwertig ist.
So wie wir Zahlen größer als 9 mit mehreren Ziffern hintereinander
schreiben, notierten die Maya Zahlen größer als 19 mit mehreren Ziffern
übereinander.
Für die 20 schreibt man einen Punkt über der Muschel (1 mal 20 und 0 mal
1).
990 schreibt sich dann als 2 mal 400 und 9 mal 20
und 10 mal 1.
Aufgabe:
- Hilf den Menschen in Yucatan, die Kultur der Maya am Leben zu
erhalten. Schreibe ein Programm, das Dezimalzahlen in Maya-Zahlen
umrechnet.
- Verwende dabei eine eigene grafische Darstellung der Maya-Symbole
und setze daraus grafische Darstellungen der Maya-Zahlen zusammen.
Sende uns grafische Darstellungen für mindestens drei Zahlen.
- Mehr über Maya-Zahlen erfährst du im Inter net, z.B. unter:
-
http://www.mathezentrale.de/maya/maya1.htm
|
|
