Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Steine aufklauben » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen Steine aufklauben
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 210

Steine aufklauben Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

In einem Feld 7*7 sind die Buchstaben von LIAOS verstreut. Ausgehend von einer Position 0,2 soll ich die Buchstaben aufsammeln, und bestimmen in welcher Reihenfolge ich sie aufsammle. H steht für Hindernisse, bei denen der Algorithmus ein return erhält. Folgender Code:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
 /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.util.ArrayList;

/**
 *
 * @author rkunstwadl
 */
public class JavaApplication1 {
    
    String[][] feld = new String[7][7];
    ArrayList<String> gefunden = new ArrayList();
    public JavaApplication1(){
        for (int i=0; i<7; i++){
            for (int j= 0; j<7; j++){
                feld[i][j]="N";
            }
        }
        feld[0][2]="Ö";
        feld[6][6]= "L";
        feld[0][1]= "A";
        feld[5][3]= "I";
        feld[0][4]= "O";
        feld[0][6]= "S";
        feld[0][0]= "H";
        feld[1][2]= "H";
        feld[2][5]= "H";
        feld[4][1]= "H";
        feld[5][1]= "H";
        feld[6][4]= "H";
        
        
        
    }

    
    
    public void traversiere(String[][] feld, int x, int y, ArrayList<String> gefunden){
        if (feld[x][y]!="H" && feld[x][y]!="Ö" && feld[x][y]!="N"){
            gefunden.add(feld[x][y]);
    }
        if (feld[x][y]=="H") return;
        if (x+1<7)  traversiere(feld, x+1,y,gefunden);
        if (y+1 <7) traversiere(feld, x, y+1,gefunden);
        if (x-1>=0) traversiere(feld,x-1,y, gefunden);
        if (y-1>=0) traversiere(feld,x,y-1,gefunden);
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        JavaApplication1 japp= new JavaApplication1(); 
        japp.traversiere(japp.feld, 0, 2, japp.gefunden);
        System.out.println(japp.gefunden);
    }
    
}
 


Mein Code erzeugt einen Stackoverflow, was ich nicht verstehe, da es doch nur ein sehr kleines Feld ist.
05.10.2017 16:14 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 304
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Ich verstehe nicht ganz: Bei tranversieren gehst Du ja in alle Nachbarfelder rekursiv. Wenn Du jetzt z. B. eins nach rechts gegangen bist und dann von diesem aus wieder ein nach links gehst usw. dann gehst Du ewig hin und her (oder hoch und runter) und hast dann natürlich eine unendliche Rekursion die unweigerlich irgendwann in einem Stack-Overflow endet.
Außerdem: Wenn es immer nur ein einzelnes Zeichen ist auf einem Feld des Spielplans, warum dann ein Array-of-Arrays-of-Strings machen und nicht eins auf char? Wäre sicherlich deutlich effizienter.

Gruß
Marco
05.10.2017 16:21 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 210

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Habe den Fehler behoben. Der richtige Code muss lauten:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
    /*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package javaapplication1;

import java.util.ArrayList;

/**
 *
 * @author rkunstwadl
 */
public class JavaApplication1 {
    
    String[][] feld = new String[7][7];
    ArrayList<String> gefunden = new ArrayList();
    public JavaApplication1(){
        for (int i=0; i<7; i++){
            for (int j= 0; j<7; j++){
                feld[i][j]="N";
            }
        }
        feld[0][2]="Ö";
        feld[6][6]= "L";
        feld[0][1]= "A";
        feld[5][3]= "I";
        feld[0][4]= "O";
        feld[0][6]= "S";
        feld[0][0]= "H";
        feld[1][2]= "H";
        feld[2][5]= "H";
        feld[4][1]= "H";
        feld[5][1]= "H";
        feld[6][4]= "H";
        
        
        
    }

    
    
    public void traversiere(String[][] feld, int x, int y, ArrayList<String> gefunden){
        if (feld[x][y]!="H" && feld[x][y]!="Ö" && feld[x][y]!="N"){
            gefunden.add(feld[x][y]);
    }
        if (feld[x][y]=="H") return;
        if (feld[x][y]!="H") feld[x][y]="B"; 
        if (x+1<7 && y>=0 && y<7 && feld[x+1][y]!="B") traversiere(feld, x+1,y,gefunden);
        if (y+1 <7 && x>=0 && x<7 && feld[x][y+1]!="B") traversiere(feld, x, y+1,gefunden);
        if (x-1>=0 && y>=0 && y<7 && feld[x-1][y]!="B") traversiere(feld,x-1,y, gefunden);
        if (y-1>=0 && x>=0 && x<7 && feld[x][y-1]!="B") traversiere(feld,x,y-1,gefunden);
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        JavaApplication1 japp= new JavaApplication1(); 
        japp.traversiere(japp.feld, 0, 2, japp.gefunden);
        System.out.println(japp.gefunden);
    }
    
}
05.10.2017 16:29 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 304
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Vielleicht noch eine Anmerkung zu dem hier:
code:
1:
2:
3:
4:
       if (feld[x][y]=="H") return;
       if (feld[x][y]!="H") feld[x][y]="B"; 

Wenn bei "H" in der ersten Zeile die Funktion schon verlassen wird, kann man mit einem "H" ja zur zweiten Zeile nie kommen. Sprich feld[x][y] kann in der zweiten Zeile niemals "H" sein so dass die Bedingung immer wahr ist und Du sie deshalb auch einfach weg lassen kannst.

Gruß
Marco
05.10.2017 17:37 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 210

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Mal eine Perspektive auf den Code:
code:
1:
2:
3:
if (feld[x][y]!="H" && feld[x][y]!="Ö" && feld[x][y]!="N"){
            gefunden.add(feld[x][y]);
    } 


reagiert auf die Redundanz:

code:
1:
2:
3:
 if (feld[x][y]!="H" && feld[x][y]!="Ö" && feld[x][y]!="N" && feld[x][y] !="B"){
            gefunden.add(feld[x][y]);
    }


In diesem Sinne hat der Code ein Unbewußtes.
09.10.2017 13:47 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 304
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Ehrlich gesagt ist es mir ein Rätsel, was Du uns mit diesem Post sagen willst, geschweige denn, ob Du eine Frage hast oder was diese sein könnte.

Gruß
Marco
09.10.2017 16:15 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 210

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Ich beschäftige mich mit der Psychoanalyse des Programmierens. Da ist es von Interesse, was als eine Form des Unbewußten in Programmen aufgefaßt werden kann. Das ist also keine Frage, sondern nur ein Anstoß für Interessierte.
11.10.2017 16:11 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 304
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Tut mir leid, ich glaube, wir sprechen nicht dieselbe Sprache. Was Du schreibst ergibt für mich von vorne bis hinten überhaupt keinen Sinn.
Du schreibst zwei if-Anweisungen hin, die identisch sind, bis auf die Bedingung. Die ist doch aber nicht gleichwertig, da im ersten Fall die Bedingung ausgeführt wird, auch wenn das Feld feld[x][y] gleich "B" ist, in der anderen aber nicht. Was ist da jetzt Deine Redundanz? Und was soll auf was "reagieren"??? "reagieren" ist doch, wenn etwas/jemand sein Verhalten durch etwas/jemand anderes/n beeinflussen lässt. Aber ich kann hier keine Verhaltensänderung von irgendetwas/irgendjemandem feststellen schon gar nicht in Abhängigkeit von etwas/jemanden anderen. Das ist einfach Unsinn!
Dann halte ich das mit Deiner Psychoanalyse auch für Geschwafel, tut mir leid. Da müsstest Du mich schon erst vom Gegenteil überzeugen...

Aber ich habe auch noch etwas programmiertechnisches auszusetzen!
In Java solltest Du niemals zwei Strings mit == oder != oder ähnliches vergleich! Das vergleicht die Referenz des String-Objekts aber nicht den String selbst! Die Strings a und b können also auch gleich sein, wenn a != b ist!
Wenn Du in Java Strings vergleichen willst, dann musst Du das mit der equals()-Methode der String-Klasse machen, also etwa a.equals(b). Oder das dann entsprechend verneinen: !a.equals(b).
Dass es häufig doch mit == und != funktioniert liegt an der Optimierung von Java, was einen Vorrat an Strings sich merkt und versucht, gleiche Strings zusammen zu fassen, so dass sie häufig dann doch dieselbe Referenz haben. Das ist aber weder garantiert noch in Wirklichkeit immer so!
Auch aus diesem Grund solltest Du also besser an Stelle von Strings char verwenden. Du hast doch pro Feld nur ein einziges Zeichen, warum dann also immer eine ganze Zeichenkette speichern? Einzelzeichen kannst Du auch tatsächlich direkt mit == oder != vergleichen. Es braucht weniger Speicher und ist generell schneller. Du müsstest dann nur mit einfachen Hochkommata arbeiten und nicht mit doppelten.

Gruß
Marco
11.10.2017 21:42 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Haevelin
Tripel-As


Dabei seit: 04.06.2013
Beiträge: 210

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Vielleicht kann ich mein Anliegen durch einen regelbasierten Ansatz klar machen:
Ein Stein ist gefunden wenn:
not(Feld.h) und not(Feld.Ö) und not(Feld.B) und not(Feld.N) ==> klaube Stein auf.

Da aber nach Feld.B nicht traversiert wird, reduziert sich diese Regel auf:
not(Feld.h) und not(Feld.Ö) und not(Feld.N) ==> klaube Stein auf.

Die Logik des Sachverhaltes wirkt sich so auf den Code aus. Da der Code den Regelbestandteil nur indirekt repräsentiert, spreche ich davon, dass es sich um ein Unbewußtes des Codes handelt.

Nochmals danke für deine Programmierungshinweise.
12.10.2017 12:33 Haevelin ist offline Beiträge von Haevelin suchen Nehmen Sie Haevelin in Ihre Freundesliste auf
as_string as_string ist männlich
Routinier


Dabei seit: 06.11.2013
Beiträge: 304
Herkunft: Heidelberg

Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen

Also, ob ich die Überprüfung auf B vor dem rekursiven Aufruf oder erst darin mache, ist für mich jetzt kein großartiger logischer Unterschied. Es ist ja nicht so als ob Du die Überprüfung auf B aufgrund äußerer Voraussetzungen Dir sparen könntest sondern nur, dass Du ein Teil der Buchstaben vor dem rekursiven Aufruf überprüfst und den Rest danach.

Übrigens ist das ganz und gar nicht äquivalent das so zu tun, wenn nicht sogar falsch! Woher weißt Du, dass das erste Feld nicht auch schon ein B beinhaltet. Du musst also eigentlich schon auf jeden Fall in der Funktion direkt vorm "aufklauben" auf B prüfen und kannst dann aber die Überprüfung vor der weiteren Rekursion weg lassen, wie Du das für die anderen Buchstaben ja auch schon tust.
Was das alles mit Psychoanalyse zu tun haben soll, ist trotzdem ein Rätsel. Ich halte das immer noch für hochtrabendes aber dafür vollkommen sinnloses Geschwätz Tut mir leid, dass ich das so sagen muss...

Gruß
Marco
14.10.2017 12:32 as_string ist offline E-Mail an as_string senden Beiträge von as_string suchen Nehmen Sie as_string in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Steine aufklauben