/*
Fibonacci-Zahlengenerator
copyright (C) Robert Nitsch, 2006

Dieses Programm generiert bzw. errechnet Fibonaccizahlen.


Änderungen:
	- 16.09.06 17:35
		- Funktion fib_fastest() hinzugefügt. Wird auch ab sofort vom Programm verwendet.
		- geringe Änderungen an den Funktion fib() und fib_fast() - v.a. werden nun andere Datentypen
		  verwendet (unsigned long).
	- erstes Release Ende August.


Beschreibung:
Bei den Fibonaccizahlen geht man von einer Funktion fib(n) aus, die fib(n-1)+fib(n-2) zurückgibt - dies ist,
einfacher ausgedrückt, die Summe der beiden vorangegangenen Funktionswerte.
Damit dieses Prinzip nicht in einem Chaos endet, wurden die Startwerte fib(0) und fib(1) festgelegt:
fib(0)=0
fib(1)=1

Demnach kann man die Zahlenreihe folgendermaßen fortsetzen:
fib(2)	=	fib(0)+fib(1)	=	1
fib(3)	=	fib(1)+fib(2)	=	2
fib(4)	=	fib(2)+fib(3)	=	3
fib(5)	=	fib(3)+fib(4)	=	5
fib(6)	=	...				=	8
fib(7)	=	...				=	13
fib(8)	=	...				=	21
fib(9)	=	...				=	34
fib(10)	=	...				=	55


Der Algorithmus lässt sich sehr elegant mit einer rekursiven Funktion lösen. Wie die Implementierung einer solchen
rekursiven Funktion aussieht, zeigt die Funktion fib().
Das Programm verwendet aber aus Geschwindigkeitsgründen die Funktion fib_fastest(), welche
ganz anders funktioniert. Sie benötigt nur 3 Variablen!

(Es gibt noch eine weitere Funktion namens fib_fast(), die ebenfalls nicht rekursiv ist, aber die die
Zwischenergebnisse in einem Array ablegt.)
*/


#include <iostream>
#include <iomanip>

using namespace std;

// Debugmodus?
//#define DEBUG


// Deklarationen
void pause();
long double fib(long double n);			// langsam; rekursive Funktion
unsigned long fib_fast(long int n); 	// schnell; nicht rekursiv, legt die Zwischenergebnisse in einem Array/Vektor ab
unsigned long fib_fastest(long int n); 	// superschnell, verwendet nur 3 Variablen!
// (die schnellste Funktion fib_fastest() wird im Programm verwendet)

int main()
{
	// Variablen
	long int input;
	
	// Ausgabe immer als Dezimalzahlen
	cout << dec; 
	
	// n einlesen und fib(n) ausgeben
	cout << "Fibonacci-Zahlengenerator" << endl << endl;
	cout << "Geben Sie n ein (max. 92): " << endl;
	cin >> input;
	
	// Programm abbrechen, wenn n größer 92
	if(input > 92) { cerr << "Fehler: n darf nicht größer 92 sein!" << endl; pause(); return 0; }
	
	cout << endl << "Fibonaccizahl zu " << input << " ist: " << fib_fastest(input) << " / " << fib_fast(input);
	
	// auf Eingabe warten
	pause();
	
	// Beenden
	return 0;
}

// Pause
void pause()
{
	cin.get();
	cin.get();
}


// rekursive Funktion, die die Fibonaccizahl zu n berechnet
unsigned long fib(long int n)
{
	if(n<2) return n;
	return fib(n-1)+fib(n-2);	
}

// diese Funktion erfüllt denselben Zweck wie fib() - siehe oben -, aber sie speichert die Zwischenergebnisse in
// einem Array. Außerdem arbeitet sie nicht wie fib() von n gegen 0, sondern von 0 gegen n!
// Sie ist zudem _nicht_ rekursiv!
unsigned long fib_fast(long int n)
{
	if(n < 2) return n;
	
	unsigned long buffer[n];
	buffer[0]=0;
	buffer[1]=1;
	
	for(int i=2; i < n+1; i++)
	{
		buffer[i]=buffer[i-1]+buffer[i-2];
		#ifdef DEBUG
		cout << buffer[i] << endl;
		#endif			
	}
	
	return buffer[n];
}

// diese Funktion ist ebenfalls NICHT rekursiv und verwendet zudem KEIN Array.
// Sie ist somit die schnellste Funktion von allen.
// Die Idee dieser Implementierung stammt übrigens nicht von mir, sondern von Dominic Griesel.
unsigned long fib_fastest(long int n)
{
	if(n < 2) return n;
	
	// die 3 benötigten Variablen
	unsigned long x=0;
	unsigned long y=1;
	unsigned long z=0;
	
	for(int i=1; i < n; i++)
	{
		z=x+y;
		if(x <= y) x=z;
		else y=z;
	}
	
	if(x <= y)
		return y;
	else
		return x;			
}