60 lines
1.4 KiB
Java
60 lines
1.4 KiB
Java
|
import java.util.ArrayList;
|
||
|
|
|
||
|
|
/**
|
||
|
|
A utility class that provide methods to compute elements of the
|
||
|
|
recursive sequence.
|
||
|
|
@author Leah Bidlake, Isaac Shoebottom (3429069)
|
||
|
|
*/
|
||
|
|
|
||
|
|
public class Seq{
|
||
|
|
|
||
|
|
/**
|
||
|
|
Recursively computes seq(n).
|
||
|
|
@param n Non-negative integer.
|
||
|
|
@return int Element n in the recursive sequence.
|
||
|
|
*/
|
||
|
|
|
||
|
|
private static ArrayList<Integer> cache;
|
||
|
|
|
||
|
|
public static int seqR(int n){
|
||
|
|
if (n == 0)
|
||
|
|
return 1;
|
||
|
|
if (n == 1)
|
||
|
|
return 5;
|
||
|
|
return seqR(n-1) + seqR(n-2);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sequence calculator using an memoization cache
|
||
|
|
* @param n The digit the sequence is to be calculated to
|
||
|
|
* @return The number in the sequence n refers to
|
||
|
|
*/
|
||
|
|
public static int seqM(int n){
|
||
|
|
if (cache == null) {
|
||
|
|
cache = new ArrayList<>();
|
||
|
|
cache.add(1);
|
||
|
|
cache.add(5);
|
||
|
|
}
|
||
|
|
|
||
|
|
if (cache.size() <= n)
|
||
|
|
cache.add(seqM(n-1) + seqM( n-2));
|
||
|
|
return cache.get(n);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* Sequence calculator using an iterative approach
|
||
|
|
* @param n The digit the sequence is to be calculated to
|
||
|
|
* @return The number in the sequence n refers to
|
||
|
|
*/
|
||
|
|
public static int seqI(int n){
|
||
|
|
int[] cache = new int[n+2]; //n+2 so seqI(0) is not out of bounds
|
||
|
|
cache[0] = 1;
|
||
|
|
cache[1] = 5;
|
||
|
|
|
||
|
|
for(int i = 2; i <= n; i++) { //i = 2 because we need to skip the first two array items
|
||
|
|
cache[i] = cache[i-1] + cache[i-2];
|
||
|
|
}
|
||
|
|
return cache[n];
|
||
|
|
}
|
||
|
|
}
|