public class HofstadterQ {
public static int Q(int n) {
if (n == 1)
return 1;
int[] m = new int[n];
m[0] = 1;
m[1] = 1;
for (int i = 2; i < n; i++)
m[i] = m[i - m[i - 1]] + m[i - m[i - 2]];
return m[n - 1];
}
public static void main(String[] args) {
System.out.println(Q(1000));
}
}
Hier kann man wiederum "dynamische Programmierung" anwenden, indem du dir bereits berechnete Ergebnisse von Q(i) in einem Array merkst. Da man hier kein Muster erkennen kann, auf welche vorherigen Q(k) tatsächlich zugegriffen wird, um Q(i) zu berechnen, brauchst du hier einfach ein Array der Größe `n`.
Z.B. so:
Hier machen wir uns zunutze, dass jedes `k` in `Q(k)` als Teil der Berechnung von `Q(i)` immer strikt kleiner als `i` selbst ist. Somit ist die Folge der zugegriffenen Arrayindizes strikt monoton steigend und wir können das so im Array speichern.Java:public class HofstadterQ { public static int Q(int n) { if (n == 1) return 1; int[] m = new int[n]; m[0] = 1; m[1] = 1; for (int i = 2; i < n; i++) m[i] = m[i - m[i - 1]] + m[i - m[i - 2]]; return m[n - 1]; } public static void main(String[] args) { System.out.println(Q(1000)); } }
public class Hofstadter {
private static int Q(int n) {
return Q(n, new int[n+1]);
}
private static int Q(int n, int[] c) {
if (c[n] != 0)
return c[n];
if (n == 1 || n == 2)
return 1;
return c[n] = Q(n - Q(n - 1, c), c) + Q(n - Q(n - 2, c), c);
}
public static void main(String[] args) {
System.out.println(Q(1000));
}
}