Rekursive Methode in Iterative umwandeln

[Ascar]

hallo ich würde gerne folgenden rekursiven algorithmus in eine iterative methode umschreiben:

public Class Queens {
static int n = 0;
static in m = 0;
public static void main(String[] args){
		long time = System.currentTimeMillis();
		n = 3;
		m = n-1;
		boolean[][] checkField = new boolean[3][];
		byte[] placedQueen = new byte[n];
		// 0 = horizontal, 1 = upper diagonal, 2 = lower diagonal
		checkField[0] = new boolean[n];
		checkField[1] = new boolean[2*n - 1];
		checkField[2] = new boolean[2*n - 1];
		System.out.println("Felder: " + n);
		System.out.println("Lösungen: " + solveIter(checkField, placedQueen));
		System.out.println("Programm braucht: " + (System.currentTimeMillis() - time) + "ms.");
	
	}
	
	private static int solve(int i, boolean[][] checkField) {
		int k = 0;
		int solution = 0;
		while(k < n){		// checks first column, top -> down
			if(i+1 < n) {	// checks if we are in last column
				if(checkField[0][k] || checkField[1][k+i] || checkField[2][i-k+m]);
				else {						// computes the remaining available queen positions
					checkField[0][k] = true; // set row taken
					checkField[1][k+i] = true; // set upper diagonal taken
					checkField[2][i-k+m] = true; // set lower diagonal taken
					
					solution += solve(i+1, checkField);
					//reset last queen positioning
					checkField[0][k] = false;
					checkField[1][k+i] = false;
					checkField[2][i-k+m] = false;
				}
			}	
			
			else {	// computes solution
				if(checkField[0][k] || checkField[1][k+i] || checkField[2][i-k+m]);
				else{
					solution++;
				}
			}
				k++;
			
	}
		return solution;
	}

mein lösungsansatz sieht momentan folgendermaßen aus:

	private static int solveIter(boolean[][] checkField, byte[] placedQueen) {
		byte i = 0;
		int solution = 0;
		byte row = 0;
			while(i < n) {	// goes through all column
				// testoutprint: System.out.println("i: " + i + " row: " + row + " z+i: " + (row+i) + " i-z+m: " + (i-row+m));
				if(checkField[0][row] || checkField[1][row+i] || checkField[2][i-row+m]){
					if(row == m){
						// reset last queen positioning
						i--;
						row = placedQueen[i];
						placedQueen[i] = 0;
						checkField[0][row] = false;
						checkField[1][row+i] = false;
						checkField[2][i-row+m] = false;
						}
					else{
				 	row++; }
				}
				else {		// computes the remaining available queen positions
					if(i == m){
						//  computes solution
						solution++;
						row++;
					}
					else{
					checkField[0][row] = true; // set row taken
					checkField[1][row+i] = true; // set upper diagonal taken
					checkField[2][i-row+m] = true; // set lower diagonal taken
					placedQueen[i] = row;
					i++;
					row = 0;
					}
				}
			}	
			
	
		return solution;
	}
}

ich kriegs aber nicht hin, dass das zurücksetzen der bedrohung in der iter methode funktioniert, dass was beim rekursiven nach dem letzten abstieg passiert.


edit: ausm zweiten codestück den doppelcopy entfernt.


Der Algorithmus soll das n-damen-problem lösen und die anzahl möglicher stellungen (spiegelungen nicht beachtet) ausgeben. Die solve() methode setzt dafür immer eine Dame weiter und sobald sie einmal am ende angekommen ist, wird angefangen immer wieder eine Dame zu entfernen und eine neue Dame woanders zu setzen, solang bis alle möglichkeiten durchprobiert sind.

Das Problem für meine iterative Variante liegt für mich dabei java iterativ zu sagen, dass er diesen einen schritt zurück gehn soll und dann quasi wieder das selbe wie vorher machen. eben dass was die rekursive methode brav durch selbstaufruf und dem wegnehmen einer dame nach durchlauf einer tieferen instanz tut.

 

[Ascar]

wäre nett wenn jemand ne idee hat, wie ich die solveIter() methode zum laufen bekomm

 

[hierUndDa]

Kannst du kurz erklären, was dein Code eigentlich machen soll?

 

[muckelzwerg]

(Das N-Damen-Problem lösen.)

 

[Becky]

Moin. Folgende Sache... ich bräuchte mal ne sowohl iterative als auch rekursive methode, die prüft ob in einem string die buchstabe "a" vorkommt...

dies hier gibt die anzahl glaub ich ... bräuchte aber eine methode mit boolean wie kann ich es umschreiben. Danke schön.

public static int zaehleBuchstaben(String zeichenkette, char zeichen) {
int anzahl = 0;
for (int i = 0; i<zeichenkette.length(); i++) {
if (zeichenkette.charAt(i)==zeichen)
anzahl +=1;
}
return anzahl;
}

 

[hierUndDa]

String#substring() würde ich für die rekursive Methode verwenden und
String (Java 2 Platform SE v1.4.2)

und String#toCharArray() für die iterative.
String (Java 2 Platform SE v1.4.2)

 

[r.w.]

dies hier gibt die anzahl glaub ich ... bräuchte aber eine methode mit boolean wie kann ich es umschreiben. ...

Das wäre wohl etwas in dieser Art:

public static boolean zaehleBuchstaben(String zeichenkette, char zeichen) {
      for (int i = 0; i<zeichenkette.length(); i++) {
        if (zeichenkette.charAt(i)==zeichen)
           return true;
        }
        return false;
}