Informatiker Board | Druckvorschau: verfrühtes return

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- verfrühtes return (http://www.informatikerboard.de/board/thread.php?threadid=3002)

Geschrieben von Haevelin am 05.05.2016 um 16:16:

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); 
		} 	
	 		 		 	}

Geschrieben von eulerscheZahl am 05.05.2016 um 16:22:

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.

Geschrieben von Haevelin am 05.05.2016 um 17:13:

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;
}

}

Geschrieben von eulerscheZahl am 05.05.2016 um 17:20:

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;
}

Geschrieben von Haevelin am 06.05.2016 um 13:40:

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?

Geschrieben von eulerscheZahl am 06.05.2016 um 15:17:

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)?

Geschrieben von Haevelin am 08.05.2016 um 15:19:

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

Geschrieben von eulerscheZahl am 08.05.2016 um 18:20:

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);
	}
}