Sequenz mit Rekursion erzeugen

Question

Ich versuche 1 2 5 9 16 27 ... zurück zu geben ... 9 = 5 + (5-2) + (2-1), 16 = 9 + (9-5) + (5-2), und so weiter. Ich gebe es zurück, weil ich es in einer anderen Funktion verwenden muss. Ich bekomme immer noch den Hang der Rekursion, so kann ich nicht für das Leben von mir herausfinden, wie man das richtig macht. Hier ist, was ich versucht habe, so weit:

int sequence(int n) 
{ 
    if(n<=2) return n; 
    else if(n==3) return 5; 
    return sequence(n-1)+((sequence(n-1)-sequence(n-2))+((sequence(n-2)-sequence(n-3)))); 
} 

Edit: Ich dies sollte eine einzelne Zahl zurück, die ersten drei Elemente gegeben.

Answer 1

Sie schrieben tatsächlich sequence(n-2)+sequence(n-3) statt sequence(n-2)-sequence(n-3) (man beachte das + Zeichen statt -)

Wenn Sie sehen, Sie müssen nicht wirklich sequence(n - 2) aufrufen, da -sequence(n - 2) und +sequence(n - 2) ausschneiden und den Ausdruck nur sequence(n-1) + sequence(n-1) - sequence(n-3)

verlassen

Und Sie rekursiv mit n - 1 mehr als einmal aufrufen, können Sie einige Laufzeit speichern, rufen Sie es nur einmal und speichern Sie das Ergebnis in einer Variablen und verwenden Sie es zweimal.

int sequence(int n) 
{ 
    if(n<=2) 
     return n; 
    else if(n==3) 
     return 5; 
    int nMinus1 = sequence(n - 1); 
    int nMinus3 = sequence(n - 3); 
    return nMinus1 + nMinus1 - nMinus3; 
} 

Sehen Sie diese Implementierung live here.

Aber ich würde wirklich empfehlen, dynamische Programmierung zu verwenden, um vorherige Ergebnisse zu speichern und sie zu verwenden, da es die Laufzeit drastisch reduzieren wird. Aber wenn Sie Rekursion verwenden müssen und nicht einfach iterieren können, um die Sequenz zu berechnen, können Sie sicher so etwas tun.

class SequenceGenerator{ 
private: 
    static std::vector<int> results; 
public: 
    static int getNthInSequence(int n){ 
     if (results.size() == 0){ 
      results.push_back(0); // just to ignore the 0 index 
      results.push_back(1); 
      results.push_back(2); 
      results.push_back(5); 
     } 
     if (n < results.size()) 
      return results.at(n); 

     int nMinus1 = getNthInSequence(n - 1); 
     int nMinus3 = getNthInSequence(n - 3); 

     int result = nMinus1 + nMinus1 - nMinus3; 
     results.push_back(result); 
     return result; 
    } 
}; 

std::vector<int> SequenceGenerator::results; 

Here is a live demo.

Answer 2

Sobald Sie die Mathematik richtig, hier ist eine Implementierung mit minimalen Änderungen an Ihr

int sequence(int n) 
{ 
    if(n<=2) return n; 
    else if(n==3) return 5; 

    return 2 * sequence(n-1) - sequence(n-3); 
} 

Answer 3

f(n) = 2 * f(n - 1) - f(n - 2) 
f(1) = 2 
f(0) = 1

Bitte überprüfen Sie dies, es funktioniert für mich:

#include <cstdio> 

int suite_(int i){ 
    if(i == 0) 
     return 1; 

    if(i == 1) 
     return 2; 

    if(i == 2) 
     return 5; 

    return (2 * suite_(i -1) - suite_(i-3)); 
} 

void main(){ 
    int j = 0; 
    for (j=0; j < 10; ++j){ 
     printf("\nRes : %d",suite_(j)); 
    } 
} 

Ergebnisse:

Res for 0: 1 
Res for 1: 2 
Res for 2: 5 
Res for 3: 9 
Res for 4: 16 
Res for 5: 27 
Res for 6: 45 
Res for 7: 74 
Res for 8: 121 
Res for 9: 197 
Res for 10: 320 
Res for 11: 519 
Res for 12: 841 
Res for 13: 1362 
Res for 14: 2205 
Res for 15: 3569 
Res for 16: 5776 
Res for 17: 9347 
Res for 18: 15125 
Res for 19: 24474