Zentral4:fibonacci

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