/*
  Fibonacci4 (fourth version)
  written by Keith Fenske
  Wednesday, 1 May 2002
  Copyright (c) 2002 by Keith Fenske.  All rights reserved.

  This Java program computes the Fibonacci sequence 1, 1, 2, 3, 5, 8, ...
  using the recursive function f(1) = f(2) = 1, f(n) = f(n-1) + f(n-2) as
  explained on page 95 of "Discrete Mathematical Structures".

  This fourth version is different than the first and second versions
  because it uses an array to hold previous results.  The first and second
  versions do O(2^n) function calls to calculate f(n).  By saving the
  previous results, the amount of work is reduced to O(n) ... much faster!

  This fourth version is also different than the third version because
  calculations are done with 64-bit "long" integers, so all results are
  accurate up to f(92) = 7,540,113,804,746,346,429.

  The index of the first element in a Java array is zero (0).  This function
  is defined starting at f(1).  To avoid confusion about function notation
  and index variables, we will create a Java array and ignore the first
  element.  Then f(n) will be in array element n.
*/

import cs1.Keyboard;              // import Lewis/Loftus keyboard class
//                           http://duke.csc.villanova.edu/jss/keyboard.html

public class Fibonacci4
{
  public static void main(String[] args)
  {
    int i;                        // index variable in "for" loop
    int n;                        // function parameter from user
    long[] results;               // array to hold previous results

    System.out.println("\nThis Java program computes the Fibonacci sequence");
    System.out.println("1, 1, 2, 3, 5, 8, 13, 21, ... using an array to hold");
    System.out.println("previous results.");

    do
    {
      System.out.println("\nWhat is the parameter n (from 1 to 99)?");
      System.out.println("Or type any other number to quit.");
      n = Keyboard.readInt();
      if ((0 < n) && (n < 100))
      {
        results = new long[100];  // f(92) is maximum for 64-bit long integers
        results[0] = 0;           // dummy value (not used)
        results[1] = 1;           // initial value for f(1)
        results[2] = 1;           // initial value for f(2)
        for (i = 3; i <= n; i ++)
        {
          results[i] = results[i-1] + results[i-2];
        }
        System.out.println("f(" + n + ") = " + results[n]);
      }
    }
    while ((0 < n) && (n < 100));

  } // end of main()

} // end of class