import algds.IOUtils;
/**
 * AlgDs WS99, Aufgabe 15.
 * Berechnet die n-te Fibonacci-Zahl.
 *
 * @author Christian Semrau, 8.11.1999, 24.12.1999
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */

/*
A1: fib(n) = ( (n==0)||(n==1) ? 1 : fib(n-1)+fib(n-2) );
A2: fib(n) = h(n,1,1);  h(n,a,b) = ( (n==0) ? a : h(n-1, b, a+b) );

Teil a)

A1: fib(6)
=                                  fib(5)     + fib(4)
=                        (fib(4)     + fib(3)) + fib(4)
=              ((fib(3)     + fib(2)) + fib(3)) + fib(4)
=      (((fib(2)   + fib(1)) + fib(2)) + fib(3)) + fib(4)
= ((((fib(1)+fib(0))+ fib(1))+ fib(2)) + fib(3)) + fib(4)
= ((((  1   +1)+ fib(1)) + fib(2)) + fib(3)) + fib(4)
= (((         2+1)  + fib(2))    + fib(3)) + fib(4)
= ((3     + (fib(1)+fib(0)))  + fib(3)) + fib(4)
= ((3 +   (1   +  1)   )   + fib(3)) + fib(4)
= ((3 +        2       ) + fib(3)) + fib(4)
= ( 5 +        (fib(2)  + fib(1))) + fib(4)
= ( 5 + ((fib(1)+fib(0)) + fib(1))) + fib(4)
= ( 5 + ((  1   +  1   ) + fib(1))) + fib(4)
= ( 5 +        (2        +  1)) + fib(4)
= ( 5 +                 3) + fib(4)
= (8) +                fib(4)
= 8 +            (fib(3) + fib(2))
= 8 +      ((fib(2) + fib(1)) + fib(2))
= 8 + (((fib(1)+fib(0))+fib(1)) + fib(2))
= 8 + (((  1   +  1   )+fib(1)) + fib(2))
= 8 + ((       2       +  1 ) + fib(2))
= 8 + (                3   + fib(2))
= 8 + (3 + (fib(1)+fib(0)))
= 8 + (3 + (  1   +  1   ))
= 8 + (3 + 2)
= 13
Irgendjemand, der sich da NICHT durchgefunden hat ?

A2: fib(6)
= h(6,1,1) = h(5,1,2) = h(4,2,3) = h(3,3,5) = h(2,5,8) = h(1,8,13) = h(0,13,21)
= 13
Das war einfach, oder?

n:fib(n), 0:1, 1:1, 2:2, 3:3, 4:5, 5:8, 6:13, 7:21, 8:34

Teil b)

A1:
n=6, Anzahl der Aufruefe auf den verschiedenen Ebenen:
 fib(0):5, fib(1):8, fib(2):5, fib(3):3, fib(4):2, fib(5):1, fib(6)=1, gesamt fib:25
 fib:21-1+5 = fib(7)-1+fib(4)
calls(A1(n)) = fib(n+1)-1+fib(n-2)  (Aufruefe der Funktion A1)

O(A(n)) gibt die Komplexitaet eines Algorithmus A in Abhaengigkeit von der Eingabe n an

-> O(A1(n)) = fib(n)  (Unterschied ist max. ein konstanter Faktor)
.. O(A1(n)) = (((1+sqrt(5))/2)^(n+1) - ((1-sqrt(5))/2)^(n+1))/sqrt(5)
.. O(A1(n)) = ((1+sqrt(5))/2)^n
.. O(A1(n)) = 1.62^n
-> O(A1(n)) = 2^n -> "exponentielle Laufzeit"

A2:
n=6, Anzahl der Aufruefe auf jeder Ebene (n..0) ist 1
calls(A2(n)) = n+1
-> O(A2(n)) = n -> "lineare Laufzeit"


Laufzeiten von A1 auf meinem Rechner:
n: Zeit, (Zeitangaben in sec, einmalig mit der Stoppuhr gemessen, kaum geschummelt),
 dahinter in Klammern erwarteter Wert als Summe der beiden vorigen Zeiten
<35: <2
 36: 2 ()               37: 2 ()            38: 4 (2+2=4)
 39: 7 (2+4=6)          40: 11 (4+7=11)     41: 18 (7+11=18)
 42: 28 (11+18=29)      43: 46 (18+28=46)   44: 75 (28+46=74)
 45: 121 (46+75=121)    46: 197 (75+121=196)
100: laeuft noch.... (ca. 1.2 Mio Jahre ;-)
BTW: fib(46) zu gross fuer int (= 2 971 215 073)

Teil c)

das Programm....
*/

public class ChS_Aufg15 {
	

/**
 * Algorithmus A1
 */
static int A1(int n) {
  // der Operator "(Bedingung) ? Ausdruck1 : Ausdruck2" ist der einzige
  // sogenannte "ternaere Operator" : ist die Bedingung true, wird Ausdruck1
  // berechnet und geliefert, ist sie false, wird Ausdruck2 berechnet und
  // geliefert. Dieser Operator ist das applikative Aequivalent zu
  // "if(Bedingung) Anweisung1; else Anweisung2;"
  return( (n==0)||(n==1) ? 1 : A1(n-1)+A1(n-2) );
} // A1()

/**
 * Algorithmus A2
 */
static long A2(int n) {
  return( A2_1(n, 1, 1) );
} // A2()

static long A2_1(int n, long a, long b) {
  return( (n==0) ? a : A2_1(n-1, b, a+b) );
} // A2_1()

/**
 * explizite Berechnung, verwendet double-Zahlen
 */
static long A3(int n) {
  // fib(n) = 1/sqrt(5)*(((1+sqrt(5))/2)^(n+1) - ((1-sqrt(5))/2)^(n+1))
  // tut mir leid wegen den vielen Klammern, als math. Term sieht das einfacher aus
  // das n+1 ergibt sich daraus, dass n bei 0 beginnt
  double s5 = Math.sqrt(5);
  double a = Math.pow((1+s5)/2, n+1) - Math.pow((1-s5)/2, n+1);
  return(Math.round(a/s5));  // Math.round liefert long
}

public static void main(String[] args) {
  int zahl;

  System.out.println("AlgDs WS99 Aufgabe 15, Christian Semrau 08.11.1999");
  System.out.println("Gibt die n-te Fibonacci-Zahl aus (beginnend bei 0).");

  try {
	// Eingabe auch ueber Kommandozeile moeglich
	zahl = new Integer(args[0]).intValue();
  }
  catch(ArrayIndexOutOfBoundsException e) {
	// Wird kein Parameter angegeben, wird die Zahl von readInt() geholt
	System.out.println("Das Programm gibt die n-te Fibonacci-Zahl aus.");
	System.out.print("n: ");
	zahl = IOUtils.readInt();
  }
  catch(NumberFormatException e) {
	// Parameter war keine Zahl
	System.out.println("ist \""+args[0]+"\" eine ganze Zahl?!");
	return;
  };

  // Ausgabe von allen drei Algorithmen
  System.out.println("fib3("+zahl+")="+A3(zahl)); // A3 und A2 sind sehr schnell
  System.out.println("fib2("+zahl+")="+A2(zahl)); //
  System.out.println("fib1("+zahl+")="+A1(zahl)); // A1 braucht ewig (Laufzeiten siehe oben)

} // main()
} // class ChS_Aufg15