Hofstäter Q Folge

Diskutiere Hofstäter Q Folge im Java Basics - Anfänger-Themen Bereich.
D

Darknet

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;
    
    }
 
H

httpdigest

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.
 
D

Darknet

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.
Das ist eine Iterative Lösung von der Aufgabenstellung soll es Rekusiv sein.
 
H

httpdigest

Gut, diese Information war in der ursprünglichen Frage nicht gegeben. Dann schreibe halt eine rekursive Methode:
Java:
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));
  }
}
 
Thema: 

Hofstäter Q Folge

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben