/**
* Test of an array-based Fibonacci number calculator.
*
* @author Wayne Eberly
*/
public class Fibonacci2 {
/**
* Test of an array-based Fibonacci number calculator.
*/
public static void main(String[] args) {
System.out.println("Test of an Array-Based Fibonacci Number Calculator");
System.out.println("");
for (int i=0; i <= 40; i++){
System.out.print("n: ");
System.out.printf("%2d", i);
System.out.print("; nth Fibonacci number: ");
System.out.printf("%10d", fib(i));
System.out.println("");
}
}
/**
* Computes a specified Fibonacci number as a long integer
* iteratively, using an array to store and reuse values
* as needed.
*
*
* Precondition:
* i
is a nonnegative integer.
* Postcondition:
* Value returned is the i
th
* Fibonacci number.
*
*
* @param i Index of the Fibonacci number to be calculated
* @return The ith Fibonacci number
* @throws IllegalArgumentException If the input integer is negative
*
*/
public static long fib(int i) {
if (i<0) {
throw new IllegalArgumentException("Negative Input: " + i);
} else { // i >= 0
if (i==0) {
return 0;
} else { // i >= 1
if (i==1) {
return 1;
} else { // i >= 2
long[] A = new long[i+1];
A[0] = 0;
A[1] = 1;
for (int j=2; j <= i; j++) {
/*
* Loop Invariant:
* a) j is an integer such that 2 <= j <= i
* b) For every integer k such that
* 0 <= k <= j-1, A[k] is equal to
* the kth Fibonacci number
* Loop Variant: i-j+1
*/
A[j] = A[j-1] + A[j-2];
};
assert A[i] == sfib(i);
return A[i];
}
}
}
}
/**
* Computes a specified Fibonacci number as a long integer by a direct
* application of the recursive definition.
*
*
* Precondition:
* i
is a nonnegative integer.
* Postcondition:
* Value returned is the i
th
* Fibonacci number.
*
*
* @param i Index of the Fibonacci number to be calculated
* @return The ith Fibonacci number
* @throws IllegalArgumentException If the input integer is negative
*
*/
public static long sfib(int i) {
if (i<0) {
throw new IllegalArgumentException("Negative Input: " + i);
} else { // i >= 0
if (i==0) {
return 0;
} else { // i >= 1
if (i==1) {
return 1;
} else { // i >= 2
return sfib(i-1) + sfib(i-2);
}
}
}
}
}