47 lines
1.1 KiB
Java
47 lines
1.1 KiB
Java
import java.util.HashMap;
|
|
import java.util.Map;
|
|
|
|
public class HofQ {
|
|
private static Map<Integer, Integer> q = new HashMap<Integer, Integer>(){{
|
|
put(1, 1);
|
|
put(2, 1);
|
|
}};
|
|
|
|
private static int[] nUses = new int[100001];//not part of the task
|
|
|
|
public static int Q(int n){
|
|
nUses[n]++;//not part of the task
|
|
if(q.containsKey(n)){
|
|
return q.get(n);
|
|
}
|
|
int ans = Q(n - Q(n - 1)) + Q(n - Q(n - 2));
|
|
q.put(n, ans);
|
|
return ans;
|
|
}
|
|
|
|
public static void main(String[] args){
|
|
for(int i = 1; i <= 10; i++){
|
|
System.out.println("Q(" + i + ") = " + Q(i));
|
|
}
|
|
int last = 6;//value for Q(10)
|
|
int count = 0;
|
|
for(int i = 11; i <= 100000; i++){
|
|
int curr = Q(i);
|
|
if(curr < last) count++;
|
|
last = curr;
|
|
if(i == 1000) System.out.println("Q(1000) = " + curr);
|
|
}
|
|
System.out.println("Q(i) is less than Q(i-1) for i <= 100000 " + count + " times");
|
|
|
|
//Optional stuff below here
|
|
int maxUses = 0, maxN = 0;
|
|
for(int i = 1; i<nUses.length;i++){
|
|
if(nUses[i] > maxUses){
|
|
maxUses = nUses[i];
|
|
maxN = i;
|
|
}
|
|
}
|
|
System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");
|
|
}
|
|
}
|