Sch. ... Rekursion mal wieder

[scaary]

Soderle,
Ich hab eine Reihe von Knoten gegeben. Diese knoten soll ich durchlaufen und feststellen, ob ich mit den Kanten, die zwischen den Knoten sind (auf welchen werte gespeichert sind), ein bestimmtes Wort erstellen kann.

Soweit so gut.

Die Methode getTargets macht uebrigens nichts anderes als von einem knoten alle ausgehenden knoten aufzurufen und in einer liste wiederzugeben(knoten = state).
Ich habe das ganze jetzt rekursiv geloest:

NDA nda2 = new NDA(5,0,4);

nda2.addTransition(0, 1, 'a');
nda2.addTransition(1, 2, 'a');
nda2.addTransition(2, 3, 'a');
nda2.addTransition(3, 4, 'a');

System.out.println(nda.forward("aaaa"));

    boolean forward(String word) {
        return nodeLeadsToEndNode(word, firstNode, 0);
    }

    boolean nodeLeadsToEndNode(String word, State state, int counter) {
        boolean result = false;
        System.out.println(counter);
        System.out.println(word.length());
        if (counter == word.length() && state == lastNode ) {
            result = true;
        } else if (counter == word.length() && !state.equals(lastNode)) {
            System.out.println("hello");
        }else {
            char symbol = word.charAt(counter);
            LinkedList<State> col = new LinkedList(); 
            col.addAll(state.getTargets(symbol));
            
            if(col != null){
                while(!col.isEmpty()) {
                    System.out.println(col);
                    nodeLeadsToEndNode(word, col.pop(), counter + 1);
                }
            }
        }
        return result;
    }

Die ganzen printausdruecke sind uebrigens nur zu korrekturzwekcen drin!
aber ich hab gleich mehrer Probleme:

Wenn ich eine Liste mit z.B. mehreren Objekten erstelle, steigt er trotzdem nur eine ebene tiefer und gibt mir dann false aus, wie man an dem counter sehen kann der nur 1 runter geht.

Ich hab das ganze ausserdem mal nur mit einem knoten versucht, und obwohl ich bei der System out... ausgabe bei einer manuellen abfrage, ob curser = wortlaenge und state == lastNode ist, beides male true bekommen habe, hat mein progtramm am schluss false ausgegeben. woran kann das liegen??:



NDA nda2 = new NDA(2,0,1);

nda2.addTransition(0, 1, 'a');


System.out.println(nda.forward("a"));

    boolean forward(String word) {
        return nodeLeadsToEndNode(word, firstNode, 0);
    }

    boolean nodeLeadsToEndNode(String word, State state, int counter) {
        boolean result = false;
        System.out.println(counter == word.length());
        System.out.println(state == lastNode);
        if (counter == word.length() && state == lastNode) {
            result = true;
        } else if (counter == word.length() && state != lastNode) {
            System.out.println("hello");
        }else {
            char symbol = word.charAt(counter);
            LinkedList<State> col = new LinkedList(); 
            col.addAll(state.getTargets(symbol));
            
            if(col != null){
                while(!col.isEmpty()) {
                    nodeLeadsToEndNode(word, col.pop(), counter + 1);
                }
            }
        }
        return result;
    }

false
false
true
true
false


Danke Schonmal im Voraus!

 

[SlaterB]

> while(!col.isEmpty()) {
> nodeLeadsToEndNode(word, col.pop(), counter + 1);
> }

was hier als Rückgabewert zurückkommt, ignorierst du, result wird davon nicht beeinflusst?

auf die Anzahl rekursiver Aufrufe dürfte das aber weniger Einfluss haben bzw. es sollten eher zu viele Aufrufe sein als zu wenig,
dein Log ist sehr kurz bzw. undurchschaubar, schreibe doch
System.out.println("counter?: "+counter == word.length());
statt
System.out.println(counter == word.length());

5 Ausgaben klingen andererseits passend wenig für nur einen Knoten

wie es bei 4 Nodes aussieht kann man aus der Ferne kommt vorausschauen, aber du hast doch dein Log,
schaue zu jedem rekursiven Aufruf, was die Ausgangslage ist (Parameter usw) und was daraus wird,

wie könnte bei so vielen System.out.println irgendwas unklar bleiben?

 

[scaary]

mpf..ich bin auch der groesste Depp ueberhaupt ^^

JA, danke, klar, hab das result = nodeLeadsToEndNode(word, col.pop(), counter + 1);
vergessen.

Jahaaa, manchmal sieht man den wald vor lauter Baeumen nicht

Vielen Dank dir !!
Jetzt funktioniert es einwandfrei ^^