das Haus vom Nikolaus

[gogocho]

Hallo zusammen !
Also, ich muss rekursiv bestimmen wie viel Moeglichkeiten gibt es das Haus vom Nikolaus zu zeichnen.
* 2
/ \
1---3
| X |
0---4
Also die Aufgabe lautet weiter:

Mithilfe eines zweidimensionalen Arrays int[][] edges kann man sich leicht
merken, welche der Punkte 0 bis 4 durch eine Linie verbunden sind. Wenn
gilt edges[j] != 0 bzw. edges[j] != 0, gibt es eine Linie zwischen
den Punkten i und j, sonst nicht. Der folgende Algorithmus versucht, das
Haus vom Nikolaus zu zeichnen und dabei jede gezeichnete Linie aus edges zu
entfernen.

dazu gibt es die Adjacencymatrix

public static int[][] edges = {{ 0, 1, 0, 1, 1 },
                                       { 1, 0, 1, 1, 1 },
                                       { 0, 1, 0, 1, 0 },
                                       { 1, 1, 1, 0, 1 },
                                      { 1, 1, 0, 1, 0 }};

• Implementieren Sie die vorgegebene Methode
public static int countSolutions(int pos, int linesLeft),
die als Parameter pos die Nummer des Punktes ubergeben bekommt, an dem man sich
beim Zeichnen gerade befindet sowie den Parameter linesLeft, der angibt, wieviele
Linien noch zu zeichnen sind.
Hinweis:
– Uberlegen Sie zun ̈chst, was es bedeutet, wenn keine Linie mehr zu zeichnen ist und geben Sie ein entsprechendes Ergebnis zur ̈ck.
– Falls noch Linien zu zeichnen und Sie am Punkt i angekommen sind, finden Sie
heraus, zu welchen anderen Punkten j es noch Linien gibt. Gibt es keine solche
Linie mehr, geben Sie ein entsprechendes Ergebnis zur ̈ck.
F ̈r jede m ̈gliche Linie fahren Sie rekursiv mit dem Aufsummieren der M ̈glich-
keiten fort. Denken Sie daran, vor dem rekursiven Aufruf die Linie durch ed-
ges[j] = edges[j] = 0 zu entfernen und nach dem Aufruf analog dazu
wieder zu setzen.
• Implementieren Sie nun die vorgegebene Methode
public static void main(String[] args).
Z ̈hlen Sie f ̈r jeden der Punkte, wieviele M ̈glichkeiten es gibt, von diesem Punkt aus
das Haus zu zeichnen und geben Sie anschliessend die Summe aus.

Sorry, dass es so lang ist.
Also ich kann nicht verstehen wie macht man die Beziehung zwischen edges[][] und die position (also pos) ..bzw. Knoten (0 bis 4) wenn das rekursiv sein muss? Und wie funktioniert die Adjacencymatrix eigentlich. Ich hab so viel gelesen schon im Internet darueber, aber die beziehung kann ich nickt verstehen. Und wie soll das denn rekursiv laufen?
Ich entschuldige mich noch mal, ich weiss, dass ich schon zu viel geschrieben hat. Wenn jemand mir helfen koennte, waere ich sehr dankbar sein. Schon zwei tage kann ich nicht die loesung finden..

 

[Jango]

Hausaufgaben gehören in das Forum, welches mit 'Hausaufgaben' überschrieben ist...

 

[maki]

*verschoben*

Ja nach Jahreszeit ist das Forum voll Themen wie "Haus vom Nikolaus", "Weihnachtsbaum" etc. pp., einfach mal suchen.

 

[gogocho]

Heute den ganzen tag such ich..deswegen frag ich hier..

 

[thorstenthor]

Das mit der Adjazenzmatrix ist interessant, weil sich Kanten ohne aufwand verändern lassen.

Dein Algo muss dann also beginnend von irgendwo eine ausgehende Kante löschen und mit der Kante des nächsten Knotens genauso verfahren, bis keine Kanten des aktuellen Knoten mehr vorhanden sind. Dann ist zu prüfen, ob das der Startknoten ist, und ob alle Kanten entfernt wurden. Lösung muss dann kopiert/ausgegeben werden. Bei einem Schritt zurück, muss die Kante wiederhergestellt werden.

Wenn man vereinbart:
0=keine Kante
1=Kante
2..n=die i-1gewählte Kante

..muss der Weg nicht extra gespeichert und die Adjanzenmatrix kann ausgeben werden.

 

[thorstenthor]

Ich habe vergessen, dass zwar alle Kanten besucht werden sollen, jedoch kein Kreis gesucht ist.

Jetzt hab ich das einmal geschrieben:

    public static int[][] edges = {{0, 1, 0, 1, 1},
        {1, 0, 1, 1, 1},
        {0, 1, 0, 1, 0},
        {1, 1, 1, 0, 1},
        {1, 1, 0, 1, 0}};

    public static void deleteEdges(int i, int n) {
        if (n - 2 == 8) {
            System.out.println(Arrays.deepToString(edges));
            return;
        }
        for (int k = 0; k < edges[i].length; k++) {
            if (edges[i][k] == 1) {
                edges[i][k] = n;
                edges[k][i] = 0;
                deleteEdges(k, n + 1);
                edges[i][k] = 1;
                edges[k][i] = 1;
            }
        }
    }

    public static void main(String[] args) {
        deleteEdges(0, 2); // zwei ist wichtig
    }

Die Ausgabe ist etwas kryptisch, erfüllt aber ihren Zweck.

Wenn ein Element (i,j) nicht 0 ist, dann heißt das, dass die Kante (i,j) als (edges[j] - 1). gewählt wird.

Bsp.:

[[0, 2, 0, 0, 6], [0, 0, 3, 8, 0], [0, 0, 0, 4, 0], [5, 0, 0, 0, 9], [0, 7, 0, 0, 0]]

Besucht werden Knoten: 0, 1, 2, 3, 0, 4, 1, 3, 4

Ich geb zu, das ist nicht optimal.

Parameter- und Variablennamen:

i=aktuell besuchter Knoten
k=Kante, die von i ausgeht
n=Anzahl bereits gewählter Kanten - 2


implementiert wurde ein Backtracking, der nicht endet, wenn eine Lösung gefunden ist.

 

[thorstenthor]

Andere Ausgabe:

    public static int[][] edges = {{0, 1, 0, 1, 1},
                                   {1, 0, 1, 1, 1},
                                   {0, 1, 0, 1, 0},
                                   {1, 1, 1, 0, 1},
                                   {1, 1, 0, 1, 0}};

    public static void deleteEdges(int i, int n, String s) {
        if (n == 8) {
            System.out.println(s);
            return;
        }
        for (int k = 0; k < 5; k++) {
            if (edges[i][k] == 1) {
                edges[i][k] = 0;
                edges[k][i] = 0;
                deleteEdges(k, n + 1, s + " -> " + k);
                edges[i][k] = 1;
                edges[k][i] = 1;
            }
        }
    }

    public static void main(String[] args) {
        deleteEdges(0, 0, "0");
    }

OT: Warum kann man eigentlich keine Beiträge im Nachhinein löschen?

 

[VanilleEis]

ich habe die selbe Hausaufgabe ^^

 

[Maximiliator]

scheinbar suchen mehrere Leute nach der Lösung. Ich auch. Habe die selbe Aufgabe.

 

[knoedl]

Ich such jetzt auch schon seit Stunden nach der Lösung, kriegs aber einfach nicht hin Hab schon mehrere Anläufe die mir alle richtig schienen aber keiner hat auch nur im geringsten funktioniert...

 

[thorstenthor]

Ok, die Wissenschaft nennt das ganze "Eulerpfad oder auch Eulerweg": Eulerkreisproblem ? Wikipedia

Einen Eulerkreis gibt es nicht. Wenn Kinder geärgert werden sollen, gibt man ihnen die Aufgabe, das Haus zu zeichnen, den Bleistift nicht abzusetzen, keine Linie doppelt zu zeichnen und wieder beim Startpunkt (Knoten) anzukommen.

Was ich oben jetzt noch ändern würde ist der Zugriffsmodifizierer public von edges und deleteEdges. Aber ich hab das auch einfach nur von gogocho übernommen. Man könnte auch einen zusätzlichen Parameter "edges" einführen.

Eine Musterlösung ist es trotzdem nicht. Wenn ihr die Aufgabe besprochen habt, könnt ihr die genau Aufgabenstellung ja einmal hier posten.

 

[Jango]

Einen Eulerkreis gibt es nicht. Wenn Kinder geärgert werden sollen, gibt man ihnen die Aufgabe, das Haus zu zeichnen, den Bleistift nicht abzusetzen, keine Linie doppelt zu zeichnen und wieder beim Startpunkt (Knoten) anzukommen.

Dich hat man also mit anspruchsvollen Aufgaben 'geärgert'? Ich hab mich über sowas gefreut, weil es das Hirn schult.

Irgendwie hab ich das Gefühl, dass du nur irgend etwas erzählst - nur um des Erzählens wegen...
Ich kann mich aber auch irren.

Und bitte nicht persönlich nehmen - selbst Leute, die ich beleidigen möchte, such ich mir aus - Du bist keiner von denen.

 

[thorstennn]

Dich hat man also mit anspruchsvollen Aufgaben 'geärgert'? Ich hab mich über sowas gefreut, weil es das Hirn schult.

Ich wurde nicht mit anspruchsvollen aufgaben geärgert (oder doch? k.a)

Es gibt 5 Knoten und 8 Kanten, nicht alle Knoten besitzen geraden Grad, deshalb kann es keinen Eulerkreis geben, deshalb besteht der Clou beim Zeichnen darin, dass man gedanklich erst 8 Schritte macht, bevor man wirklich anfängt zu zeichnen.

Irgendwie hab ich das Gefühl, dass du nur irgend etwas erzählst - nur um des Erzählens wegen...
Ich kann mich aber auch irren.

Es gibt sicher viele Gründe, warum Leute in Communits aktiv sind.... Interesse an "Depth-first search (DFS) zählt auch dazu..

Und bitte nicht persönlich nehmen - selbst Leute, die ich beleidigen möchte, such ich mir aus - Du bist keiner von denen.

warum auch nicht mich beleidigen? spricht ja nichts dagegen, solange man nicht selbst beleidigt wird..

 

[Andi_CH]

<10 Sekunden Aufwand (inklusive firefox starten und hier tippen)

just klick here

oder 20€ locker machen und du kannst die fertige Lösung bei mir kaufen