Pfade eines Baums angeben ohne Rekursion

ernst

Top Contributor
Hallo allerseits,
gegeben sei ein Baum.
Realisiert wird dies dadurch, dass in jedem Noten ein Verweis für jeden Nachfolgeknoten enthalten ist.
Dies kann man durch eine entsprechende, selbstgebastelte Klasse (Datenstruktur) realisieren.
(ich will keine vorgefertigte Klasse aus der Entwicklungsumgebung).
Wenn man in dem Baum alle Pfade (von der Wurzel an alle Blätter) durchlaufen will, so kann man das wie folgt ohne Rekursion, rein iterativ machen (grob beschrieben):
Gehe zum nächsten freien Knoten.
"Markiere" ihn.
Wenn man an einem Blatt angekommen ist, wird es markiert, dann geht man zum Vorgängerknoten und dort zum nächsten freien Blatt (das man markiert)
Das macht man so lange, bis alle Knoten des Baums markiert sind.
Bemerkung (zur Markierung):
Ein Knoten zeigt auf allen Nachfolgeknoten. Deshalb kann ein Knoten so viele Markierungen haben, wie er Nachfolgeknoten hat.
Allerdings muss man dann die Datenstruktur des Baums abändern, die der Programmierer des Baums gemacht hat.

D.h. ich muss die Datenstruktur des Baums durch die Hinzunahme (Implementierung) der Markierungen verändern.

Frage:
Kann man das auch machen, ohne die vorgegebene Datenstruktur eines Knotens abzuändern ?

mfg
ern
 

httpdigest

Top Contributor
Definiere bitte mal ganz genau, was du in deiner Beschreibung unter einem "Vorgängerknoten" und "Nachfolgerknoten" ganz genau verstehst. Eine Baumstruktur wird ja üblicherweise so definiert, dass jeder Knoten Referenzen auf seine "Kindknoten" besitzt. Meinst du mit Nachfolgeknoten die Kinder eines Knotens oder was anderes, wie etwa, den nächsten Knoten, den eine pre-order, in-order oder post-order Traversierung üblicherweise als nächstes besuchen würde?
Siehe hierzu auch: https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)
 

ernst

Top Contributor
Definiere bitte mal ganz genau, was du in deiner Beschreibung unter einem "Vorgängerknoten" und "Nachfolgerknoten" ganz genau verstehst. Eine Baumstruktur wird ja üblicherweise so definiert, dass jeder Knoten Referenzen auf seine "Kindknoten" besitzt. Meinst du mit Nachfolgeknoten die Kinder eines Knotens oder was anderes, wie etwa, den nächsten Knoten, den eine pre-order, in-order oder post-order Traversierung üblicherweise als nächstes besuchen würde?
Siehe hierzu auch: https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)
Nachfolgerknoten = Kinder

mfg
ern
 

httpdigest

Top Contributor
Okay. Desweiteren geht aus deiner Ausführung im ersten Post nicht hervor, was denn jetzt eigentlich die Aufgabe ist. Du schreibst, was man machen könnte mit Markieren und so weiter. Aber was soll denn die Aufgabe genau sein?
Meine Vermutung ist, dass deine Aufgabe/Frage lautet: "Wie kann man eine Baumstruktur ohne Rekursion traversieren?"
Und die Antwort darauf wäre: Benutze eine Iteration mit einer Stack-Datenstruktur.
Die Möglichkeiten, die du durch Rekursion gewinnst, können immer iterativ mit Hilfe eines Stacks nachgebildet werden. Letztlich ist Rekursion ja auch nichts anderes als ein Stack (nämlich der Callstack / Stack Frames der Methodenaufrufe).
 

ernst

Top Contributor
Und die Antwort darauf wäre: Benutze eine Iteration mit einer Stack-Datenstruktur.
Die Möglichkeiten, die du durch Rekursion gewinnst, können immer iterativ mit Hilfe eines Stacks nachgebildet werden. Letztlich ist Rekursion ja auch nichts anderes als ein Stack (nämlich der Callstack / Stack Frames der Methodenaufrufe).
Vielen Dank für deine Antwort.
Stack-Prinzip: last in - first out.
Gibt es dazu eine andere Alternative (wie bei meiner Lösung mit den Markierungen) ?

mfg
ern
 

httpdigest

Top Contributor
Alleine zum Markieren benötigst du ja schon einen Stack, um das Markieren alleine nicht-rekursiv zu tun.
Oder wie würdest du die Knoten markieren (und wieso überhaupt), ohne Rekursion.
Letztlich ist das Markieren ja auch einfach nur das Traversieren des Baumes. Und, wenn du das tust, hast du den Baum ja schon traversiert, und somit wärest du dann ja auch schon fertig.
 

ernst

Top Contributor
Alleine zum Markieren benötigst du ja schon einen Stack, um das Markieren alleine nicht-rekursiv zu tun. Oder wie würdest du die Knoten markieren
Indem man dafür in jedem Knoten des Baums zusätzlich - nur fürs Markieren - einen Speicher reserviert. Das ist aber umständlich. Deswegen halte ich das für eine schlechte Lösung.

(und wieso überhaupt), ohne Rekursion.
zur Übung

Letztlich ist das Markieren ja auch einfach nur das Traversieren des Baumes. Und, wenn du das tust, hast du den Baum ja schon traversiert, und somit wärest du dann ja auch schon fertig.
Ich glaube jetzt zu wissen, was du meinst:
markieren heißt bei dir die traversierten Knoten in einem Stack speichern.
Ich werde das mal ausprobieren.
Vielen Dank.

mfg
ern
 

fhoffmann

Top Contributor
Du benötigst keine Markierungen. Die Idee ist folgende
Code:
- erzeuge eine (leere) Liste von Knoten
- füge die Wurzel des Baumes in die Liste ein
- solange die Liste nicht leer ist
     - entnehme der Liste einen Knoten (den ersten oder letzten)
     - bearbeite diesen Knoten
     - füge alle Kinder des Knotens in die Liste ein
 

ernst

Top Contributor
Du benötigst keine Markierungen. Die Idee ist folgende
Code:
- erzeuge eine (leere) Liste von Knoten
- füge die Wurzel des Baumes in die Liste ein
- solange die Liste nicht leer ist
     - entnehme der Liste einen Knoten (den ersten oder letzten)
     - bearbeite diesen Knoten
     - füge alle Kinder des Knotens in die Liste ein
Danke für diese Info.
Mein Algorithmus war so, dass man den Baum traversiert und dabei die schon besuchten Knoten in einer Knoten_Liste abspeichert.
Der Baum wird dann solange traversiert, bis bis es keinen unbesuchten Knoten mehr gibt.
Nachteil: Es muss immer geprüft werden, ob ein neuer zu besuchender Knoten schon in der Knoten_Liste vorkommt.

konkreter:
aktueller Knoten = Wurzel
so lange nicht alle Knoten markiert sind, mache folgendes:
1)
wenn aktueller Knoten unmarkiert, markiere ihn
2)
Fall: aktueller Knoten ist ein Blatt:
setze aktueller Knoten = Elternknoten
Fall: aktueller Knoten ist kein Blatt:
Falls es ein unmarkiertes Kind gibt:
setze aktueller Knoten = ein noch unmarkiertes Kind
Falls es kein unmarkiertes Kind gibt (alle Kindknten markiert):
setze aktueller Knoten = Elternknoten

Die markierten Knoten werden alle in einer Knoten_Liste gespeichert.
Wäre das nicht auch ein möglicher Algorithmus?
Nachteil: schlechtere Laufzeit, da für jeden Knoten die Knoten_Liste durchsucht werden muss (um zu prüfen, ob der Knoten schon markiert ist).

mfg
ern
 

mrBrown

Super-Moderator
Mitarbeiter
Deine Variante setzt voraus, dass jeder Knoten sowohl Kind- als auch Elternknoten kennt, sonst ist das nur rekursiv umsetzbar.
 

ernst

Top Contributor
Deine Variante setzt voraus, dass jeder Knoten sowohl Kind- als auch Elternknoten kennt, sonst ist das nur rekursiv umsetzbar.
Ok.
1)
Wie verhält es sich mit der Laufzeit (im Vergleich zu der Löungsidee mit dem Stack)?

2)
Wie kommt man auf die Lösungsidee mit dem Stack?
Gibt es intuitive Merkhilfen, wann man Lösungsideen mit dem Stack verwenden kann?

mfg
ern
 

mrBrown

Super-Moderator
Mitarbeiter
1) das hängt hauptsächlich vom Markieren ab. Mit geeigneten Datenstrukturen dürfte das die gleiche Laufzeit haben.

2) man kann Rekursion immer in einem Iteration mit Stack umformen. Wenn also ein rekursive Algorithmus naheliegt (zB bei Rekursiven Datenstrukturen), liegt da auch eine Variante mit Stack nahe
 

ernst

Top Contributor
Die Möglichkeiten, die du durch Rekursion gewinnst, können immer iterativ mit Hilfe eines Stacks nachgebildet werden. Letztlich ist Rekursion ja auch nichts anderes als ein Stack (nämlich der Callstack / Stack Frames der Methodenaufrufe).
Mir ist leider nicht klar, wie man (algorithmisch, kochrezeptmäßig) vorgehen muss, um eine Rekursion als Iteration nachzubilden, indem man den Stack simuliert.
Beispiel (Fibonacci-Folge 1,2,3,5,8, ...):
Code:
fib(int n) {
  int erg;
  if(n==0)
    erg=1;
  else if(n==1)
    erg=2;
  else
    erg = fib(n-1) + fib(n-2);
  return erg;
}
Wie bildet man da den Stack nach und bekommt eine Iteration ?

mfg
ern
 

mrBrown

Super-Moderator
Mitarbeiter
Fibonacci ist zwar ein schlechtes Beispiel, aber generell geht das, indem man dir rekursiven Funktionsaufrufe ersetzt, in dem man das entsprechende auf den Stack legt

Bei Fibonacci wäre das jeder Aufruf von fib, stattdessen legt man dann das n auf den Stack.
Solange dann noch etwas auf dem Stack liegt, nimmt man das oberste als n runter.
- ist es 0 oder 1 (gibt es also keine weitere Rekursion), addiert man diese auf
- ansonsten legt man n-1 und n-2 auf den Stack

(btw, dein Algorithmus liefert falsche Werte, 0 wäre 0 und 1 wäre 1)
 

httpdigest

Top Contributor
Der allgemeinste Algorithmus, um aus einer ganz beliebigen Rekursion mit beliebig vielen rekursiven Teilaufrufen (wie bei Fibonacci) eine Iteration zu machen, besteht daraus, den darunterliegenden Prozessor/Maschine (oder virtuelle Maschine im Java-Fall) zu emulieren:
- rekursive Aufrufe, die letztlich einen Stackframe erzeugen würden, müssen mit ihren Argumenten auf eine eigene Stack-Datenstruktur gepackt werden
- das Abarbeiten aller rekursiven Aufrufes muss iterativ in einer Schleife passieren, indem über die in dem Stack aktuell gespeicherten rekursiven Aufrufe iteriert wird
- bei jedem rekursiven Aufruf im Stack muss dessen "Zustand" gemerkt und fortgeschrieben werden (das heißt im Endeffekt: Merken des Program Counters der Methode)
- die Zustände ergeben sich im feinsten Fall aus jeder einzelnen Zeile der Methode, aber können gröber gehalten werden. Im Allgemeinen aber muss die Methode einen separaten Program Counter Wert für jeden rekursiven Teilaufruf haben, um diesen erkennen und ausführen (sprich: auf den Stack packen) zu können

Das Verfahren ist am allgemeinsten, liefert dir aber auch das schlechteste Ergebnis (was Performance und Lesbarkeit angeht - es emuliert ja letztlich die Maschine). Für Fibonacci habe ich das mal untenstehend umgesetzt:
Java:
static int fibIt(int n) {
  class Call {
    int arg; // <- argument
    int ret; // <- return value
    int pc; // <- program counter
    Call parent; // <- parent call (emulate storing ECX register and performing RET)
    int callsite; // <- which callsite in the parent does this call belong to
    int[] partials = new int[2]; // <- partial results for recursive calls
    Call(int n, int callsite, Call parent) {
      this.arg = n;
      this.callsite = callsite;
      this.parent = parent;
    }
    void returns(int ret) {
      this.ret = ret;
      if (parent != null)
        parent.partials[callsite] = ret;
    }
  }
  Stack<Call> calls = new Stack<>();
  Call top = new Call(n, 0, null);
  calls.add(top);
  while (!calls.isEmpty()) {
    Call current = calls.pop();
    switch (current.pc) {
    case 0:
      // First case: All non-recursive steps
      if (current.arg == 0) {
        current.returns(0);
        continue;
      } else if (current.arg == 1) {
        current.returns(1);
        continue;
      }
      current.pc = 1;
    case 1:
      // Second case: First recursive call
      current.pc = 2;
      calls.push(current);
      calls.push(new Call(current.arg - 1, 0, current));
      break;
    case 2:
      // Third case: Second recursive call
      current.pc = 3;
      calls.push(current);
      calls.push(new Call(current.arg - 2, 1, current));
      break;
    case 3:
      // Fourth case: Both recursive calls returned
      // Collect both callsite return values
      current.returns(current.partials[0] + current.partials[1]);
      break;
    }
  }
  return top.ret;
}
 

httpdigest

Top Contributor
Eine noch hardwarenähere Lösung (zum Vermeiden von "callsite" und "parent" und "partials" etc.):
Java:
static int fibIt(int n) {
  class Call {
    int arg; // <- Argument des Aufrufes
    int pc; // <- Programmzähler (aktueller Zustand der Methodenausführung)
    int mem; // <- Reservierter Stackspeicher für Zwischenergebnisse
    Call(int n) { this.arg = n; }
  }
  class Registers {
    int eax; // <- wir tun mal so, als wäre das hier x86
  }
  Registers r = new Registers();
  Stack<Call> calls = new Stack<>();
  calls.add(new Call(n));
  // Solange wie es noch aktive Aufrufe gibt...
  while (!calls.isEmpty()) {
    // Hole den aktuell zu verarbeitenden Aufruf
    Call current = calls.pop();
    // In Abhängigkeit vom aktuellen Ausführungszustand...
    switch (current.pc) {
    case 0:
      // verarbeite die nicht-rekursiven Anweisungen am Anfang
      if (current.arg == 0) {
        // setze Rückgabewert für diesen Aufruf
        r.eax = 0;
      } else if (current.arg == 1) {
        // setze Rückgabewert für diesen Aufruf
        r.eax = 1;
      } else {
        // setzen den Ausführungszustand weiter
        current.pc = 1;
        calls.push(current);
      }
      break;
    case 1:
      // verarbeite den ersten rekursiven Teilaufruf
      current.pc = 2;
      calls.push(current);
      // "rufe" die erste Teilrekursion auf
      calls.push(new Call(current.arg - 1));
      break;
    case 2:
      // erster rekursiver Teilaufruf ist zurückgekehrt
      // speichere den Rückgabewert davon zwischen
      current.mem = r.eax;
      // und setze den Ausführungszustand weiter
      current.pc = 3;
      calls.push(current);
      // "rufe" die zweite Teilrekursion auf
      calls.push(new Call(current.arg - 2));
      break;
    case 3:
      // zweiter rekursiver Teilaufruf ist zurückgekehrt
      // setze Rückgabewert für diesen Aufruf
      r.eax = current.mem + r.eax;
      break;
    }
  }
  return r.eax;
}
 
Zuletzt bearbeitet:

ernst

Top Contributor
Halo httpdigest,
1)
Danke für die 2 Lösungen.
Momentan reichen leider meine intellektuellen Fähigkeiten noch nicht aus, dies genau zu verstehen, obwohl ich weiss, wie ein Stack funktioniert.
Ich werde mir das noch genauer ansehen.

2)
Eine andere Möglichkeit, eine Rekursion zu simulieren ist Folgende:
Jede Rekursion ist Spezialfall einer induktiv definierten Menge.
Eine induktiv definierte Menge wird durch Regeln erzeugt.
Aus einer Anfangsmenge D0 werden mit Hilfe der Regeln R die Menge D1 erzeugt, usw. Kurz:
D0 --R--> D1 --R--> D2 ....
Die Vereinigung all dieser Mengen ist die induktiv definierte Menge.
Die einzelnen Mengen kann man mit einer Iteration erzeugen.
Was meinst du dazu ?

mfg
ern
 

httpdigest

Top Contributor
Du wanderst jetzt aber sehr weit in die theoretische Informatik bzw. Mathematik ab und viel von dir geschriebenes hat keinen praktischen Bezug mehr mit dem Programmiersprachenkonstrukt "Rekursion".

Natürlich kann man auch eine bijektive Abbildung zwischen zwei (oder denselben) Mengen über eine rekursive Funktion definieren, also etwa:

f(0) = 1
f(N) = f(N-1) + 1

Das wäre ja quasi die "Nachfolgerfunktion" auf den natürlichen Zahlen.
Aber das hat nun rein garnichts mehr mit "Rekursion simulieren/emulieren" oder auch Rekursion als Iteration in einer Programmiersprache ausdrücken zu tun.

Es wäre sicherlich von Vorteil, wenn du deine ganzen theoretischen Überlegungen (deren Zweck ich langsam nicht mehr sehe), auch in Programmcode gießen könntest. Oder zumindest, wenn du einmal das tatsächlich zu lösende Problem beschreiben könntest, ohne in wilde theoretische Diskussionen auszuarten.
 

ernst

Top Contributor
Der allgemeinste Algorithmus, um aus einer ganz beliebigen Rekursion mit beliebig vielen rekursiven Teilaufrufen (wie bei Fibonacci) eine Iteration zu machen, besteht daraus, den darunterliegenden Prozessor/Maschine (oder virtuelle Maschine im Java-Fall) zu emulieren:
...
while (!calls.isEmpty()) {
Call current = calls.pop();
}
Habe mir nochmals deine Lösung angeschaut, die natürlich korrekt ist und an der ich nichts auszusetzen habe.
Aber in deiner while-Schleife kommt am Anfang immer eine pop-Anweisung.
Wenn ich mir aber eine einfache Rekursionsfunktion schreibe (z.B. in C, wo ich dann den Assembler-Code anschauen kann), wie z.B:
f(n) = f(n-1) + 10 für n>1
und
f(1) = 100
dann wird bei Berechnung von z.B. f(5) hintereinander zerst mehrfach hintereinander push-Anweisungen durchgeführt, bis dann am Schluss mehrfach hintereinander pop-Befehle durchgeführt werden.
(Zumindest meine ich mich an das noch erinnern zu können).
D.h. deine Lösungsidee ist nicht eine genaue Simulation dieser Rekursion.
Ich will damit deine Lösung nicht schlechtreden.
Mir geht es nur darum, ob ich in meiner gerade geschilderten Überlegung keinen Denkfehler habe.
Was meinst du dazu ?

mfg
ern
 

httpdigest

Top Contributor
Du hast Recht, wenn man ganz pedantisch sein möchte, dann würde man es wohl eher so machen:
Java:
static int fibIt(int n) {
  class Call {
    int arg, pc, mem;
    Call(int n, int pc) {
      this.arg = n;
      this.pc = pc;
    }
  }
  class Registers {
    int eax, ecx, pc;
  }
  Registers reg = new Registers();
  Stack<Call> calls = new Stack<>();
  calls.add(new Call(n, 0));
  class InsnSet {
    void ret() {
      Call current = calls.pop();
      reg.pc = current.pc;
    }
    void call() {
      calls.push(new Call(reg.ecx, reg.pc + 1));
      reg.pc = 0;
    }
  }
  InsnSet is = new InsnSet();
  while (!calls.isEmpty()) {
    Call current = calls.peek();
    switch (reg.pc) {
    case 0:
      if (current.arg == 0) {
        reg.eax = 0;
        is.ret();
      } else if (current.arg == 1) {
        reg.eax = 1;
        is.ret();
      } else {
        reg.pc = 1;
      }
      break;
    case 1:
      reg.ecx = current.arg - 1;
      is.call();
      break;
    case 2:
      current.mem = reg.eax;
      reg.ecx = current.arg - 2;
      is.call();
      break;
    case 3:
      reg.eax = current.mem + reg.eax;
      is.ret();
      break;
    }
  }
  return reg.eax;
}
Das peek() ist jetzt nur noch dazu da, dass wir wissen, in welchem aktuellen Call wir uns denn gerade befinden.
 

ernst

Top Contributor
Hallo tttpdigest,
Du hast geschrieben:
"Du hast Recht, wenn man ganz pedantisch sein möchte, dann würde man es wohl eher so machen:"
Habe jetzt auch eine Idee, wie man eine Rekursion iterativ simuliert.
(Programm siehe unten: Fibonacci).
Jede Berechnung f(...) wird als Auftrag verstanden, der in eine Auftragsbox gepackt wird und auf den Stapel kommt.
Frage:
Kann man diese Idee für beliebige Rekursionen nutzen, um diese iterativ zu simulieren ?

mfg
ern


Java:
/*
P R O G R A M M B E S C H R E I B U N G
I) Rekursives Programm
Es soll das folgende rekursive Programm durch eine reine Iteration
nicht rekursiv implementiert werden.
Man soll daran ein Schema erkenn, wie man das allgemein macht.

    static int fibIterativRekursiv(int n) {
        int auftragsergebnis;
        int unterauftrag1;
        int unterauftrag2;
        if (n == 1) {
            auftragsergebnis = 10;
        } else if (n == 2) {
            auftragsergebnis = 20;
        } else {
            unterauftrag1 = fibIterativRekursiv(n - 1);
            unterauftrag2 = fibIterativRekursiv(n - 2);
            auftragsergebnis = unterauftrag1 + unterauftrag2;
        }
        return auftragsergebnis;

    }

II) Auftragsboxen

Eine Auftragsbox besteht aus 4 Teilen:
- arg
- unterauftrag1
- unterauftrag2
- auftragsergebnis

Diese Auftragsbox legt der Augtragggeber auf einen Stapel, wo sie dann
vom Auftragnehmer abgeholt wird.

Aus einem Auftrag werden Unteraufträge "unterauftrag1" bzw. "unterauftrag2"
gemacht. Dort wird vermerkt:
- ob diese Unteraufträge in "Auftrag gegeben" wurden, also noch in Bearbeitung
  sind (IN_BEARBEITUNG) bzw.
- oder ob sie schon abgearbeitet wurden (Ergebnis liegt vor),
  dann steht dort das Ergebnis (als Zahl) drin.

In "auftragsergebnis" wird vermerkt:
- ob das Auftragsergebnis (das von den Unteraufträgen abhängt) in Auftrag
  gegeben wurde und noch nicht vorlegt also noch in Bearbeitung ist bzw.
- oder ob es schon abgearbeitet wurde (Ergebnis liegt vor),
  dann steht dort das Ergebnis (als Zahl) drin. Diese berechnet sich aus dem
  Wert von auftrag1 bzw, auftrag2, also:
  auftragsergebnis = unterauftrag1 + unterauftrag2
 
In "arg" steht ein Parameterwert, der zur Berechnung des Auftragsergebnisses
benötigt wird.

III)
Lege Auftragsbox auf den Stapel
while (unterste Auftragsbox.auftragsergebnis ist in Bearbetung) {
  oberstes Stapelelement einlesen in topAuftragsbox
  if (topAuftragsbox.auftragsergebnisLiegtVor()) {
    zweites Stapelelement in secondAuftragsbox einlesen
    secondAuftragsbox mit topAuftragsbox.auftragsergebnis bestücken
    stapel.pop();
  else if(topAuftragsbox.sindAlleUnteraufträgeAusgeführt()){
    topAuftragsbox.auftragsergebnis=topAuftragsbox.unterauftrag1+topAuftragsbox.unterauftrag2;
  else{
    index = topAuftragsbox.nächsterAuszuführenderUnterauftrag();
    arg=topAuftragsbox.arg-index;
    stapel.push(new Auftragsbox(arg));


 */
package rekursionsimulation300;

import java.util.ArrayList;

public class Startklasse {

    public static void main(String[] args) {
        int auftragsergebnis;
        int n;
        n = 5;
        auftragsergebnis = fibIterativ(n);
        System.out.println("fibIterativ(" + n + ")" + "=" + auftragsergebnis);

    }
   
    static int fibIterativ(int n) {
        int index;
        int arg;
        Stapel stapel = new Stapel();
        stapel.push(new Auftragsbox(n));
        // oberstes Element auf dem Stapel
        Auftragsbox topAuftragsbox = stapel.peek();
        // zweit oberstes Element auf dem Stapel       
        Auftragsbox secondAuftragsbox = null;

        while (stapel.peek().auftragsergebnis == Konstanten.IN_BEARBEITUNG || stapel.size()>1) {
            // oberstes Stapelelement lesen
            topAuftragsbox = stapel.peek();
            if (topAuftragsbox.auftragsergebnisLiegtVor()) {
                // es gibt noch ein weiteres Element
                // bestimme das zweitoberste Element des Staples
                secondAuftragsbox = stapel.peekSecond();
                secondAuftragsbox.auftragsergebnisBeimAuftraggeberAbgeben(topAuftragsbox.auftragsergebnis);
                stapel.pop();
            }
            else if(topAuftragsbox.sindAlleUnteraufträgeAusgeführt()){
                topAuftragsbox.auftragsergebnis=topAuftragsbox.unterauftrag1+topAuftragsbox.unterauftrag2;
            }
            else{
                index = topAuftragsbox.nächsterAuszuführenderUnterauftrag();
                arg=topAuftragsbox.arg-index;
                stapel.push(new Auftragsbox(arg));
            }       
        }
        return topAuftragsbox.auftragsergebnis;
    }

    static int fibIterativRekursiv(int n) {
        int auftragsergebnis;
        int unterauftrag1;
        int unterauftrag2;
        if (n == 1) {
            auftragsergebnis = 10;
        } else if (n == 2) {
            auftragsergebnis = 20;
        } else {
            unterauftrag1 = fibIterativRekursiv(n - 1);
            unterauftrag2 = fibIterativRekursiv(n - 2);
            auftragsergebnis = unterauftrag1 + unterauftrag2;
        }
        return auftragsergebnis;

    }
}

class Auftragsbox {

    public int arg;
    // unterauftrag1:
    // - wurde in Auftrag gegeben und liegt noch nicht vor oder
    // - Ergebnis liegt als Zahl vor
    public int unterauftrag1;
    public int unterauftrag2;
    public int auftragsergebnis;

    public Auftragsbox(int arg) {
        this.arg = arg;
        if (arg > 2) {
            this.unterauftrag1 = Konstanten.IN_BEARBEITUNG;
            this.unterauftrag2 = Konstanten.IN_BEARBEITUNG;
            this.auftragsergebnis = Konstanten.IN_BEARBEITUNG;
        } else if (arg == 1) {
            // irgenwas reinschreiben
            this.unterauftrag1 = 123;
            // irgenwas reinschreiben           
            this.unterauftrag2 = 123;
            this.auftragsergebnis = 10;
        } else if (arg == 2) {
            // irgenwas reinschreiben
            this.unterauftrag1 = 124;
            // irgenwas reinschreiben           
            this.unterauftrag2 = 124;
            this.auftragsergebnis = 20;
        }

    }

    public boolean auftragsergebnisLiegtVor() {
        boolean ret = false;
        if (unterauftrag1 != Konstanten.IN_BEARBEITUNG && unterauftrag2 != Konstanten.IN_BEARBEITUNG && auftragsergebnis != Konstanten.IN_BEARBEITUNG) {
            ret = true;
        } else {
            ret = false;
        }

        return ret;
    }

    public int nächsterAuszuführenderUnterauftrag() {
        int index = -1;
        if (unterauftrag1 == Konstanten.IN_BEARBEITUNG) {
            index = 1;
        } else if (unterauftrag2 == Konstanten.IN_BEARBEITUNG) {
            index = 2;
        }
        return index;
    }

    public void auftragsergebnisBeimAuftraggeberAbgeben(int auftragsergebnis) {
        if (unterauftrag1 == Konstanten.IN_BEARBEITUNG) {
            unterauftrag1 = auftragsergebnis;
        } else if (unterauftrag2 == Konstanten.IN_BEARBEITUNG) {
            unterauftrag2 = auftragsergebnis;
        }
    }


    public boolean sindAlleUnteraufträgeAusgeführt() {
        boolean erg=false;
        if (unterauftrag1 != Konstanten.IN_BEARBEITUNG && unterauftrag2 != Konstanten.IN_BEARBEITUNG){
            erg = true;
        }
        else{
            erg=false;
        }
        return erg;
    }
}

class Stapel {
    public ArrayList<Auftragsbox> liste;

    public Stapel() {
        liste = new ArrayList<Auftragsbox>();
    }

    public Auftragsbox pop() {
        int auftragsergebnis;
        Auftragsbox f;
        auftragsergebnis = liste.size();
        f = liste.get(auftragsergebnis - 1);
        liste.remove(auftragsergebnis - 1);
        return f;
    }

    public Auftragsbox peek() {
        int auftragsergebnis;
        Auftragsbox f;
        auftragsergebnis = liste.size();
        f = liste.get(auftragsergebnis - 1);
        return f;
    }

    public Auftragsbox peekSecond() {
        int auftragsergebnis;
        Auftragsbox f;
        auftragsergebnis = liste.size();
        f = liste.get(auftragsergebnis - 2);
        return f;
    }

    public void push(Auftragsbox f) {
        liste.add(f);
    }

    public int size() {
        return liste.size();
    }
}


class Konstanten {

    public static final int IN_BEARBEITUNG = -1;
}
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Applikationsserver (WildFly) - Zugriff auf Ressourcen.. Problem mit Pfade Java Basics - Anfänger-Themen 10
C Datei über relative Pfade einlesen Java Basics - Anfänger-Themen 6
L Breadth-First Search statt einem Pfad, alle Pfade herausfinden Java Basics - Anfänger-Themen 4
MiMa Formate für Dateien und Pfade? Java Basics - Anfänger-Themen 1
I Alle Laufwerke und deres Pfade ausgeben Java Basics - Anfänger-Themen 6
O Löschen lange pfade...Fehler? Java Basics - Anfänger-Themen 1
O Absolute Pfade in mehrere Klassen verwenden Java Basics - Anfänger-Themen 3
L Manifest und absolute Pfade Java Basics - Anfänger-Themen 5
S Variable Pfade Java Basics - Anfänger-Themen 14
N Feste Hardcodierte Pfade im Quellcode Java Basics - Anfänger-Themen 6
M Pfade in Tree einbinden Java Basics - Anfänger-Themen 2
J Icons. und. Pfade Java Basics - Anfänger-Themen 3
N Java wird nicht ausgeführt obwohl nötige Pfade gesetzt sind Java Basics - Anfänger-Themen 5
G Servlets: Erwartete/Angelegte Pfade von Tomcat/Eclipse Java Basics - Anfänger-Themen 2
A Unterschiedliche Pfade je nach OS? Java Basics - Anfänger-Themen 4
L Dateien im Netzwerk bearbeiten (UNC-Pfade und gemappte Laufw Java Basics - Anfänger-Themen 5
A Reguläre Ausdrücke der Pfade unter Windows und Unix Java Basics - Anfänger-Themen 3
J relative pfade windows/unix Java Basics - Anfänger-Themen 12
F Relative Pfade zu Fenster-Icon in Main-Methode? Java Basics - Anfänger-Themen 7
V filereader soll aus config.txt pfade lesen Java Basics - Anfänger-Themen 6
M Länge eines Arrays als Variable speichern möglich? Java Basics - Anfänger-Themen 14
P Objekt einer Methode eines anderen Objektes übergeben Java Basics - Anfänger-Themen 5
P Wie kann ich beispielsweise Speicherstände eines Spiels DAUERHAFT in meinem Programm speichern? Java Basics - Anfänger-Themen 3
laxla123 Eigenschaften eines Algorithmus (determiniert vs.. deterministisch) Java Basics - Anfänger-Themen 2
monsterherz Ablauf der Erstellung eines Java Programmes Java Basics - Anfänger-Themen 17
monsterherz Fehler Semikolon fehlt - ich weiss aber nicht wo da noch eines hin sollte... Java Basics - Anfänger-Themen 21
J Farbe des Striches eines TitledBorders ändern Java Basics - Anfänger-Themen 2
pc pc pc pc pc letztes Element eines Arrays n Java Basics - Anfänger-Themen 3
walid Öffnungszeiten eines Geschäftes Java Basics - Anfänger-Themen 3
paulen1 Best Practice "Unchecked Assignment" Warnung beim erstellen eines 2D Arrays of Arraylists Java Basics - Anfänger-Themen 2
T Probleme beim Import eines Git-Repos Java Basics - Anfänger-Themen 2
U Eigenschaft eines JTextfiels per ActionListener ändern... Java Basics - Anfänger-Themen 2
B Synchronisation eines kleinen Museums Java Basics - Anfänger-Themen 47
krgewb Breite und Höhe eines Bildes in base64 auslesen Java Basics - Anfänger-Themen 3
Sachinbhatt Was ist die Notwendigkeit eines Sammlungsframeworks in Java? Java Basics - Anfänger-Themen 2
N Textdatei aus Resourcen-Ordner eines Projekts/ jar-file lesen Java Basics - Anfänger-Themen 4
B Produkt eines double - streams Java Basics - Anfänger-Themen 3
B Attribute eines Objekts einer Klasse durch statische Methode einer 2. Klasse ändern? Java Basics - Anfänger-Themen 32
S Variablen Letzte Zeile eines Strings entfernen Java Basics - Anfänger-Themen 1
D Inhalt eines Arrays ausgeben Java Basics - Anfänger-Themen 7
A Jedes zweite Element eines Arrays entfernen Java Basics - Anfänger-Themen 30
sserio Java Fx, wie erstellt man einen EventHandler, der durch das Drücken eines Button Texte in eine Table view einfügt Java Basics - Anfänger-Themen 17
J Größe eines Strings in Pixel Java Basics - Anfänger-Themen 18
M Parse-Tree eines statements darstellen Java Basics - Anfänger-Themen 0
H Java verkettete Liste, Wert eines Index zurückgeben Java Basics - Anfänger-Themen 1
bluetrix Programmieren eines Bots für Zahlen-Brettspiel Java Basics - Anfänger-Themen 9
J Hinzufügen eines Objektes in ein Objekt-Array Java Basics - Anfänger-Themen 62
M Wie kann die Implementation einer Methode den Wert eines Attributs vermindern? Java Basics - Anfänger-Themen 3
A Rekursive Implementation eines Codes Java Basics - Anfänger-Themen 4
H String Repräsentation eines Rechtecks mit Instanz-Methode Java Basics - Anfänger-Themen 8
M Konstruktor ohne Übergabe eines Wertes Java Basics - Anfänger-Themen 7
M Wie kann ich in einem Konstruktor die Methode eines anderen Interfaces mit den jeweiligen Parametern aufrufen? Java Basics - Anfänger-Themen 8
M Wie erreiche ich das Vorwärtsgehen eines Roboters? Java Basics - Anfänger-Themen 2
M Wie erreiche ich es das Vorwärtsgehen eines Roboters? Java Basics - Anfänger-Themen 0
R While-Loop der die Einträge eines Arrays in umgekehrter Reihenfolge anzeigt Java Basics - Anfänger-Themen 3
A Optimierung eines Programms: Mergen der Dateien Java Basics - Anfänger-Themen 23
melisax Alle Möglichkeiten eines Wortes angeben Java Basics - Anfänger-Themen 3
A Java, verarbeitung eines xml-files Java Basics - Anfänger-Themen 2
C Fehler beim erstellen eines Objektes Java Basics - Anfänger-Themen 3
B Konkatenieren eines Strings und inkremtierenden Zahl zu einer INT Variablen Java Basics - Anfänger-Themen 7
F Initialisieren eines Web-Mp3 Players in Tabs durch "booleans" erst wenn Tab geöffnet wird ...? Java Basics - Anfänger-Themen 1
P Drei Zahlen eines Würfelspiels auswerten Java Basics - Anfänger-Themen 7
C Brauche Hilfe beim Schreiben eines Programmes :/ Java Basics - Anfänger-Themen 1
C initialisieren eines arrays richtiger Größe und mit geeignetem Datentyp Java Basics - Anfänger-Themen 26
C Überprüfen eines Programms auf Syntaxfehler Java Basics - Anfänger-Themen 3
S Wie kann ich den Bereich eines Integers begrenzen? Java Basics - Anfänger-Themen 2
nonickatall Grundsätzliches Verständnisproblem des Aufbaus eines Programms Java Basics - Anfänger-Themen 19
B Downgrade eines bestehenden Projektes Java Basics - Anfänger-Themen 5
amelie123456 Geschwindigkeit der Methode bewegeDich eines Objekts ändern Java Basics - Anfänger-Themen 2
D Hilfe beim Erzeugen eines Arrays NullPointerException wird ausgelöst Java Basics - Anfänger-Themen 11
J maximaler Wert eines Integers Java Basics - Anfänger-Themen 14
TimoN11 IntelliJ , Ausgabe von einem Quellcode in Eingabe eines Quellcodes Java Basics - Anfänger-Themen 1
Z Rückgabe eines Values in umgekehrte richtung Java Basics - Anfänger-Themen 5
L Methode zum invertieren eines Arrays Java Basics - Anfänger-Themen 7
B fragen zu Aufbau eines UML-Klassendiagramm Java Basics - Anfänger-Themen 1
eleonori Durchschnitt aller Werte eines Baums berechnen Java Basics - Anfänger-Themen 5
M Benutzereingabe eines Codes verbessern Java Basics - Anfänger-Themen 3
B Modulo-Operator anhand eines Beispieles erklären Java Basics - Anfänger-Themen 7
J Verschieben von Buchstaben in einem String um vorgegebene Anzahl von Zeichen innerhalb eines weiteren String Java Basics - Anfänger-Themen 12
F Auf Variablen eines Konstruktors zugreifen Java Basics - Anfänger-Themen 4
Kawastori Größe eines Arrays bestimmen Java Basics - Anfänger-Themen 13
Lena_2611 Vergleich von Array1 Index mit Array2 Wert und erzeugen eines neues Arrays Java Basics - Anfänger-Themen 8
A Teilarrays eines 2D-Arrays sortieren Java Basics - Anfänger-Themen 4
marcooooo Separator zwischen allen Zeichen eines Strings einfügen Java Basics - Anfänger-Themen 29
C Wie kann ich Versionen eines Projektes in Eclipse erstellen? Java Basics - Anfänger-Themen 3
yoskaem Text Color durch Klicken eines Buttons in anderer Activity ändern Java Basics - Anfänger-Themen 2
A Teilen eines Arrays Java Basics - Anfänger-Themen 5
DorFey Sortieren eines mehrdimensionalen Arrays Java Basics - Anfänger-Themen 8
P Klasse hat keinen Zugriff auf getter/setter-Methoden eines Objektes Java Basics - Anfänger-Themen 9
R Löschen und ausgeben eines Teilbaums Java Basics - Anfänger-Themen 3
J Alle Werte eines Strings zusammen addieren Java Basics - Anfänger-Themen 15
M Hilfe bei Strukturierung eines Buchungssystems Java Basics - Anfänger-Themen 3
M Erstellen eines insets Objekts, GridBagLayout Java Basics - Anfänger-Themen 13
M Rückgabe eines Arrays Java Basics - Anfänger-Themen 10
Z Erste Schritte Indexe innerhalb eines Arrays zusammensählen Java Basics - Anfänger-Themen 14
W Random Zahl unter Berücksichtung eines Durchschnitts Java Basics - Anfänger-Themen 7
N Länge eines Arrays in einem Objekt testen Java Basics - Anfänger-Themen 51
A Freie Stelle eines Arrays Java Basics - Anfänger-Themen 17
C Erstellen eines Widerstandsnetzwerks Java Basics - Anfänger-Themen 10
C Methode Seiten tauschen eines erstellten Rechtecks mit Seite A und B Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben