Ich soll die 1 Milliardste Q-Zahl der Hofstadter-Folge berechnen …
Leider hält meine Implementierung nicht an. Was mache ich falsch?
public class A005185 {
public static int q(int n) {
if (n <= 2) {
return 1;
}
return q(n - q(n - 1)) + q(n - q(n - 2));
}
public static int q_cache(int n) {
int[] cache = new int[n + 2];
cache[1] = 1;
cache[2] = 1;
for (int i = 3; i <= n; i++) {
cache[i] = cache[i - cache[i - 1]] + cache[i - cache[i - 2]];
}
return cache[n];
}
public static void main(String[] args) {
for (int i = 1; i <= 20; i++) {
System.out.println("Q(" + i + ") = " + q(i));
}
System.out.println();
for (int i = 1; i <= 20; i++) {
System.out.println("Q(" + i + ") = " + q_cache(i));
}
System.out.println();
for (int i = 1; i <= 1_000_000_000; i *= 10) {
System.out.println("Q(" + i + ") = " + q_cache(i));
}
}
}