001    package de.hska.info1.rekursion;
002    
003    /**
004     * Enthält verschiedene Implementierungen, um die
005     * Fibonacci-Zahlen zu berechnen.
006     * 
007     * @author Christian Pape
008     *
009     */
010    public class FibonacciZahlen {
011    
012            
013            /**
014             * Berechnet die Fibonaccizahl von n rekursiv.
015             */
016            public long fib1(long n) {
017                    if (n <= 1) {
018                            return 1;
019                    } else {
020                            return fib1(n - 1) + fib1(n - 2);
021                    }
022            }
023    
024            /**
025             * Berechnet die Fibonaccizahl nicht mehr rekursiv,
026             * sondern iterativ. Die Rekursion ist mit Hilfe
027             * des Dynamischen Programmierens eleminiert.
028             */
029            public long fib2(int n) {
030                    long [] fib = new long[n + 1];
031    
032                    fib[0] = 1;
033                    fib[1] = 1;
034                    
035                    for (int k = 2; k <= n; k++) {
036                            fib[k] = fib[k - 1] + fib[k - 2];
037                    }
038                    
039                    return fib[n];
040            }
041    
042            /**
043             * Optimierung der iterativen Variante, so dass nicht mehr
044             * alle Fibonaccizahlen zwischengespeichert werden, sondern
045             * nur die beiden zuvor berechneten.
046             */
047            public long fib(int n) {
048                    long fib0 = 1;
049                    long fib1 = 1;
050                    long fibk = 1;
051                    
052                    for (int k = 2; k <= n; k++) {
053                            fibk = fib0 + fib1;
054                            fib0 = fib1;
055                            fib1 = fibk;
056                    }
057                    
058                    return fibk;
059            }
060    
061            public static void main(String [] s) {
062                    FibonacciZahlen fibonacciZahlen = new FibonacciZahlen();
063                    
064                    System.out.println( fibonacciZahlen.fib1(2000) );
065            }
066    }