Mannschaftswettbewerb der Spezialschulen Informatik 2005

Die Bauten des Herrn Tausendsasser

Der Architekt Herr Tausendsasser ist ein äußerst kreativer Mensch und gestaltet Wohngebäude möglichst bizarr. Für sein neustes Projekt plant er die Vielfalt schlechthin.

Es stehen ihm verschieden Arten von Steinsorten zur Verfügung, deren Hälften auf Grund der schlechten Lagerung verschiedene Färbungen aufweisen. Nur manchmal sind noch zwei Hälften von zwei verschiedenen Steinen gleich (s. Abb. 1). Mit diesen Steinen hantiert er nun solange, bis es seinem Wohlempfinden entspricht. Er dreht die Steine und wenn er Lust hat, teilt er sie auch manchmal. Schließlich entwirft er eine Grundplatte, bei der jede Färbung einmal waagerecht und einmal senkrecht auftaucht. Mit einem zufrieden stellenden Entwurf wendet er sich an seinen Baukonstrukteur Zehnig.

Herr Zehnig hat nun die Aufgabe die Platten zu einem Haus zusammenzustellen und schließlich in alt bewährter Plattenbauweise am Computer Häuser daraus entstehen zu lassen. Oftmals langweilt Herr Zehnig sich dabei fürchterlich und fängt an, an den Entwürfen von Herrn Tausendsasser herumzuspielen, so dass der es kaum merkt. Schließlich hatte Herr Zehnig die Spezialschule besucht und kannte sich ein wenig in der Mathematik und Computerei aus.

Insbesondere wenn die Anzahl der Steine in einer Reihe eine Quadratzahl ergibt, leistet er sich ein kleines Spielchen und vertauscht alle Steine. Es gibt ja bei einer Quadratzahl immer genauso viel Unterquadrate wie die Quadratzahl, mit genau so vielen Steinen wie die Quadratzahl. Also kann man nicht nur in jeder Zeile und Spalte verschiedene Steine haben, sondern auch in jedem Unterquadrat.

Manchmal klappt dies so nicht und da verlässt er sich auf den Glasermeister Zehnung. Herr Zehnung setzt nun noch verschiedene Fenster ein (s. Abb. 2). Da er auch mathematisch begabt ist, durchschaut er natürlich das Spielchen von Herrn Zehnig und hilft ihm ein wenig. So setzt er die Fenster genau dort ein, wo sich bei Herrn Zehnig die Fehler eingeschlichen haben. Allerdings darf eine Platte nicht mehr als ein Fünftel Fensterfläche haben. Wegen der Helligkeit sollte eine Platte aber mindestens auf vier Fünfundzwanzigstel der Fläche Licht durchlassen.

Schließlich muss noch die Bauzeichnung vom Programmierer Malzehn in den Computer eingegeben werden, damit die Statiker mit ihren Berechnungen loslegen können. Herr Malzehn ist nun seinerseits nicht nur ein geschickter Programmierer sondern auch ein hervorragender Denker. Und so denkt er, es müsste doch eine Möglichkeit geben, ein Programm zu schreiben, das Teile von Herrn Zehnig übernimmt und den Rest berechnet. Andererseits könnte es sogar einfacher sein, dass man einfach alle möglichen Bauplatten nach den Regeln von Herrn Zehnig berechnet, diese ausgibt und dann nach dem optischen Eindruck eine auswählt. Er entschließt sich dreißig Positionen der Farben zu übernehmen und diese einzugeben. Den Rest soll das Computerprogramm berechnen. Dabei sollen nun sich aber keine Fehler mehr einschleichen.

Nachdem er eine Weile voller Tatendrang die Aufgabe angehen wollte, verlässt ihn bald der Mut.

 

Da er gehört hatte, dass es einen Mannschaftswettbewerb Informatik in Magdeburg gibt, richtet er sich Hilfe suchend an die Schüler!

Aufgabe 1:
Analysieren Sie das Problem von Herrn Zehnmal algorithmisch!

Aufgabe 2:
Entwerfen Sie ein Programm zur Lösung des Problems nach den Vorstellungen von Herrn Zehnmal und implementieren Sie es!

Aufgabe 3:
Nehmen Sie zu den folgenden Fragen, die bei Herrn Zehnmal auftraten, Stellung!

  1. Ist die angesprochene Variante, sich alle Lösungen anzuschauen und „per Hand“ zu entscheiden, besser als die Übernahme von Vorgaben?
  2. Ist die Anzahl der Vorgaben, die er sich sinnvoll und gibt es Grenzen!
  3. Wie komplex wird schätzungsweise der Algorithmus mit den 30 Vorgaben?
  4. Wie könnte ein effizienter Algorithmus aussehen, der Vorgaben entwirft und dabei möglichst ähnlich komplexe Muster erzwingt?

Hinweis:
Stellen Sie die Ergebnisse der Aufgaben 1 und 3 in einer Powerpoint-Präsentation dar! Bereiten Sie einige Beispiele für eine kurze Programmvorführung vor! Sie haben max. 10 min Redezeit für die Präsentation und die Vorführung!

Viel Spaß!


© R. Feuerstein, 2005