Fibonacci.java

Go to the documentation of this file.

 
public class Fibonacci {
  private long ncalls = 0;
  private long[] fibs = null;
  private int nf = 0;
 
  // Empty constructor
  public Fibonacci () {}
 
  public Fibonacci ( int n ) {
     Fibo(n-1);
  }
 
  public static void main(String[] args) {
    int n = 0;
    if (args.length > 0) {
        try {
           n = Integer.parseInt(args[0]);
        } catch (NumberFormatException e) {
           System.err.println("Argument must be an integer");
           System.exit(1);
        }
    }
    Fibonacci f = new Fibonacci();
    Fibonacci f2 = new Fibonacci(n);
    f.fibo(n);
    System.out.println(f2);
    System.out.println(f);
    System.out.println(String.format("%12s %12s %12s %12s", "N", "Fib(N)", "Dumb", "Smart"));
    System.out.println(String.format("%12s %12s %12s %12s", "-------", "-------", "-------", "-------"));
    for ( int i = 1; i <= n; ++i ) {
        f.ncalls = 0;
        long dumb_result = f.fiboDumb(i);
        long dumb_count = f.ncalls;
        long smart_result = f.fib(i);
        long smart_count = f.ncalls;    
        System.out.println (String.format ("%12d %12d %12d %12d", i, smart_result, dumb_count, smart_count)); 
   }
  }
 
  public void fibo (int n) {
    long n0 = 0, n1 = 1, n2;               // Initialize variables of the series
    System.out.print(n0 + " " + n1 + " "); // Print first and second terms
 
    for (int i = 0; i < n-2; i++) {        // Loop for the next n terms
      n2 = n1 + n0;                        // Next term is sum of previous two
      System.out.print(n2 + " ");          // Print it out
      n0 = n1;                             // First previous becomes 2nd previous
      n1 = n2;                             // And current number becomes previous
    }
    System.out.println("\n");             // Terminate the line
  }
 
  public long fiboDumb (int n) {
      ++ncalls;
      if ( n <= 1 ) return n;
      return fiboDumb(n-1)+fiboDumb(n-2);
  }
 
  public long fib (int n) {
      this.ncalls = 0;
      return fib (n,0,1);
  }
 
  private long fib (int n, long s1, long s2) {
      ++ncalls;
      if (n<=1)
          return s1;
 
      return fib(n-1,s1+s2,s1);
  }
 
  public long Fibo ( int n ) {
    ++ncalls;
 
    if ( n <= 1 ) return n;
 
    if ( nf == 0 ) {
         if ( fibs == null || fibs.length <= n )
              fibs = new long [n+1];  // Each class variable, instance variable, or array component is initialized 
                                      // with a default value when it is created (§15.9, §15.10) [...] 
                                      // For type int, the default value is zero, that is, 0. 
         nf = n;
    }
 
    if ( fibs[n-1]==0 ) fibs[n-1] = Fibo(n-1);
    if ( fibs[n-2]==0 ) fibs[n-2] = Fibo(n-2);
 
    long f = fibs[n] = fibs[n-1]+fibs[n-2];
    if ( n == nf )
         nf = 0;
 
    return f;
  }
 
  public String toString() {
    String s = "";
    if ( fibs != null ) {
        for ( int i = 0; i < fibs.length; ++i )
              s += Long.toString (fibs[i]) + " ";
        s += String.format("\nNumber of calls = %d\n", ncalls);
    }
    return s;
  }
}