- left
- right
- up
- down
Hier könnt ihr Fragen zur Aufgabe 5 (Rominos) der 1. Runde stellen.
Ich versuche diese Aufgabe gerade mit Brute Force zu lösen.
Bei den 10-er Rominos sind es aber so viele Kombinationen, dass mein Computer etwa 100.000 Stunden brauchen würde, um alle zu bestimmen. Ich schätze mal, es gibt einen effizienteren Weg die Aufgabe zu lösen?
Andere Frage: Dieser hier wäre auch ein valider, oder?
Bei den Aufgaben der ersten Runde kann man normalerweise davon ausgehen, dass sich alle vorgegebenen Beispiele (also hier n von 4 bis 10) innerhalb von jeweils höchstens einer bis zwei Minuten lösen lassen. Mit dieser Aufgabe kenne ich mich jetzt natürlich nicht aus, aber ich vermute, Brute Force ist tatsächlich nicht gerade der effizienteste Weg.
Danke, das hatte ich schon gedacht ;)
Ich hab jetzt schon ein anderes Programm an dessen Stelle gelöst, also habe ich meine drei zusammen. Danke trotzdem!
Ich hab eine Frage bezüglich der Definition eines n-Rominos. Nach Aufgabenstellung gilt eine Figur als n-Romino, sollte sie folgendes Konstrukt enthalten:
ox
xo
(Dabei stellt ein x ein Quadrat und ein o ein leeres Feld da.)
Nach dieser Definition wäre folgende Figur ein 7-Romino:
xxx
xox
xxo
Diese Figur wäre allerding auch ein Heptomino (freie Anpassung des Begriffs Pentomino für 7). Die Frage, die sich mir nun stellt, ist, wie mein Programm eine solche Figur behandeln soll.
Stefan M said:
Ich hab eine Frage bezüglich der Definition eines n-Rominos. Nach Aufgabenstellung gilt eine Figur als n-Romino, sollte sie folgendes Konstrukt enthalten:
ox
xo
(Dabei stellt ein x ein Quadrat und ein o ein leeres Feld da.)
Nach dieser Definition wäre folgende Figur ein 7-Romino:
xxx
xox
xxo
Diese Figur wäre allerding auch ein Heptomino (freie Anpassung des Begriffs Pentomino für 7). Die Frage, die sich mir nun stellt, ist, wie mein Programm eine solche Figur behandeln soll.
Zwei Gedanken:
1. Ich sehe darin, dass die Figur ein "Heptomino" sein könnte, kein Problem damit, dass sie auch ein 7-Romino ist. Die Aufgabenstellung verbietet ja nicht, dass n-Rominos auch n-Ominos sein dürfen.
2. In der Aufgabenstellung werden n-Ominos höheren Grades nicht definiert. Aber es wäre kein Widerspruch zu den gezeigten Pentominos, wenn das oben gezeigte Konstrukt explizit verboten wäre.
Hilft das weiter?
In dem Zusammenhang lässt sich auch noch ein ganz allgemeiner Grundsatz bei der Lösung von BwInf-Aufgaben benennen: der BwInf-Dreisprung. Was ist das? Nun, bei Unsicherheiten über Details in der Aufgabenstellung sollte man
Damit ist man immer auf der sicheren Seite.
Viel Erfolg – auch beim Dreispringen! 
Darf die grafische Ausgabe durch die Bibliothek Matplotlib in Python ausgegeben werden, sodass für jede Figur ein Fenster geöffnet wird?
Z.b. bei 3-Rominos also 3 neue Fenster mit je einer Figur.
Ich frage, da es als störend erfunden werden könnte, wenn es viele n-Rominos gibt und dementsprechend ausgegeben werden müssen.
Grundsätzlich ist die Nutzung von Bibliotheken erlaubt.
Ideal sind die vielen Fenster zwar nicht. Aber wichtiger als die Bildschirmausgabe ist, dass du diese Ausgabe dokumentierst, also die Bilder der 4-Rominos und 5-Rominos in die Dokumentation einbindest. Vielleicht erlaubt es die Bibliothek ja auch, die Bilder in Dateien auszugeben.
Zählt es auch als grafische Ausgabe, wenn man zur Darstellung der Blöcke gewisse ASCII-Zeichen benutzt?
Aus technischer Sicht ist es Text, aber gleichzeitig wird dieser genutzt, um eine Grafik darzustellen
Konrad N. said:
Zählt es auch als grafische Ausgabe, wenn man zur Darstellung der Blöcke gewisse ASCII-Zeichen benutzt?
Aus technischer Sicht ist es Text, aber gleichzeitig wird dieser genutzt, um eine Grafik darzustellen
Eine „graphische Ausgabe“ in der Konsole ist erlaubt, allerdings würde ich von der im Link gezeigten Darstellung abraten, da dabei die beiden Figuren
▇
▇ ▇
▇
und
▇
▇▇▇
▇
nicht voneinander unterschieden werden können.
Die grafischen Darstellungen der Rominos für n=4 und n=5 sollen ja laut Aufgabe in der Dokumentation enthalten sein. Allerdings gibt es insbesonders für n=5 relativ viele Rominos, ist es da der Übersichtlichkeit zuliebe auch möglich die Darstellungen der Rominos in eine separate Datei auszulagern und in der Dokumentation lediglich auf die Datei zu verweisen?
Konrad N. said:
Die grafischen Darstellungen der Rominos für n=4 und n=5 sollen ja laut Aufgabe in der Dokumentation enthalten sein. Allerdings gibt es insbesonders für n=5 relativ viele Rominos, ist es da der Übersichtlichkeit zuliebe auch möglich die Darstellungen der Rominos in eine separate Datei auszulagern und in der Dokumentation lediglich auf die Datei zu verweisen?
Da explizit gefordert ist, die grafische Ausgabe zu dokumentieren, wäre es keine gute Idee, in der Dokumentation die Abbildungen der 4-Rominos und 5-Rominos komplett wegzulassen. Eine kompakte Zusammenstellung der erzeugten Abbildungen könnte vielleicht auf eine Seite passen. Auch wenn das Programm die Abbildungen alle untereinander ausgibt, ist es in Ordnung, sie in der Dokumentation anders anzuordnen.
Ein akzeptabler Kompromiss kann sein, bei den 5-Rominos in der Dokumentation nur die ersten x und die letzten x generierten Abbildungen darzustellen (wobei x nicht allzu klein sein sollte) und die vollständige Sammlung in einer separaten Datei zu zeigen. Die BewerterInnen sollen/wollen auch anhand der Abbildungen und ihrer Abfolge Rückschlüsse ziehen können, wie der Algorithmus zur Aufzählung bzw. Erzeugung der Rominos funktioniert.
julia barbosa bardt said:
Hallo, könnte mir einer vielleicht diesen Satz erläutern : "... dürfen außerdem nicht an den Seiten ein und desselben dritten Quadrats anliegen" .
Es soll mindestens zwei Quadrate geben, die (locker formuliert) über Eck aneinander liegen, wo aber nicht gleichzeitig mit einem dritten Quadrat auch ein kompletter Winkel entsteht. Malen wir mal die beiden Quadrate als X. Die sollen also so liegen (es gibt zwei Möglichkeiten):
?X X?
X? ?X
An den Positionen der Fragezeichen darf aber kein Quadrat sein, denn das wäre ein drittes Quadrat, an dessen Seiten die beiden anderen anliegen.