Rekursive Methode in Iterative umwandeln

A

Ascar

Neues Mitglied
hallo ich würde gerne folgenden rekursiven algorithmus in eine iterative methode umschreiben:
Java:
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:

Java:
	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.
 
Zuletzt bearbeitet:
A

Ascar

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

Becky

Mitglied
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;
}
 
Zuletzt bearbeitet:
R

r.w.

Bekanntes Mitglied
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:
Java:
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;
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
G rekursive u iterative Methode Java Basics - Anfänger-Themen 8
macle Rekursive String Methode, Gerade Zahlen rausfiltern Java Basics - Anfänger-Themen 10
J Rekursive swapArray Methode Java Basics - Anfänger-Themen 69
D Rekursive Methode Java Basics - Anfänger-Themen 8
O Quersumme rekursive Methode Java Basics - Anfänger-Themen 3
M Rekursive Methode Programmieren Java Basics - Anfänger-Themen 3
J rekursive Methode Java Basics - Anfänger-Themen 26
J Rekursive Methode - Ziffern einer Zahl ausgeben Java Basics - Anfänger-Themen 2
S Rekursive Methode Java Basics - Anfänger-Themen 8
O Rekursive Methode Java Basics - Anfänger-Themen 4
V Methoden Rekursive Methode mit String als Rückgabe Java Basics - Anfänger-Themen 7
K Rekursive Methode Java Basics - Anfänger-Themen 1
K Rekursive Methode für Fakultät mit BigInteger Java Basics - Anfänger-Themen 10
L Rekursive Methode a * b berechnen Java Basics - Anfänger-Themen 2
L Rekursive Methode zur Berechnung der Potenz q hoch p Java Basics - Anfänger-Themen 17
J Methoden Rekursive Return Methode Java Basics - Anfänger-Themen 2
P Methoden Rekursive Methode für Potenzen Java Basics - Anfänger-Themen 2
S Int zu Hexadezimal - Rekursive Methode Java Basics - Anfänger-Themen 2
C rekursive methode Java Basics - Anfänger-Themen 2
R rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
R Rekursive Methode, Files finden Java Basics - Anfänger-Themen 2
C rekursive Methode verstehe nicht! Java Basics - Anfänger-Themen 3
S Methoden rekursive Methode funktioniert nicht Java Basics - Anfänger-Themen 4
E Rekursive Methode Java Basics - Anfänger-Themen 3
C Rekursive Methode - Ziffern in Zahl Java Basics - Anfänger-Themen 33
G Rekursive Methode Java Basics - Anfänger-Themen 3
E Rekursive Methode mit Zufallsarray Java Basics - Anfänger-Themen 6
E Rekursive Methode Java Basics - Anfänger-Themen 18
M Rekursive Methode - wo ist der Fehler? Java Basics - Anfänger-Themen 4
J rekursive methode Java Basics - Anfänger-Themen 6
H ScrollBar inaktiv / Rekursive Methode Java Basics - Anfänger-Themen 4
J Rekursive Methode Java Basics - Anfänger-Themen 11
G Rekursive Methode Java Basics - Anfänger-Themen 5
J Rekursive Methode: Fakultaet berechnen Java Basics - Anfänger-Themen 5
G rekursive Methode Java Basics - Anfänger-Themen 3
G Rekursive Methode Java Basics - Anfänger-Themen 7
veryck Methoden Rekursive Methoden mit Rückgabeparameter Java Basics - Anfänger-Themen 9
M Rekursive Prüfung ob ein Array sortiert ist... Java Basics - Anfänger-Themen 4
R Methoden rekursive Methoden Java Basics - Anfänger-Themen 6
B Treetable (rekursive Funktion) aufbauen von Datenbank Java Basics - Anfänger-Themen 4
M rekursive division/0 mit exception Java Basics - Anfänger-Themen 18
M Rekursive Dateiliste erstellen mit Dateiendung(en) ?? Java Basics - Anfänger-Themen 4
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
T Stack Overflow - Rekursive Fibonacci Java Basics - Anfänger-Themen 10
B Datentypen Suchbaum - Rekursive Ausgabe Java Basics - Anfänger-Themen 1
M Methoden Binäre Suche als rekursive Variante Java Basics - Anfänger-Themen 5
B Rekursive Algorithmus schreiben Java Basics - Anfänger-Themen 8
S Eine rekursive Lösung Java Basics - Anfänger-Themen 4
M Rekursive Suche in einem Feld Java Basics - Anfänger-Themen 11
N Rekursive Addition mit Scanner Java Basics - Anfänger-Themen 12
shiroX OOP Rekursive und Iterative Definition Java Basics - Anfänger-Themen 2
B Methoden Rekursive Methoden Java Basics - Anfänger-Themen 2
T Iterative Pi Berechnung in Rekursive Java Basics - Anfänger-Themen 2
D Methoden Rekursive Methoden Java Basics - Anfänger-Themen 13
M Stürzen alle Rekursive Methoden irgendwann ab? Java Basics - Anfänger-Themen 11
D Primzahlen und Rekursive Liste Java Basics - Anfänger-Themen 29
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
N Methoden Rekursive Fibonaccizahlen mit Array Java Basics - Anfänger-Themen 2
R Rekursive Ausgabe eines Binärbaums Java Basics - Anfänger-Themen 4
J Methoden Rekursive Potenz ohne Math.Pow() Java Basics - Anfänger-Themen 9
S Labyrith Rekursive Wegsuche Java Basics - Anfänger-Themen 4
U Dezimal zu Hexadezimal rekursive Funktion Java Basics - Anfänger-Themen 8
M rekursive Funktion zur Berechnung der Spiegelzahl Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
A rekursive Listen in Java? Java Basics - Anfänger-Themen 5
B OOP Einfach verkettete Liste - rekursive Methoden Java Basics - Anfänger-Themen 1
U Rekursive lösung von pascal dreieck Java Basics - Anfänger-Themen 11
N Rekursive Berechnung der Höhe eines binären Baumes Java Basics - Anfänger-Themen 4
K Rekursive Methoden Java Basics - Anfänger-Themen 15
K Rekursive Funktion (Verständnissfrage) Java Basics - Anfänger-Themen 5
S Rekursive Bruch potenzierung Java Basics - Anfänger-Themen 2
D rekursive Summenberechnung Java Basics - Anfänger-Themen 8
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
A HILFE! Rekursive Funktion Java Basics - Anfänger-Themen 20
kulturfenster rekursive Binaere Suche Java Basics - Anfänger-Themen 12
F Rekursive Aufrufe, Parameterübergabe, call by reference Java Basics - Anfänger-Themen 3
G Rekursive Berechnung von n über k schlägt fehl Java Basics - Anfänger-Themen 5
B Rekursive & schreiben im ArrayList Java Basics - Anfänger-Themen 2
J Rekursive Fkt. Java Basics - Anfänger-Themen 2
A Rekursive Dateisuche Java Basics - Anfänger-Themen 12
K rekursive Funktion mit mehreren Parametern Java Basics - Anfänger-Themen 5
N rekursive Beispiele Java Basics - Anfänger-Themen 3
ven000m Rekursive Funktionen - Frage Java Basics - Anfänger-Themen 16
D rekursive ausgabe einer zahl Java Basics - Anfänger-Themen 14
S Rekursive Funktionen in imperative Funktionen umwandeln Java Basics - Anfänger-Themen 2
M Rekursive Binärsuche Java Basics - Anfänger-Themen 6
S rekursive methoden Java Basics - Anfänger-Themen 5
A Methode in einer anderen Klasse verwenden Java Basics - Anfänger-Themen 1
Eule25 Methode mit Array Java Basics - Anfänger-Themen 4
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
S HashMap contains() Methode Java Basics - Anfänger-Themen 1
F Methoden Methode richtig aufrufen Java Basics - Anfänger-Themen 3
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
JD_1998 Random Array sortieren mit Hilfe einer Methode Java Basics - Anfänger-Themen 4
T Methode implementieren Java Basics - Anfänger-Themen 21
JD_1998 Vorgegebene Methode erweitern um Hex -> Dezimal umzuwandeln Java Basics - Anfänger-Themen 1
A While Schleife - buubelsort methode Java Basics - Anfänger-Themen 2
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
X compareTo Methode wird ignoriert Java Basics - Anfänger-Themen 7
B Wie kann ich etwas vor der Main-Methode ausführen? Java Basics - Anfänger-Themen 21

Ähnliche Java Themen

Anzeige

Neue Themen


Oben