Frage von Namennutzerin, 15

Iterative Fibonacci Methode unter der Benutzung von Stacks?

Hallo, Hab morgen Klausur und komme bei dieser Aufgabe einfach nicht auf die Lösung. Wie kann ich die rekursive Fibonacci-Methode:

public static int fibonacci(int n) { if (n > 2) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } }

mithilfe von Stacks iterativ implementieren?

Eine iterative Lösung hätte ich schon, aber die implementiert nicht die rekursive Vorgehensweise:

public static int fibIt (int n) { int fib1 = 0; int fib2 = 1; int fib = 0; for (int i = 1; i < n; i++) { fib = fib1 + fib2; fib1 = fib2; fib2 = fib; } return fib; }

Hat jemand vielleicht einen Vorschlag?

Antwort
von W00dp3ckr, 10

<2

Ein klassischer, unoptimierter C function call tut die Parameter auf den Stack und dann den Return Wert wieder auf den Stack.

Antwort
von Namennutzerin, 10

Nevermind. Hab wohl zu schnell gepostet. Mir ist der Knoten jetzt aufgegangen. Für alle die diesen Post in Zukunft mal lesen hier meine Lösung:

public static int fib (int n) {
int current;
int result = 0;
Stack<Integer> stack = new Stack<Integer>();

stack.push(n);

while (!stack.isEmpty()) {
current = stack.pop();
if (current > 1) {
stack.push(current - 1);
stack.push(current - 2);
}
else{
result += current;
}
}
return result;

}

Keine passende Antwort gefunden?

Fragen Sie die Community