/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu
************************************************/

import java.io.*;

public class P01Fibo {
  private static final String FileOutputName = "FiboReport.txt";

  private static final int N = 50;

  private static long fibo1(int n) {
    if (n <= 1)
      return n;
    return fibo1(n - 1) + fibo1(n - 2);
  }

  private static long fibo2(int n) {
    if (n < 2) {
      return n;
    }
    long prevprev = 0;
    long prev = 1;

    for (int i = 2; i < n; i++) {
      long temp = prev;
      prev += prevprev;
      prevprev = temp;
    }
    return prev + prevprev;
  }

  public static void main(String[] args) throws IOException {
    PrintStream out = new PrintStream(new File(FileOutputName));
    try {
      for (int i = 0; i < N; i++) {
        long tm = System.currentTimeMillis();
        long f = fibo1(i);
        tm = System.currentTimeMillis() - tm;
        out.printf("%4d %15d    t1=%6d", i, f, Math.round(tm / 1000));
        tm = System.currentTimeMillis();
        f = fibo2(i);
        tm = System.currentTimeMillis() - tm;
        out.printf(" %15d    t2=%6d%n", f, Math.round(tm / 1000));
        out.flush();
      }
    } finally {
      out.close();
    }
  }
}