• Wir präsentieren Dir heute ein Stellenangebot für einen Frontend-Entwickler Angular / Java in Braunschweig. Hier geht es zur Jobanzeige

Backtracking und Rekursion

V

Vani_x

Mitglied
Guten Abend,

ich hatte mir selber eine Aufgabe gestellt. Und zwar wollte ich eine Zahl N nehmen. Also beispielsweise N = 3, dann wird ein Array der Größe 2*N kreiert. Und in diesem Feld wird per Rekursion und Backtracking eine Lösung gesucht.

Also, wenn N = 3 ist, dann werden die Zahlen 1, 2 und 3 in das Feld so reingelegt, sodass der Abstand immer um die Zahl selber ist. Also z.B. wenn im ersten Feld eine 3 ist, dann muss nach drei Feldern wieder eine 3 stehen. Die Zahlen 1,2,3 müssen doppelt vorkommen, sonst macht das garkeinen Sinn.

Eine Lösung für N=3 wäre:



Lösung1.PNG


Ich weiß ungefähr, wie ich das realisieren möchte, aber es zu codieren, ist für mich fast unmöglich.

Bin für jeden Tipp sehr dankbar.
 
O

Oneixee5

Bekanntes Mitglied
Was finden nur immer alle an der Rekursion? Rekursion hat gewichtige Nachteile. Ich gehe sogar soweit und behaupte: Rekursion ist kein guter Stil - Rekursive Programme haben in der Regel keine gute Performance. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation der Kontext gesichert, was zu zusätzlichem Programmcode und höherem Arbeitsspeicherverbrauch führt. Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren und umgekehrt.
 
V

Vani_x

Mitglied
Ich will jetzt nicht unhöflich klingen, aber wäre eher lieber über ein Tipp erfreulich, der mir dabei hilft, das Problem zu lösen. Trotzdem danke ich dir für die Antwort.

Ich bin auch kein Fan von Rekursion, aber muss das üben für den Kurs, den ich besuche.
 
H

httpdigest

Top Contributor
Zuersteinmal brauchst du eine Strategie, was denn genau ein rekursiver Aufruf repräsentiert. Ich würde vorschlagen, dass ein rekursiver Aufruf das zweimalige Setzen, Prüfen bzw. Weitermachen und wieder "Entfernen" einer der drei Zahlen (in deinem Beispiel mit N=3) in dem Array repräsentiert.
Ich würde also eine Methode schreiben, die per Schleife über alle sinnvollen im Array verfügbaren Stellen geht, und versucht, an den aktuell zwei möglichen Stellen (also i und i+k+1) die aktuelle Zahl `k` zu setzen und dann mit der nächsten Zahl `k+1` weitermacht. Wenn `k == N+1` ist, dann wird das aktuelle Ergebnis bzw. der aktuelle Zustand ausgegeben.

Dass Rekursion (in Java) zu meist im Vergleich zu iterativen Lösungen ineffizienteren Lösungen führt, ist nur dem relativ dummen JIT Compiler geschuldet und der Tatsache, dass die JVM keine effiziente tail-recursion unterstützt. In rekursiven Algorithmen denken zu können, ist eine unbedingt zu erlernende Grundfertigkeit, die einem auch in anderen eher puren funktionalen Programmiersprachen (ohne Schleifen) zugutekommt und generell das abstrakte Denken fördert.
 
L

LimDul

Top Contributor
Idee:

- Array anlegen
- Hilfs-Methode schreiben, die überprüfen kann ob eine Array-Belegung (die auch noch nicht vollständig sein muss) bisher gültig ist.
- Dann deine rekursive Methode. Als erstes wird an Stelle 1 eine 1 gesetzt
- Hilfsmethode aufrufen. Wenn ja, ruft die Methode sich selber auf und macht an Stelle 2 weiter
- Wenn nein, die 1 durch die 2 austauschen und wie oben
usw.
 
H

httpdigest

Top Contributor
@LimDul Eine explizite Gültigkeitsprüfung brauchst du nicht, da man von vornherein gleich nur gültige Belegungen generieren kann (so es denn der Schleifenindex zulässt).
 
V

Vani_x

Mitglied
Bin jetzt soweit gekommen, aber kriege das irgendwie nicht ganz hin. Wo ist mein Denkfehler?

Aufgabe1:
public class Aufgabe1 {

    static int[] funktion;
    static int zaehler = 0;

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        funktion = new int[2 * N];
        solve(N);
    }

    public static void solve(int N) {

        if (N <= 0)
            return;

        for (int i = 0; i < funktion.length; i++) {
            if (i  < funktion.length - 1) {
                if (funktion[i] == 0) {
                    funktion[i] = N;
                    if (funktion[i + N + 1] != N + 1  && funktion[i + N + 1] == 0) {
                        funktion[i + N + 1 ] = N;
                    } else {
                        funktion[i] = 0;
                        funktion[i + 1] = N;
                        funktion[i + N + 2 ] = N;
                    }
                    solve(N - 1);
                }
            } else {
                solve(N + 1);
            }
        }
    }
}
 
H

httpdigest

Top Contributor
funktion[i + N + 1] ist falsch. Die zwei Zahlen sind ja nicht immer im Abstand von N voneinander entfernt. Der Abstand hängt von der Zahl selber ab.
Bzw. du solltest klären, was N bei dir eigentlich ist.
Ich würde generell vorschlagen, dass du erstmal versuchst, ohne globalen Zustand (static Variablen) auszukommen. Versuche mal, den Algorithmus rein funktional zu formulieren. Hierzu brauchst du natürlich eine Hilfsmethode, die entsprechend mehr als nur einen Parameter bekommt.
 
V

Vani_x

Mitglied
Naja, hatte es versucht zu machen, dass N immer die Zahl ist, die gerade eingesetzt wird, wenn die Funktion solve aufgerufen wird. Bei solve(3) wäre in dem Fall mein N = 3.
 
H

httpdigest

Top Contributor
Ja, aber du brauchst dann ja auch noch eine Zahl (ich nannte sie `k`), die repräsentiert, welche Zahl denn nun gerade dran ist (von 1 angefangen).
 
V

Vani_x

Mitglied
Das ist glaube ich alles zu hoch für mich. :(

Wie genau soll ich mir das überlegen? Ich muss ja alle Möglichkeiten durchgehen, aber das ist so kompliziert und kompakt.
 
H

httpdigest

Top Contributor
Du hast dir aber auch nun wirklich nicht die einfachste Rekursionsübung herausgesucht. :)
Immer weiter probieren, nachdenken und weiterprobieren.

Bedenke: Die Aufgabe eines Rekursionsaufrufes sollte es sein (meiner Meinung nach), die zwei Stellen im Array mit der aktuellen Zahl `k` zu belegen, rekursiv abzusteigen, und dann die Zahlen wieder zu löschen (das Löschen, damit mit den nächsten Stellen im Array weiterprobiert werden kann).
 
V

Vani_x

Mitglied
Hmm, danke dir! Ich versuchs einfach solange, bis ich am Stuhl einschlafe und morgen sage ich bescheid, ob ich es geschafft habe.
 
H

httpdigest

Top Contributor
Okay, und denke nicht zu kompliziert. Sobald deine rekursive Methode zuuu kompliziert aussieht, ist sie vermutlich falsch. :)
Die rekursive Methode kann man zumindest innerhalb von 9 Zeilen schreiben (also: jeweils gefundene Lösungen ausgeben und neue Lösungen generieren).
 
H

httpdigest

Top Contributor
Was ein Rekursionsaufruf machen (sollte):
1. Prüfen, ob wir schon fertig sind, also eine Lösung gefunden haben (`k == N-1`) und diese dann ausgeben
2. Sonst: Für alle möglichen Arraystellen prüfen, ob die für `k` zu setzenden zwei Stellen im Array noch frei sind, falls eine (neue) Stelle gefunden, dann:
2.1: Stellen mit `k` belegen
2.2: rekursiv absteigen mit k+1
2.3: Stellen im Array wieder löschen (auf 0 setzen)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Subset sum problem mit Backtracking Java Basics - Anfänger-Themen 18
O Backtracking Java Basics - Anfänger-Themen 5
C Rekursives Backtracking beim Spiel Peg Java Basics - Anfänger-Themen 22
A Backtracking Java Basics - Anfänger-Themen 56
R Backtracking Java Basics - Anfänger-Themen 1
V Feld sortieren mit Backtracking Java Basics - Anfänger-Themen 1
A Sudoku mit Backtracking lösen Java Basics - Anfänger-Themen 3
L Sudoku Backtracking Pseudocode Java Basics - Anfänger-Themen 3
N Backtracking - Labyrinth/Irrgarten Java Basics - Anfänger-Themen 14
I Backtracking Schach Java Basics - Anfänger-Themen 5
L Magisches Quadrat und Backtracking Java Basics - Anfänger-Themen 19
M Backtracking/Solve Methode Java Basics - Anfänger-Themen 7
P Labyrinth, Backtracking, verzögerte Anzeige Java Basics - Anfänger-Themen 15
D Sudoku lösen mit Backtracking Java Basics - Anfänger-Themen 20
E backtracking und Induktionsprinzip Java Basics - Anfänger-Themen 2
D Backtracking Waage Problem Java Basics - Anfänger-Themen 23
N Backtracking Solohalma Java Basics - Anfänger-Themen 2
W Backtracking und Frustration Java Basics - Anfänger-Themen 6
X Sudoku Backtracking Java Basics - Anfänger-Themen 6
J Solitaire via Backtracking Java Basics - Anfänger-Themen 7
A Backtracking - kennt Java keine Rücksprungmarken? Java Basics - Anfänger-Themen 15
G Backtracking mit globaler Variable Java Basics - Anfänger-Themen 5
M BackTracking Java Basics - Anfänger-Themen 22
J Backtracking Algorithmus Java Basics - Anfänger-Themen 16
L REKURSION Java Basics - Anfänger-Themen 13
Kirby.exe Rekursion Java Basics - Anfänger-Themen 7
N for Schleife durch Rekursion ersetzen Java Basics - Anfänger-Themen 6
X Rekursion Java Basics - Anfänger-Themen 3
H Rekursion Java Basics - Anfänger-Themen 2
D Erste Schritte Rekursion Java Basics - Anfänger-Themen 13
M Rekursion Tage Ansteckung gesamte Bevölkerung Java Basics - Anfänger-Themen 15
M Java Rekursion Java Basics - Anfänger-Themen 9
G Java Rekursion Java Basics - Anfänger-Themen 5
J Rekursion Klausur Aufgabe Java Basics - Anfänger-Themen 2
N Rekursion Java Basics - Anfänger-Themen 18
M Verständnisproblem der Rekursion bei Arrays Java Basics - Anfänger-Themen 8
X Rekursion Rätsel Java Basics - Anfänger-Themen 4
N Klassen Rekursion mit Feldern von Objekten Java Basics - Anfänger-Themen 14
W Rekursion Java Basics - Anfänger-Themen 0
D Konsolenausgabe Zahlenfolge Rekursion Java Basics - Anfänger-Themen 3
J Ping Pong Methode mit Rekursion Java Basics - Anfänger-Themen 1
N Rekursion Java Basics - Anfänger-Themen 1
B Rekursion Basic Java Basics - Anfänger-Themen 15
O Rekursion Mergesort Java Basics - Anfänger-Themen 18
G Rekursion Java Basics - Anfänger-Themen 20
M Rekursion Java Basics - Anfänger-Themen 7
F Hilfe bei Rekursion... Java Basics - Anfänger-Themen 4
A Mit Rekursion Zufallszahlen erstellen und größte finden Java Basics - Anfänger-Themen 5
B Rekursion Wurzel Java Basics - Anfänger-Themen 39
O Rekursion ordentlich aufschreiben Java Basics - Anfänger-Themen 2
B Rekursion verstehen Java Basics - Anfänger-Themen 4
O Rekursion Java Basics - Anfänger-Themen 2
E Rekursion verstehen. Java Basics - Anfänger-Themen 4
E Rekursion Kisten befüllen Java Basics - Anfänger-Themen 10
E Rekursion verstehen Java Basics - Anfänger-Themen 2
O Rekursion, String Java Basics - Anfänger-Themen 8
N Invertierte Rekursion??? Java Basics - Anfänger-Themen 5
M Bitte um Hilfe bei Quellcode (Rekursion) Java Basics - Anfänger-Themen 6
T Rekursion Warum bricht meine Funktion nicht ab Java Basics - Anfänger-Themen 4
A Hilfe bei Rekursion,Ich verstehe nicht,wie funktioniert die Rekursion in der Methode "walk" Java Basics - Anfänger-Themen 13
L Rekursion im Baum Java Basics - Anfänger-Themen 9
E Pfade eines Baums angeben ohne Rekursion Java Basics - Anfänger-Themen 20
L Rekursion Baumknoten Java Basics - Anfänger-Themen 8
L Rekursion größtes Zeichen Java Basics - Anfänger-Themen 8
L Rekursion Modulo Java Basics - Anfänger-Themen 7
I Rekursion Java Basics - Anfänger-Themen 11
H Rekursion Java Basics - Anfänger-Themen 7
N Methoden zur Rekursion (catalansche Zahlen) Java Basics - Anfänger-Themen 4
S Frage zu Rekursion... Java Basics - Anfänger-Themen 15
N Java catalansche Zahlen (Rekursion) Java Basics - Anfänger-Themen 5
S Noch eine Frage zur Rekursion... Java Basics - Anfänger-Themen 11
S Frage zu einer Rekursion Java Basics - Anfänger-Themen 15
F Methoden Abbruchbedingung bei Rekursion Java Basics - Anfänger-Themen 2
Z Rekursion Primzahlen Java Basics - Anfänger-Themen 1
K Rekursion Verständnisfrage Java Basics - Anfänger-Themen 19
L Methoden Rekursion gibt alten Wert wieder Java Basics - Anfänger-Themen 37
M Rekursion Minimums Suche Java Basics - Anfänger-Themen 12
J Rekursion Java Basics - Anfänger-Themen 5
F Aufgabe Rekursion Binärer Baum Java Basics - Anfänger-Themen 15
N Rekursion Java Basics - Anfänger-Themen 2
B Rekursion - Übung Java Basics - Anfänger-Themen 2
B Problem beim grundsätzlichen Verständnis bei Rekursion mit 2-dimensionalen Array Java Basics - Anfänger-Themen 6
P Rekursion Java Basics - Anfänger-Themen 19
G Rekursion Beispiel Java Basics - Anfänger-Themen 3
M Rekursion schreiben Java Basics - Anfänger-Themen 16
A Rekursion Funktion in eine Iterativ Funktion umwandeln Java Basics - Anfänger-Themen 8
T Array Rekursion Java Basics - Anfänger-Themen 1
B lineare und schlichte Rekursion Java Basics - Anfänger-Themen 1
A Rekursion Java Basics - Anfänger-Themen 2
B Rekursion Java Basics - Anfänger-Themen 3
A Rekursion stoppt an der falschen Stelle Java Basics - Anfänger-Themen 4
A Lineare Rekursion Java Basics - Anfänger-Themen 6
P Hilfe zur Rekursion? Java Basics - Anfänger-Themen 2
B Rekursion Schneeflocke - Kurze Frage zur Methode Java Basics - Anfänger-Themen 11
L Rekursion Java Basics - Anfänger-Themen 4
S Rekursion Rückgabe - Türme von Hanoi Java Basics - Anfänger-Themen 16
kilopack15 Rekursion und Schleifen Java Basics - Anfänger-Themen 27
E Rekursion Java Basics - Anfänger-Themen 10
JavaXava rekursion nicht verstanden Java Basics - Anfänger-Themen 5
K Rekursion-Verständnisfrage Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Anzeige

Neue Themen


Oben