verfrühtes return

05.05.2016, 16:16

Haevelin

verfrühtes return

Hallo,

für ein Feld wird die Möglichkeit gesucht von dem Feldbeginn (0,0) zum Feldende zu traversieren, wobei Bewegungen nach links, rechts oben und unten möglich sind. Das habe ich mit Backtracking versucht, meine Methode verlangt allerdings ein return, welches ich nicht einfach einsetzen kann, ohne die Rekursion zu brechen. Wie erreiche ich ein return ohne die Rekursion abzuwürgen?

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:

public ArrayList<Point_Maze[]> auswerten(int[][] feld, Point_Maze[] weg, int anzahl, ArrayList<Point_Maze[]> al)
{ 		
                int x = weg[15-anzahl].x_koordinate;
 		int y = weg[15-anzahl].y_koordinate;
 		feld[x][y]=1;
 		if (anzahl==1) return al;
 		if ((x-1>-1)&&(y>-1)&&(feld[x-1][y]==0)&& (anzahl>0))
               {
 			feld[x-1][y]=1;
 			Point_Maze neuer_Punkt= new Point_Maze(); 			      
                        neuer_Punkt.x_koordinate=x-1; 			 
                        neuer_Punkt.y_koordinate=y;
 			weg[15-anzahl+1]= neuer_Punkt;
 			return auswerten(feld,weg,anzahl-1, al); 		
                }
 		if ((x+1>-1)&&(y>-1)&&(feld[x+1][y]==0)&&(anzahl>0)){ 			
                          feld[x+1][y]=1;
 			Point_Maze neuer_Punkt= new Point_Maze(); 			
                        neuer_Punkt.x_koordinate=x+1; 			 
                        neuer_Punkt.y_koordinate=y; 
			weg[15-anzahl+1]= neuer_Punkt; 	
		         if ((x+1 == 3)&&(y==3)) return al;
 			return auswerten(feld,weg,anzahl-1, al); 		
                   }
 		 		if ((x>-1)&&(y+1>-1)&&(feld[x][y+1]==0)&&(anzahl>0))

             {
 			feld[x][y+1]=1;
 			Point_Maze neuer_Punkt= new Point_Maze(); 
			neuer_Punkt.x_koordinate=x;
 			neuer_Punkt.y_koordinate=y+1; 
			weg[15-anzahl+1]= neuer_Punkt;
 			if ((x == 3)&&(y+1==3)) return al;
 			return auswerten(feld,weg,anzahl-1, al);
 		}
 		if ((x>-1)&&(y-1>-1)&&(feld[x][y-1]==0)&&(anzahl>0))
{
 			feld[x][y-1]=1;
 			Point_Maze neuer_Punkt= new Point_Maze(); 
			neuer_Punkt.x_koordinate=x; 
			neuer_Punkt.y_koordinate=y-1; 
			weg[15-anzahl+1]= neuer_Punkt;
 			return auswerten(feld,weg,anzahl-1, al); 
		} 	
	 		 		 	}

05.05.2016, 16:22

Auf diesen Beitrag antworten »

eulerscheZahl

Vor der Rekursion: erstelle eine ArrayList, in die das Ergebnis kommt.
Da wo du return machst, müsstest du das Ergebnis des rekursiven Aufrufs dann in diese ArrayList anfügen.
Das return kommt dann ans Ende und gibt die zu Beginn erzeugte ArrayList zurück.

05.05.2016, 17:13

Auf diesen Beitrag antworten »

Haevelin

Frägt immer noch nach einem return

public ArrayList<Point_Maze[]> auswerten(int[][] feld, Point_Maze[] weg, int anzahl, ArrayList<Point_Maze[]> al){
int x = weg[15-anzahl].x_koordinate;
int y = weg[15-anzahl].y_koordinate;
feld[x][y]=1;
if (anzahl==1) return al;
if ((x-1>-1)&&(y>-1)&&(feld[x-1][y]==0)&& (anzahl>0)){
feld[x-1][y]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x-1;
neuer_Punkt.y_koordinate=y;
weg[15-anzahl+1]= neuer_Punkt;
auswerten(feld,weg,anzahl-1, al);
return al;
}

if ((x+1<3)&&(y>-1)&&(feld[x+1][y]==0)&&(anzahl>0)){
feld[x+1][y]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x+1;
neuer_Punkt.y_koordinate=y;
weg[15-anzahl+1]= neuer_Punkt;
if ((x+1 == 3)&&(y==3)) al.add(weg);
auswerten(feld,weg,anzahl-1, al);
return al;
}

if ((x>-1)&&(y+1<4)&&(feld[x][y+1]==0)&&(anzahl>0)){
feld[x][y+1]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x;
neuer_Punkt.y_koordinate=y+1;
weg[15-anzahl+1]= neuer_Punkt;
if ((x == 3)&&(y+1==3)) al.add(weg);
auswerten(feld,weg,anzahl-1, al);
return al;
}
if ((x>-1)&&(y-1>-1)&&(feld[x][y-1]==0)&&(anzahl>0)){
feld[x][y-1]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x;
neuer_Punkt.y_koordinate=y-1;
weg[15-anzahl+1]= neuer_Punkt;
auswerten(feld,weg,anzahl-1, al);
return al;
}

}

05.05.2016, 17:20

Auf diesen Beitrag antworten »

eulerscheZahl

Ich sehe jetzt erst, dass du al bereits als Parameter mitschleifst. Dann könntest du die Funktion genausogut void machen.
Aber was spricht dagegen, das return erst am Ende auszuführen?

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:

public ArrayList<Point_Maze[]> auswerten(int[][] feld, Point_Maze[] weg, int anzahl, ArrayList<Point_Maze[]> al){
	int x = weg[15-anzahl].x_koordinate;
	int y = weg[15-anzahl].y_koordinate;
	feld[x][y]=1;
	if (anzahl==1) return al;
	if ((x-1>-1)&&(y>-1)&&(feld[x-1][y]==0)&& (anzahl>0)){
		feld[x-1][y]=1;
		Point_Maze neuer_Punkt= new Point_Maze();
		neuer_Punkt.x_koordinate=x-1;
		neuer_Punkt.y_koordinate=y;
		weg[15-anzahl+1]= neuer_Punkt;
		result.addAll(auswerten(feld,weg,anzahl-1, al));
	}
	if ((x+1<3)&&(y>-1)&&(feld[x+1][y]==0)&&(anzahl>0)){
		feld[x+1][y]=1;
		Point_Maze neuer_Punkt= new Point_Maze();
		neuer_Punkt.x_koordinate=x+1;
		neuer_Punkt.y_koordinate=y;
		weg[15-anzahl+1]= neuer_Punkt;
		if ((x+1 == 3)&&(y==3)) al.add(weg);
		auswerten(feld,weg,anzahl-1, al);
	}
	if ((x>-1)&&(y+1<4)&&(feld[x][y+1]==0)&&(anzahl>0)){
		feld[x][y+1]=1;
		Point_Maze neuer_Punkt= new Point_Maze();
		neuer_Punkt.x_koordinate=x;
		neuer_Punkt.y_koordinate=y+1;
		weg[15-anzahl+1]= neuer_Punkt;
		if ((x == 3)&&(y+1==3)) al.add(weg);
		auswerten(feld,weg,anzahl-1, al);
	}
	if ((x>-1)&&(y-1>-1)&&(feld[x][y-1]==0)&&(anzahl>0)){
		feld[x][y-1]=1;
		Point_Maze neuer_Punkt= new Point_Maze();
		neuer_Punkt.x_koordinate=x;
		neuer_Punkt.y_koordinate=y-1;
		weg[15-anzahl+1]= neuer_Punkt;
		auswerten(feld,weg,anzahl-1, al);
	}
	return al;
}

06.05.2016, 13:40

Auf diesen Beitrag antworten »

Haevelin

Hab jetzt die Funktion auf void gesetzt; sieht wie folgt aus:

public void auswerten(int[][] feld, Point_Maze[] weg, int anzahl){
int x = weg[15-anzahl].x_koordinate;
int y = weg[15-anzahl].y_koordinate;
feld[x][y]=1;
if ((x-1>-1)&&(y>-1)&&(feld[x-1][y]==0)&& (anzahl>0)){
feld[x-1][y]=1;
System.out.println("Jetzt in der Rekursion");
ArraysString(feld);
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x-1;
neuer_Punkt.y_koordinate=y;
weg[16-anzahl+1]= neuer_Punkt;
auswerten(feld,weg,anzahl-1);

}

if ((x+1<4)&&(y>-1)&&(feld[x+1][y]==0)&&(anzahl>0)){
System.out.println("Jetzt in der Rekursion");
ArraysString(feld);

feld[x+1][y]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x+1;
neuer_Punkt.y_koordinate=y;
weg[16-anzahl+1]= neuer_Punkt;
if ((x+1 == 3)&&(y==3)){
al.add(weg);
} else auswerten(feld,weg,anzahl-1);

}

if ((x>-1)&&(y+1<4)&&(feld[x][y+1]==0)&&(anzahl>0)){
System.out.println("Jetzt in der Rekursion");
ArraysString(feld);

feld[x][y+1]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x;
neuer_Punkt.y_koordinate=y+1;
weg[16-anzahl+1]= neuer_Punkt;
if ((x == 3)&&(y+1==3)) {
al.add(weg);
} else auswerten(feld,weg,anzahl-1);

}
if ((x>-1)&&(y-1>-1)&&(feld[x][y-1]==0)&&(anzahl>0)){
System.out.println("Jetzt in der Rekursion");
ArraysString(feld);

feld[x][y-1]=1;
Point_Maze neuer_Punkt= new Point_Maze();
neuer_Punkt.x_koordinate=x;
neuer_Punkt.y_koordinate=y-1;
weg[16-anzahl+1]= neuer_Punkt;
auswerten(feld,weg,anzahl-1);

}

}

Allerdings ergibt das eine unschöne Ausgabe, die ich hier protokolliere:

Jetzt in der Rekursion

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Jetzt in der Rekursion

1 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
Jetzt in der Rekursion

1 0 0 0
1 0 0 0
1 0 0 0
0 0 0 0
Jetzt in der Rekursion

1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0
Jetzt in der Rekursion

1 0 0 0
1 0 0 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 0 0 0
1 1 0 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 1 0 0
1 1 0 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 1 1 0
1 1 0 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 1 1 0
1 1 1 0
1 1 0 0
1 1 0 0
Jetzt in der Rekursion

1 1 1 0
1 1 1 0
1 1 1 0
1 1 0 0
Jetzt in der Rekursion

1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 0
Jetzt in der Rekursion

1 1 1 0
1 1 1 0
1 1 1 0
1 1 1 1
Jetzt in der Rekursion

1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1
Jetzt in der Rekursion

1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

D.h. das Feld wird durchlaufen, obwohl mit 3,3 ein Ende erreicht wurde. Ausserdem werden nicht mehr Rekursionen durchlaufen. Woran liegt das?

06.05.2016, 15:17

Auf diesen Beitrag antworten »

eulerscheZahl

Was genau stellst du dir denn vor, dass passieren sollte?
Willst du nur einen Weg finden (am besten den schnellsten)?
Oder willst du alle Wege finden, die kein Feld doppelt nutzen?
Ist das Abbruchkriterium das Erreichen des Feldes (3,3)?

08.05.2016, 15:19

Auf diesen Beitrag antworten »

Haevelin

Ich will alle Wege finden und ausgeben. Das Abbruckkriterium ist das Erreichen des Feldes (3,3)

08.05.2016, 18:20

Auf diesen Beitrag antworten »

eulerscheZahl

Ich habe bewusst kein quadratisches Feld genommen, um Indexfehler auszuschließen.

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:

import java.awt.Point;

public class Main {
	static int[][] offset = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };

	public static void FindWay(boolean[][] visited, Point current, Point target, Point[] path, int index) {
		path[index++] = current;
		if (current.equals(target)) {
			for (int i = 0; i < index; i++)
				System.out.print("(" + path[i].x + "/" + path[i].y + ") ");
			System.out.println();
			return;
		}
		visited[current.x][current.y] = true;
		for (int dir = 0; dir < 4; dir++) {
			Point next = new Point(current.x + offset[dir][0], current.y + offset[dir][1]);
			if (next.x >= 0 && next.x < visited.length && next.y >= 0 && next.y < visited[0].length && !visited[next.x][next.y]) {
				FindWay(visited, next, target, path, index);
			}
		}
		visited[current.x][current.y] = false;
	}

	public static void main(String[] args) {
		FindWay(new boolean[3][2], new Point(0, 0), new Point(2, 1), new Point[6], 0);
	}
}

Neue Frage »

Antworten »

verfrühtes return

Verwandte Themen