Rekursiven Programmcode verändern

[ClyonBlizz]

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]

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]

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]

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]

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]

printReversed die Listenlänge als Parameter

Muss Du nicht!
So z.B.

public class Node {
    int value = 0;
    Node next = null;
    public Node(int value) {
        this.value = value;
    }
}

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

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

 

[mrBrown]

Muss Du nicht!
So z.B.

Ich bezweifle, dass Feld statt Parameter eine erlaubte Lösung ist (vor allem ist rekursiv in Verbindung mit veränderlichen Feldern immer irgendwie schlecht... :/)

 

[httpdigest]

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

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.

 

[Blender3D]

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.

 

[Blender3D]

Bauen Sie den oben angegebenen Algorithmus printReversed(↓Node n) so um,

Die Originalmethode wird also nur ein bisschen erweitert und wird zur Hilfsmethode

Das ist ja laut Angabe kein Problem.

 

[mrBrown]

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]

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.