Rekursion < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:10 Mi 11.03.2009 | | Autor: | stefan00 |
| Aufgabe | ![[]](/images/popup.gif) http://home.arcor.de/snuernberg/puzzle.png
Das oben abgebildete Puzzle besteht aus neun Teilen. Davon haben jeweils die vier Eckteile (A bis D) und die vier Randteile (1 bis 4) ähnliche Formen. Die Anordnung der Teile des Puzzles wird mit einer Liste beschrieben, in der die Bezeichnungen der Teile von oben nach unten, von links nach rechts eingetragen sind. Die Liste L=<A, 1, B, 4, X1, 2, D, 3, C> beschreibt die oben gezeigte Anordnung. Der Index i beim Xi beschreibt die Orientierung dieses Puzzleteils.
(a) Bei dem Versuch, beim Zusammensetzen der Teile die richtige Anordnung zu
finden, kann man verschiedene Möglichkeiten ausprobieren. Bestimmen Sie die Anzahl der sinnvollen Möglichkeiten, das Puzzle zusammenzusetzen. Sinnvoll heißt hierbei, dass ein Eckstück bei den verschiedenen Möglichkeiten stets nur auf eine Eckposition und ein Randstück nur auf eine Randposition gelegt werden darf. Das mittlere Teil X bleibt immer in der Mitte, ist aber drehbar. Desweiteren gehen wir davon aus, dass wir wissen, dass Teil A in der oberen linken Ecke liegen muss und dass alle Puzzleteile mit der "Bildseite" nach oben liegen.
(b) Geben Sie kurz und präzise die Idee eines rekursiven Algorithmus an, der die
in (a) bestimmten Möglichkeiten zur Anordnung der Teile erzeugt. Geben Sie die ersten zehn erzeugten Anordnungsmöglichkeiten in Listenform an. |
Hallo,
Ich habe versucht, die Aufgabe mittels Baum zu lösen, komme aber beim Durchlauf durch den Baum nicht zur gewünschten Ausgabe. Wie kann ich die o.a. Liste in spitzen Klammern rekursiv durchlaufen, um alle Anordnungen angeben zu können. Ich habe 9 Positionen, die ich bestücken muss, die erste ist fest mit A vorgegeben. Dann eine Zahl, ein Buchstabe, wieder eine Zahl, dann die Drehposition mit X bezeichnet (4mal), dann wieder eine Zahl, usw. Ich komme leider auf keinen wirklich sinnvollen Ansatz, hat jemand einen Tipp?
Vielen Dank für die Hilfe.
(Ich habe diese Frage in keinem anderen Forum gestellt.)
Grüße, Stefan.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:06 Do 12.03.2009 | | Autor: | Gilga |
http://en.wikipedia.org/wiki/Permutation#Numbering_permutations
Rekursion: Funktion ruft sich selbst mit inkrementierter Zahl auf
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:48 Fr 13.03.2009 | | Autor: | stefan00 |
Hallo,
>
> http://en.wikipedia.org/wiki/Permutation#Numbering_permutations
vielen Dank für den Link.
>
> Rekursion: Funktion ruft sich selbst mit inkrementierter
> Zahl auf
hm, danke für deine Hilfe. Könntest du das noch ein klein wenig ausführen? Ich habe verstanden, dass es um einen Permutationsalgorithmus geht, so scheint es zumindest. Die erste Position bleibt hier fest mit A belegt, die zweite ist ein Buchstabe, die dritte eine Zahl, die vierte das Drehstück mit X1, X2, X3 und X4, dann wieder eine Zahl, ... usw... Dabei dürfen die vorhergehenden Zahlen/Buchstaben ja nicht mehr vorkommen. Man muss also im Prinzip eine Position festhalten und die anderen durchgehen, zwischendurch muss man Positionen wechseln (swap), ok, aber wie mache ich das mit einer Rekursion? Das Prinzip der Rekursion besagt ja, dass ich etwas Kompliziertes auf etwas Einfaches zurückführe und das immer wieder, bis es stoppt. Ich habe leider noch keinen Durchblick. Kannst Du mir nochmal helfen?
Vielen Dank und schönen Gruß, Stefan.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:56 Fr 13.03.2009 | | Autor: | Gilga |
Stimmt. Da fehlt noch einiges zur Lösung.
Die brachiale Lösung wäre es einfach mehrere Permutationsgruppen zu bilden (für Eckstücke, Randstücke, Rotationen des Mittelstückes). Die aktuelle Permutationszahl wäre dann ein Vektor der Länge 3 und jeder Aufruf der Rekursion überprüft die aktuelle Permutaion der durch diese Nummer definiert ist gibt "Erfolg mit Permutaion... " zurück oder dekrementiert den Vektor und ruft dann sich selbst auf.
(Bei der rotation wäre z.b die 4 Ausrichtungen enthalten und das erste element bestimmt die Orientierung)
Richtig toll ist die Lösung nicht, erfüllt aber die Aufgabenstellung
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:12 So 15.03.2009 | | Autor: | stefan00 |
Hallo,
> Stimmt. Da fehlt noch einiges zur Lösung.
> Die brachiale Lösung wäre es einfach mehrere
> Permutationsgruppen zu bilden (für Eckstücke, Randstücke,
> Rotationen des Mittelstückes).
ja, so habe ich es dann auch letztendlich gelöst und in Java umgesetzt. Ich habe das Drehstück für jede Position in eine Schleife gepackt und dann jedes End- und Randstück vertauscht und rekursiv permutiert. Das hat soweit ganz gut geklappt.
Vielen Dank, der Hinweis bzgl. Permutationsalgorithmus war auf jeden Fall sehr gut.
Gruß, Stefan.
|
|
|
|
![[]](http://home.arcor.de/snuernberg/puzzle.png){kind=small}
http://home.arcor.de/snuernberg/puzzle.png