Wie würdet ihr anfangen (keine Lösungen bitte nur einen Ansatz geben)?

... komplette Frage anzeigen

3 Antworten

Ich würde

- zunächst die fehlenden Punkte ermitteln (also für jedes Rechteck den Punkt rechts oben und links unten)

- die horizontalen Linien sammeln (also für jedes Rechteck die Koordinaten der beiden oberen bzw. unteren Punkte)

- Die Schnittpunkte sammeln (also für jeden von den "links oben"-Punkten deiner gegebenen Rechtecke nach unten gehen und schauen, ob der sich mit einer horizontalen Linie schneidet)

- Alle vier Rechteckskoordinaten und die Schnittpunkte sind die Gesamtmenge

- Für jeden Punkt links oben und jeden Schnittpunkt prüfen:

  - gibt es einen Punkt rechts davon auf derselben Linie in der Gesamtmenge?

  - gibt es einen Punkt unterhalb davon auf der selben Linie in der Gesamtmenge?

  - gibt es den vierten Punkt in der Gesamtmenge, der das neue Rechteck komplettiert?

  - Wenn ja: Bingo, wir haben ein Rechteck gefunden.

Ich hab das nicht getestet. Vielleicht gibt es dazu aber auch noch einen anderen Ansatz, ich bin auch gespannt auf weitere Antworten.

Antwort bewerten Vielen Dank für Deine Bewertung

Die Formulierung "die sich insgesamt ergebenden Rechtecke" ist sehr schwammig. Ergeben zwei gleich hohe, nebeneinander liegende Rechtecke wieder ein Rechteck? Zählen weiße Rechtecke mit? Sind Rechtecke mit Höhe 0 erlaubt?

Wenn das eine Übungsaufgabe ist, sind wahrscheinlich nur Schnitte zwischen Rechtecken gemeint. Der Schnitt ergibt immer ein Rechteck oder ist leer. Da diese Operation assoziativ und kommutativ ist, kannst Du einfach jedes mit jedem schneiden und das alles solange wiederholen, bis keine neuen Rechtecke mehr dazukommen. Alternativ lassen sich alle Rechtecke rekursiv als Schnitt einer Teilmenge der gegebenen Rechtecke ermitteln.

Dabei fehlt aber zum Beispiel das flache blaue Rechteck, das in Deinem Bild oben aufliegt. Will man das mitnehmen, steigt der Aufwand enorm: Bestenfalls kannst Du alle Kombinationen aus je zwei senkrechten und zwei waagrechten Rechteckseiten darauf untersuchen, ob sie wieder ein Rechteck bilden (d.h. alle vier Seiten lang genug sind). Zusammen mit den Rasterseiten bekommst Du damit garantiert alle Rechtecke — auch weiße und gemischte.

Bevor Du das programmierst, solltest Du klären, ob das wirklich gewünscht ist. Ich würde dazu folgende Frage stellen:

Gegeben: Ein Raster 3x3 und zwei Rechtecke 1x3 bzw. 3x1 mittig angeordnet. Das ergibt ein griechisches Kreuz. Wie viele Rechtecke ergeben sich hier? Bei Schnittbildung kommt nur eins dazu, im allgemeinen Fall sind's 33.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von ralphdieter
25.01.2016, 12:59

Während ich schrieb, hat Schachpapa etwas Licht ins Dunkel gebracht. Der Raster-Rand zählt offenbar nicht mit; beim griechischen Kreuz hat man damit deutlich weniger Rechtecke. Aber schwammig bleibt's trotzdem: Mir ist nicht ganz klar, wie zum Beispiel ein Schachbrett (aus Einheitsquadraten) gezählt wird. Ich glaube, dass sich hier die genannten Lösungshinweise (http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf23/loesungshinweise231.pdf) unterschiedlich verhalten.

Korrektur: In meinem "allgemeinen Ansatz" muss man zuerst Rechteckseiten vereinigen, wenn sie sich teilweise überlappen oder aneinander grenzen.

0

Wo hast du das denn ausgegraben? Das ist die Aufgabe 5 aus der 1. Runde des 23. Bundeswettbewerbs Informatik von 2004. Auf der Seite http://www.bundeswettbewerb-informatik.de/ findest du im Aufgabenarchiv diese und andere Aufgaben und auch Lösungshinweise.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Kyraxan
25.01.2016, 11:45

Das ist eine Aufgabe dich ich bekommen habe von meinem Praktikum.

0

Was möchtest Du wissen?