Brauche dringend Hilfe!

[++nancy++]

Hallo an alle!!

Habe ein sehr großes Problem.
Bin Wirtschaftsstudentin und muss leider ein Informatikfach belegen, welches ich bis jetzt noch so meistern konnte.
Doch nun haben wir eine Aufgabe bekommen, da fehlen mir einfach die Ideen.
Diese lautet wie folgt:

Wir sollen ein n x m - Gitter anlegen, welches aus Quadraten zusammengesetzt ist. Undzwar sind die Quadrate in einer Dreiform. D.h. es gibt 6 mögliche Anordnungen von jeweils 3 Quadraten.
Hier ein Bild zur Verständniss:


Ein 2 x 9 - Gitter könnte z.B so gefüllt werden:


Jetzt sollen wir für eine beliebige Eingabe für n und m die Anzahl der Möglichkeiten für das Auslegen des Gitters in Dreiform herausfinden.
So gibt es z.B für ein 2 x 3 - Gitter 3 Möglichkeiten und für ein 2 x 9 - Gitter 41 Möglichkeiten.
Dabei sollen symmetrische Möglichkeiten doppelt gezählt werden.
Die Lösung darf auch auf mathematischen Überlegungen aufbauen.

Ich hoffe mir kann jemand von euch helfen, wäre wirklich super!! :lol:
Bin euch für jede Hilfestellung sehr dankbar.

 

[SebiB90]

Also, ich hab grad mal die Aufgabe gelöst, weil ich die Aufgabe interessant fand.
Dauert also gar net so lange

Wie weit biste denn?
Paar Tipps:
-Wenn die Anzahl der Felder nicht durch 3 Teilbar ist, gibt es keine möglichkeit. Also m*n % 3 muss 0 sein.
-Das Feld kann man als 2d Array darstellen (z.b. int array)
-Freies Feld ist 0, jeder Stein dann ne höhere Zahl. Die Quadrate die zu einem Stein gehören die gleiche Zahl
-Typische Backtracking Aufgabe die man rekrusiv leicht lösen kann, würde ich sagen

Versuchs und stell dann am besten genau fragen, wenn du nicht weiter kommst

 

[Gelöschtes Mitglied 5909]

http://de.wikipedia.org/wiki/Backtracking

da is ne gute beschreibung für das standard vorgehen

 

[Guest]

ey leute, ich sitze hier schon die ganze Zeit vor der Aufgabe und komme einfach nicht voran.Gibt es nicht noch was leichteres als backtracking, ich bin langsam verzweifelt :cry:. Habt ihr nicht noch andere vorschläge oder etwas was mir weiter hilft.

 

[++nancy++]

P.S. Der Gast, das bin natürlich ich. Hatte mich nur vergessen einzuloggen

MfG

Nancy

 

[SebiB90]

also einfacher kann man es glaub ich nicht lösen. ich wüsste jedenfalls nicht auf anhieb wie.
zeig doch dein momentanen code, dann können wir gemeinsam weiter schauen.
wenn ich dir den code jetzt geb, bringt dir es nix.

 

[SlaterB]

die Steine sind ja relativ einfach,
die verwinkelten muss man eh immer zu einem 2x3-Block zusammenlegen, vermute ich spontan,
oder hat schon jemand ein Beispiel mit einer etwas interessanteren Struktur gefunden?

selbst wenn dem nicht so ist, solltest du allein schon zu Testzwecken
erstmal nur mit Steinen 3x1, 1x3, 3x2 und 2x3 arbeiten,

oder gar nur einen davon, 3x1, damit ist die Rekursion zwar recht linear,
aber wenn man das schon mal hinbekommt ist das ein erster guter Schritt

wenn man gar keinen Ansatz hat, dann hilft das natürlich eher wenig weiter


edit:
ach schade, aus den Eckstücken kann man auch größeres zusammenbauen, z.B. ein größeres Eckstück:

aacc
abbc
  bd
  dd

 

[SebiB90]

einfach oben links inner ecke anfangen. probieren was rein passt,
rein packen. nächstes feld. wieder rum probieren usw. bis
a) Das Feld komplett ist, dann zähler um 1 lösung erhöhen
b) nichts mehr rein passt, aber das feld nicht komplett ist.
In beiden Fällen den letzten Stein wieder rausnehmen und versuchen nen anderen einzusetzen.