Erste Schritte Haus des Nikolaus - Rekursion

[Sciles]

Heyho!

Ich mach gerade meine Hausaufgabe und bin ein bisschen am Verzweifeln. Allgemein geht es darum, alle Möglichkeiten zu finden, ein Haus des Nikolaus zu bilden; dabei sind die Ecken so definiert:

2
/ \
1---3
| X |
0 ---4

Wir müssen das Problem per Rekursion lösen. Wir müssen die Methode 'public static int countSolutions (int pos, int linesLeft)' bearbeiten, wobei pos für die Nummer des Punktes und linesLeft angibt, wie viele Linien noch abzulaufen sind. Bisher habe ich das hier:

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 int countSolutions (int pos, int linesLeft) {
      int solutions = 0;
       if (linesLeft == 0) {
            solutions = + 1;
        }
       else {
        for (int k = 0; k < 5; k++) {
            if (edges[pos][k] == 1) {
                edges[pos][k] = 0;
                edges[k][pos] = 0;
                countSolutions(k, linesLeft - 1);
                edges[pos][k] = 1;
                edges[k][pos] = 0;
            }
        }
       }
        return solutions;
    }

Bisher funktioniert das aber - unüberraschenderweise - noch nicht sonderlich gut. Ich weiß a) nicht, wie ich es schaffe, dass die eine Möglichkeit, das Haus abzulaufen dann aus dem Code gestrichen wird und b) kommt bei den solutions immer 0 raus, es sei denn, ich setzte linesLeft von Anfang an auf 0.

Ich glaube, ich hab einfach irgendeinen schwerwiegenden Denkfehler über diese wohl eigentlich einfache Aufgabe. Ich würde mich über etwaige Hilfe freuen!

Danke im Voraus!

 

[Flown]

Kannst du mal die genaue Beschreibung des Beispiels hochladen?

 

[Sciles]

Der genaue Wortlaut der Aufgabe ist der hier:

In dieser Aufgabe soll rekursiv die Anzahl der M¨ oglichkeiten bestimmt werden, das Haus vom Nikolaus zu zeichnen. Dabei kann mit dem Zeichnen des Hauses an jeder beliebigen Stelle begonnen werden, jede Linie darf jedoch nur genau einmal gezeichnet werden. 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[a] != 0 bzw. edges[a] != 0, muss eine Linie zwischen den Punkten i und j gezeichnet werden, sonst nicht. Der folgende Algorithmus versucht, das Haus vom Nikolaus abzulaufen und dabei jede abgelaufene Linie in edges auf 0 zu setzen.

Implementieren Sie die vorgegebene Methode public static int countSolutions(int pos, int linesLeft), die als Parameter pos die Nummer des Punktes übergeben bekommt, an dem man sich beim Ablaufen gerade befindet sowie den Parameter linesLeft, der angibt, wie viele Linien noch nicht abgelaufen sind. Hinweis:
– Überlegen Sie zunächst, was es bedeutet, wenn keine Linie mehr abzulaufen ist und geben Sie ein entsprechendes Ergebnis zurück.
– Falls noch Linien abzulaufen sind und Sie am Punkt i angekommen sind, finden Sie heraus, welche Linien vom Punkt i aus noch abzulaufen sind. 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öglichkeiten fort. Denken Sie daran, vor dem rekursiven Aufruf die Linie durch edges[a] = edges[a] = 0 als bereits abgelaufen zu markieren und nach dem Aufruf die Markierung wieder zu entfernen.

 

[Flown]

Was ist die Lösung, bzw. was soll dann rauskommen?

 

[Flown]

countSolutions(k, linesLeft - 1);
edges[pos][k] = 1;
edges[k][pos] = 0;

sollte eher so aussehen:

solutions += countSolutions(k, linesLeft - 1);
edges[pos][k] = 1;
edges[k][pos] = 1;

 

[Thallius]

Also ich finde das Problem ganz schön komplex. Ist zwar nicht meine Art aber hier mal eine Lösung.

public class Nicolaus {
    static int [][] sourceEdges = {
            { 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 main(String[] args) {
        for(int start = 0; start < 5; start++) {
            System.out.println("Start painting at "+start);
            int[] solutionArray = new int[9];
            int[][] edges = copyEdges(sourceEdges);
            drawNicolaus(edges, solutionArray, start, 0);
        }
    }

    public static void printEdges(int[][] matrix) {
        for(int i=0;i<5;i++) {
            String out = "";
            for(int j=0;j<5;j++) {
                out+=matrix[i][j];
            }
            System.out.println(out);
        }
    }

    public static int[][] copyEdges(int[][] edges) {
        int [][] newEdges = new int[5][5];
        for(int i=0; i<5; i++) {
            for(int j=0; j<5; j++) {
                newEdges[i][j]=edges[i][j];
            }
        }
        return newEdges;
    }

    public static int drawNicolaus (int[][] edges, int[] solutionArray, int start, int lineCount) {
        // System.out.println("Draw: "+start+ " Count: "+lineCount);
        solutionArray[lineCount]=start;
        //printEdges(edges);
        if(lineCount==8) {
            String out = "Solution found: ";
            for(int i=0;i<9; i++) {
                if(i!=0)
                    out+=",";
                out+=solutionArray[i];
            }
            System.out.println(out);
            return lineCount-1;
        }

        for(int index=0; index<5; index++) {
            if(edges[start][index]==1) {
                int[][] newEdges = copyEdges(edges);
                newEdges[index][start]=0;
                newEdges[start][index]=0;
                lineCount = drawNicolaus(newEdges, solutionArray, index, lineCount+1);
            }
        }
        return lineCount-1;
    }
}

Gruß

Claus

 

[Sciles]

Das ist die komplette Angabe... was da genau raus kommen soll, hab ich mich ehrlich gesagt auch schon gefragt. Ich hab angenommen, dass das Programm vielleicht die Lösungen von einem bestimmten Punkt ab zählen soll, aber da bin ich mir auch nicht 100%ig sicher.

Oh... Ja, das klingt schon sinnvoller! Danke schonmal!

 

[Flown]

@Thallius deine Methode sollte die Anzahl der Möglichen Lösungen liefern nicht die Lösungen. Aber wenn es insgesamt 88 sind, dann ist das richtig.

 

[Thallius]

@Thallius deine Methode sollte die Anzahl der Möglichen Lösungen liefern nicht die Lösungen. Aber wenn es insgesamt 88 sind, dann ist das richtig.

Naja die Anzahl herauszufinden fand ich jetzt nic so spannend. Und die Lösungen meiner Methode jetzt noch zu zählen ist ja nicht so schwierig. Ob meine Lösung richtig ist kann ich auch nicht versprechen, war ein aus einer Bierlaune heraus entstandener Code.

Gruß

Claus