Hofstäter Q Folge

Q(n) = Q(n-Q(n-1))+ Q(n-Q(n-2)) für n >2

Wie bekommt man für Q(1000) ein Ergebnis. Der Rechner Rechent bis unendlich.
Q(20) ist 12
Code:
private static int  Q(int n){
    
    if(n == 1 || n == 2) return 1;
    
    int reture = Q(n-Q(n-1))+Q(n-Q(n-2));
    return reture;
    
    }
 
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:
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));
  }
}
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.
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben