Zentral4:fibonacci
Rekursives und Iteratives Berechnen der Fibonacci-Folge
FibLive.java
—
Java source code,
1 KB (1350 bytes)
Dateiinhalt
package Fibonacci; public class FibLive { public static void main(String[] args) { // Berechnen der Fibonacci Folge auf verschiedenen Arten int maxfib = 22; // 1. Variante, rekursiv System.out.print("1.Fibonacci:"); for (int i = 1; i <= maxfib; i++) { long x = fib1(i); System.out.print(" " + x); } System.out.println(); // 2. Variante, iterativ System.out.print("2.Fibonacci:"); for (int i = 1; i <= maxfib; i++) { long x = fib2(i); System.out.print(" " + x); } System.out.println(); } public static long fib1(int a) { // Diese Funktion ist die direkte Umsetzung der rekursiven Definition - schnell zu implementieren. // Leider ist das in diesem Fall etwas ineffizient (exponentielle Komplexität) if (a <= 2) { return 1; } else { long result = fib1(a - 1) + fib1(a - 2); return result; } } public static long fib2(int a) { // Diese Version ist iterativ, und merkt sich die letzten beiden Fibonacci Zahlen, // um Wiederholungen zu vermeiden (lineare Komplexität). // (Es sei aber angemerkt das man die Fibonacci Zahlen noch effizienter berechnen kann.) long b1 = 1; // merkt sich fib(i) long b2 = 1; // merkt sich fib(i+1) for (int i = 1; i<a; i++){ long b3 = b2; // merkt sich b2, um es nach b1 zu verschieben b2 = b2 + b1; b1 = b3; } return b1; } }
Artikelaktionen