Rekursiven Programmcode verändern

ClyonBlizz

Mitglied
Hallo, bin noch ein Programmier Anfänger und bräuchte bei dieser Aufgabenstellung ein bisschen Hilfe:

"Eine einfach verkette Liste ist eine dynamische Datenstruktur, welche eine im Vorhinein unbestimmte Anzahl an Elementen speichert. Jedes Element enthält dabei einen Zeiger auf das nächste Element (next), der Zeiger des letzten Elements zeigt auf den Wert null.

Folgende Knotendefinition können Sie für dieses Beispiel benutzen:
type Node = {
int value
Node next
}


Der folgende rekursive Algorithmus printReversed(↓Node n) gibt eine Liste (wobei n der Anfangsknoten ist) verkehrt herum aus.
printReversed(↓Node n) {
if(n != null) {
printReversed(↓n.next)
write(↓n.value)
} }


a) Bauen Sie den oben angegebenen Algorithmus printReversed(↓Node n) so um, dass nur die letzte Hälfte der Liste ausgegeben wird. Sollte die Länge der Liste ungerade sein, so soll das mittlere Element mitausgegeben werden. Führen Sie bei Bedarf einen Hilfsalgorithmus mit erweiterter Aufrufschnittstelle (mit Rückgabewert und/oder zusätzlichen Parametern) ein.
Es ist nicht erlaubt, die Listenelemente vor dem rekursiven Aufruf abzuzählen (die Länge der Liste kann also nicht als Parameter übergeben werden)."


Mein Ansatz wäre gewesen jedesmal vor Aufruf der Rekursion einen zähler einzubauen aber da dies nicht erlaubt habe ich keine Idee wie ich dieses Problem sonst lösen könnte; hätte wer von euch vielleicht einen Ansatz?
 

httpdigest

Top Contributor
Deine Rekursion hat ja zwei "Phasen": Abstieg und Aufstieg. Während des rekursiven Abstiegs zählst du einen Akkumulator hoch, den du als zusätzlichen Parameter einer neuen angesprochenen Hilfsmethode deklarierst. Also bei jedem Listenelement steigst du rekursiv weiter ab und zählst den Akkumulator (der Parameter dieser Methode ist) um eins hoch und rufst den nächsten Abstieg mit diesem neuen Wert auf.
Bei dem rekursiven Aufstieg, also wenn die Rekursionsabbruchbedingung (nächstes Listenelement ist null) das erste Mal eingetreten ist, lieferst du als Rückgabewert den finalen Akkumulatorwert zurück. Jetzt weiß jeder Aufstieg-Schritt, wieviele Elemente die Liste hatte und durch den aktuellen Akkumulatorwert in der jeweiligen Rekursionstiefe kann auch jeder Rekursionsschritt ermitteln, ob sie das jeweilige Listenelement noch ausgeben soll, oder nicht.

Du darfst natürlich einen Zähler benutzen. Gemeint ist nur, dass du nicht ganz vor der Rekursion überhaupt erst einmal die Listenlänge ermittelst.
 

ClyonBlizz

Mitglied
Deine Rekursion hat ja zwei "Phasen": Abstieg und Aufstieg. Während des rekursiven Abstiegs zählst du einen Akkumulator hoch, den du als zusätzlichen Parameter einer neuen angesprochenen Hilfsmethode deklarierst. Also bei jedem Listenelement steigst du rekursiv weiter ab und zählst den Akkumulator (der Parameter dieser Methode ist) um eins hoch und rufst den nächsten Abstieg mit diesem neuen Wert auf.
Bei dem rekursiven Aufstieg, also wenn die Rekursionsabbruchbedingung (nächstes Listenelement ist null) das erste Mal eingetreten ist, lieferst du als Rückgabewert den finalen Akkumulatorwert zurück. Jetzt weiß jeder Aufstieg-Schritt, wieviele Elemente die Liste hatte und durch den aktuellen Akkumulatorwert in der jeweiligen Rekursionstiefe kann auch jeder Rekursionsschritt ermitteln, ob sie das jeweilige Listenelement noch ausgeben soll, oder nicht.

Du darfst natürlich einen Zähler benutzen. Gemeint ist nur, dass du nicht ganz vor der Rekursion überhaupt erst einmal die Listenlänge ermittelst.

Danke für deine Anwtort,
Soll ich also bei dem schon angegebenen Algorithmus einen zusätzlichen Parameter(Akkumulatorwert) und einen Rückgabewert(Endergebnis des Akkumulatorwert) hinzufügen?
 

httpdigest

Top Contributor
Ja. Und, da die ursprüngliche Signatur der Methode ja nicht geändert werden sollte (gehe ich mal sehr stark von aus), musst du die vorhandene Methode einfach umbenennen (und z.B: private machen) und diese dann von der eigentlichen Methode aus aufrufen. Mit einem sinnvollen Startwert für den Akkumulator-Parameter, versteht sich.
 

ClyonBlizz

Mitglied
Ja. Und, da die ursprüngliche Signatur der Methode ja nicht geändert werden sollte (gehe ich mal sehr stark von aus), musst du die vorhandene Methode einfach umbenennen (und z.B: private machen) und diese dann von der eigentlichen Methode aus aufrufen. Mit einem sinnvollen Startwert für den Akkumulator-Parameter, versteht sich.

aber schlussendlich muss ich doch dort auch wieder bei der Methode printReversed die Listenlänge als Parameter übergeben weil ich sonst nicht den Akku erhöhen kann;
 

Blender3D

Top Contributor
printReversed die Listenlänge als Parameter
Muss Du nicht!
So z.B.
Java:
public class Node {
    int value = 0;
    Node next = null;
    public Node(int value) {
        this.value = value;
    }
}


Java:
    int[] data = { 1, 2, 3, 4, 5 };
        MyList list = new MyList();
        for (int i : data)
            list.add(i);
        list.printReversed();

Java:
public class MyList {
    private Node start = null;
    private int cnt = 0;
    private int size = 0;

    public void add(int value) {
        if (start == null) {
            start = new Node(value);
            return;
        }
        Node it = start;
        while (it.next != null)
            it = it.next;
        it.next = new Node(value);
    }

    public void printReversed() {
        size = 0;
        cnt = -1;
        printReversed(start);
    }

    private void printReversed(Node n) {
        if (n != null) {
            size++;
            printReversed(n.next);
            if (cnt == -1)
                cnt = size / 2;
            else if (cnt > 0)
                cnt--;
            if (cnt == 0)
                System.out.println(n.value);
        }
    }
}
;)
 

httpdigest

Top Contributor
Okay, wir schreiben also leider schon konkrete Codelösungen hier hin.
Ich dem Fall hatte ich eher sowas im Sinn (Lösung aus dem Kopf, habe es nicht getestet):
Java:
private int printReversedHelper(Node n, int acc) {
  if (n != null) {
    int size = printReversedHelper(n.next, acc+1);
    if (acc >= size / 2)
      write(n.value);
    return size;
  }
  return acc;
}
public void printReversed(Node n) {
  printReversedHelper(n, 0);
}
Die Originalmethode wird also nur ein bisschen erweitert und wird zur Hilfsmethode. Die neue Originalmethode ruft einfach nur die Hilfsmethode auf.
 
Zuletzt bearbeitet:

Blender3D

Top Contributor
:)
Ich bezweifle, dass Feld statt Parameter eine erlaubte Lösung ist

a) Bauen Sie den oben angegebenen Algorithmus printReversed(↓Node n) so um, dass nur die letzte Hälfte der Liste ausgegeben wird. Sollte die Länge der Liste ungerade sein, so soll das mittlere Element mitausgegeben werden. Führen Sie bei Bedarf einen Hilfsalgorithmus mit erweiterter Aufrufschnittstelle (mit Rückgabewert und/oder zusätzlichen Parametern) ein.
Es ist nicht erlaubt, die Listenelemente vor dem rekursiven Aufruf abzuzählen (die Länge der Liste kann also nicht als Parameter übergeben werden)."
Also erlaubt ist nicht vorher abzuzählen. -->
Andere Signatur oder Feld statt Parameter erlaubt. ;) Des weiteren geht es hier nicht um die gute Lösung, sondern um eine gangbare.

schlussendlich muss ich doch dort auch wieder bei der Methode printReversed die Listenlänge als Parameter übergeben
Die Lösung soll nur aufzeigen, dass es hier kein muss für Parameter gibt. Wobei die Parameterlösung sicher die bessere ist.
 

mrBrown

Super-Moderator
Mitarbeiter
Also erlaubt ist nicht vorher abzuzählen. -->
Andere Signatur oder Feld statt Parameter erlaubt. ;) Des weiteren geht es hier nicht um die gute Lösung, sondern um eine gangbare.

Ich bezog mich auf die offensichtlichen Zweifel des TO, ob Länge als Parameter erlaubt ist, worauf du ja auch geantwortet hast. Wenn Parameter nicht erlaubt wäre (was der TO in seiner Antwort implizit meinte), wäre Feld ganz sicher nicht erlaubt ;)
Ich kann nur für mich sprechen, aber in meinem Kurs würde man für das Feld keine Punkte bekommen, für Parameter aber schon ;) Das es in der Aufgabenstellung keinen Listen-Typ (geschweige denn Klasse) gibt, ist nur ein Grund dafür...
 

Blender3D

Top Contributor
Ich kann nur für mich sprechen, aber in meinem Kurs würde man für das Feld keine Punkte bekommen, für Parameter aber schon
Stimmt würde ich auch keine Punkte dafür geben. Vorausgesetzt die Aufgabe verbietet es. Was ja hier offensichtlich nicht der Fall ist.
Pädagogisch spricht nichts dagegen dem Schüler eine nicht so gute Lösung finden zu lassen, wenn man bei der Besprechung der Aufgaben die Nachteile erläutert. Hat dann oft den Besseren Lerneffekt.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
berserkerdq2 Wo geschieht der "Rücksprung, bei der rekursiven Folge Java Basics - Anfänger-Themen 5
H Den Wert einer rekursiven Funktion bestimmen Java Basics - Anfänger-Themen 5
R Implementieren einer iterativen und rekursiven Klassenmethode. Java Basics - Anfänger-Themen 1
B Hilfe bei einer rekursiven Methode Java Basics - Anfänger-Themen 3
S Rekursiven Stack Java Basics - Anfänger-Themen 6
I Labyrinth auf der Basis eines rekursiven Algorithmus Java Basics - Anfänger-Themen 27
MiMa abbruch innerhalb einer Rekursiven Schleife Java Basics - Anfänger-Themen 5
S Hilfe bei Fehlerfindung einer rekursiven Methode Java Basics - Anfänger-Themen 2
X Probleme beim rekursiven Durchsuchen von Verzeichnissen Java Basics - Anfänger-Themen 1
L Mit rekursiven Aufrufen einen Stack emulieren Java Basics - Anfänger-Themen 1
D Methode mit mehren Rekursiven aufrufen in Methode mit einem Rekursiven Aufruf umwandeln! Java Basics - Anfänger-Themen 1
B JavaKara rekursiven Teppich erstellen??? Java Basics - Anfänger-Themen 5
S Frage zu einer rekursiven Funktion Java Basics - Anfänger-Themen 28
timbeau Endergebnis einer rekursiven Methode Java Basics - Anfänger-Themen 11
G List als Rückgabewert einer rekursiven Methode (Baum) Java Basics - Anfänger-Themen 3
E Mehrfache print ausgabe ohne Schleife oder Rekursiven aufruf? Java Basics - Anfänger-Themen 48
D Problem bei einer Rekursiven Methode Java Basics - Anfänger-Themen 2
A Beschränkung der Anzahl der rekursiven Aufrufe einer Methode Java Basics - Anfänger-Themen 4
H Scripte oder Programmcode aus Datei lesen? Java Basics - Anfänger-Themen 5
J Wo ist der Fehler im Programmcode? Java Basics - Anfänger-Themen 7
S Programmcode verstehen Java Basics - Anfänger-Themen 4
T Best Practice Beurteilung Programmcode Java Basics - Anfänger-Themen 17
S Erste Schritte BlueJ-Aufgabe: Programmcode / Brauche dringend Hilfe !!! Java Basics - Anfänger-Themen 37
D Datentypen Bild in Programmcode integrieren Java Basics - Anfänger-Themen 17
W Programmcode Eulersche Zahl Java Basics - Anfänger-Themen 2
U Frage zu IO programmcode Java Basics - Anfänger-Themen 7
B Programmcode von replace, split, u.s.w. Java Basics - Anfänger-Themen 3
JavaBeginner22 Button Text verändern Java Basics - Anfänger-Themen 1
milan123 das ist meine aufgabe ich hab das problem das bei mir Wenn ich die Richtung der Linien verändern will und drei davon sind richtig, verändere ich die 4 Java Basics - Anfänger-Themen 3
H OOP Werte mit Set verändern Java Basics - Anfänger-Themen 6
M Was muss ich verändern damit ich es so ausgegeben bekomme wie auf dem Foto? Java Basics - Anfänger-Themen 2
A Haben KNNs ein Gedächtnis, lernen etwas oder verändern sich, während sie nicht trainieren, aber aktiv sind? Java Basics - Anfänger-Themen 3
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
A Variablen zum final verändern Java Basics - Anfänger-Themen 4
A Kann man eine Methode als Variable speichern und danach noch verändern? Java Basics - Anfänger-Themen 6
S Verändern der Liniendicke Java Basics - Anfänger-Themen 5
V Vererbung Subklasse soll Superklasse verändern Java Basics - Anfänger-Themen 2
S werte von objekten in schleife verändern Java Basics - Anfänger-Themen 14
N Sicherheitsnummer erstellen und verändern können Java Basics - Anfänger-Themen 1
A JLabel mit button drücken verändern Java Basics - Anfänger-Themen 6
J Wert bei Objekterzeugung verändern Java Basics - Anfänger-Themen 12
J Die Y Koordinate von einer anderen Klasse auch verändern Java Basics - Anfänger-Themen 1
L JTable Tagebuch Spaltenhöhe verändern Java Basics - Anfänger-Themen 3
M Listener für Button - Wert von Variablen verändern Java Basics - Anfänger-Themen 14
D Mit Buttonklick Farbe der anderen Buttons verändern? Java Basics - Anfänger-Themen 2
G Im ActionListener eine "äußere" Variable verändern Java Basics - Anfänger-Themen 13
E RTF/DOC(x) textteile ersetzen/verändern Java Basics - Anfänger-Themen 0
W aus Methode auf JLabel zugreifen und Image verändern Java Basics - Anfänger-Themen 1
W JLabel in Main aus Thread verändern. Java Basics - Anfänger-Themen 4
I For Schleife - Variable verändern Java Basics - Anfänger-Themen 4
C Im Array zählen und verändern Java Basics - Anfänger-Themen 5
C Finden und verändern Java Basics - Anfänger-Themen 1
J Erste Schritte String verändern Java Basics - Anfänger-Themen 3
S Rollen verändern, Interfaces austauschen wie? Java Basics - Anfänger-Themen 10
M Von einer Klasse aus, Objekte einer anderen Klasse verändern. Java Basics - Anfänger-Themen 2
Streeber Jar dekompilieren, Code verändern und als .jar speichern Java Basics - Anfänger-Themen 5
K Windows Kontextmenü verändern Java Basics - Anfänger-Themen 5
M Zahlen verändern nach Zeit Java Basics - Anfänger-Themen 6
TheSorm Obercalsse von Unterclasse verändern Java Basics - Anfänger-Themen 3
C Input/Output Hilfe..txt Datei zeile verändern und Ausgabe ..Hilfe Java Basics - Anfänger-Themen 11
L Platz auf JButtons verändern Java Basics - Anfänger-Themen 18
O Bereits "gepostete" Strings in der Konsole verändern? Java Basics - Anfänger-Themen 2
G über JButton Action einen anderen Button verändern Java Basics - Anfänger-Themen 7
J Android R.Java verändern!? Java Basics - Anfänger-Themen 6
M Felder mit Methode verändern Java Basics - Anfänger-Themen 11
I Shortcut verändern Java Basics - Anfänger-Themen 9
P GUI - Layout per Laufzeit erstellen/verändern? Java Basics - Anfänger-Themen 6
S String verändern Java Basics - Anfänger-Themen 15
I Im JFrame Inhalte verändern per Methode aus anderer Class Java Basics - Anfänger-Themen 5
K In ArrayList Daten verändern Java Basics - Anfänger-Themen 8
M Klassen Durch den ActionListener das GUI einer anderen Klasse verändern Java Basics - Anfänger-Themen 8
J Collections Auf ein bestimmtes Objekt in der Liste zugreifen und Werte verändern + Anschließend Sortieren... Java Basics - Anfänger-Themen 8
F Klassenübergreifend String verändern Java Basics - Anfänger-Themen 5
R Benutzeroberfläche verändern Java Basics - Anfänger-Themen 4
H BufferedImage DPI verändern Java Basics - Anfänger-Themen 5
J Mit JS, Text und Bilder von Webseite verändern... Java Basics - Anfänger-Themen 10
X Collections Reihenfolge bestimmter Objekte in einer ArrayList verändern Java Basics - Anfänger-Themen 2
B ComboBox(editable) - Text verändern Java Basics - Anfänger-Themen 7
S String dauerhaft mit replaceAll verändern Java Basics - Anfänger-Themen 3
V "TAB" komplett verändern Java Basics - Anfänger-Themen 10
Z Anzahl der Stellen nach dem Komma verändern. Java Basics - Anfänger-Themen 7
C ComboBoxModel mit Daten der Datenbank verändern Java Basics - Anfänger-Themen 2
C jPanel im jPanel verändern Java Basics - Anfänger-Themen 15
B JPanel nachträglich verändern Java Basics - Anfänger-Themen 20
StrikeTom *.txt-datei verändern|wie? Java Basics - Anfänger-Themen 5
S Eigenes Objekt temporär verändern? (Clone)? Java Basics - Anfänger-Themen 12
E Breite des Schiebers in JscrollPane verändern Java Basics - Anfänger-Themen 2
J Ausgelesenen Dateipfad verändern Java Basics - Anfänger-Themen 5
B Ausgabe verändern Java Basics - Anfänger-Themen 6
L Methode über for-schleife aufrufen und verändern Java Basics - Anfänger-Themen 7
L Methode über for-schleife aufrufen und verändern Java Basics - Anfänger-Themen 5
R Textdatei im Internet verändern... Java Basics - Anfänger-Themen 4
B Hintergrundfarbe laufend verändern Java Basics - Anfänger-Themen 14
B Collection während Iteration verändern Java Basics - Anfänger-Themen 7
D .class-Datei innerhalb einer .jar-Datei verändern Java Basics - Anfänger-Themen 4
F Verändern einer Variable im ActionListener Java Basics - Anfänger-Themen 14
A Von einer Klasse aus die Eingabe einer anderen verändern Java Basics - Anfänger-Themen 3
D kleine Passwortabfrage erstellen incl. Method zum verändern Java Basics - Anfänger-Themen 7
G Variable welche in anderer Klasse liegt, verändern. Java Basics - Anfänger-Themen 2
M Text in Konsole schreiben, den man irgendwie verändern kann. Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben