Hofstäter Q Folge

Darknet

Bekanntes Mitglied
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;
    
    }
 

httpdigest

Top Contributor
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.
 

Darknet

Bekanntes Mitglied
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.
 

httpdigest

Top Contributor
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));
  }
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S Abwandlung der Fibonacci Folge Java Basics - Anfänger-Themen 3
berserkerdq2 Wo geschieht der "Rücksprung, bei der rekursiven Folge Java Basics - Anfänger-Themen 5
sserio Längste Collatz-Folge Java Basics - Anfänger-Themen 11
D Grösste Zahl in einer Folge herausfinden. (ULAM) Java Basics - Anfänger-Themen 9
J Rekursive Folge (a=a-1) Java Basics - Anfänger-Themen 9
GAZ Tribonacci Folge Rekursiv Java Basics - Anfänger-Themen 11
V Fibonacci Folge Java Basics - Anfänger-Themen 4
M Methoden Fibonacci-Folge Java Basics - Anfänger-Themen 6
J Fibonacci -Folge rekursiv berechnen Java Basics - Anfänger-Themen 18
S Negafibonacci Folge berechnen Java Basics - Anfänger-Themen 24
T Algortihmus: Kürzeste Folge zu einer Zahl Java Basics - Anfänger-Themen 40
G Harmonische Rekursive Folge Java Basics - Anfänger-Themen 3
M Fibonacci-Folge mit while-Schleife Java Basics - Anfänger-Themen 4
J Byte Folge erkennen Java Basics - Anfänger-Themen 5
A Gerade Terme der Fibonacci-Folge aufsummieren Java Basics - Anfänger-Themen 12
R Roboter - Helmich Folge 6 Java Basics - Anfänger-Themen 32
S rekursive folge verbessern Java Basics - Anfänger-Themen 2
H JOptionPane YES Option mit Folge? Java Basics - Anfänger-Themen 2
P Collatz-Folge mittels indirekter Rekursion Java Basics - Anfänger-Themen 8
X Problem mit Ducci-Folge Java Basics - Anfänger-Themen 7
S Fibonacci Folge Java Basics - Anfänger-Themen 34
B Element in Folge suchen Java Basics - Anfänger-Themen 7
L iterative und rekursive Folge Java Basics - Anfänger-Themen 20
N Folge verschiedener Nährwerte zur Kubikwurzel Java Basics - Anfänger-Themen 15
I Fibonacci-Folge , direkter Weg. Java Basics - Anfänger-Themen 5
J Wurzel mit einer Folge brechnen Java Basics - Anfänger-Themen 5
E Rekursive definierten Folge Java Basics - Anfänger-Themen 10
D Bit-Folge bearbeiten Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben