Finden Sie die Pell-Nummer mit C++

In der gegebenen Aufgabe erhalten wir eine ganze Zahl n und müssen P_n finden, was die Zaubernummer an dieser Position ist. Nun, wie wir wissen, ist eine Schreibzahl Teil einer Folge, die durch die folgende Formel gegeben wird: P_n = 2*P_n-1 + P_n-2

Die ersten beiden Startnummern – P ₀ = 0 und P₁ = 1

Methodenlösung finden

Jetzt werden wir dieses Problem mit zwei Methoden lösen: Rekursion und Iteration.

Rekursive Methode

In dieser Formel wenden wir die Formel Pell Number rekursiv an und führen n Iterationen durch.

Beispiel

#include <iostream>

using namespace std;
int pell(int n) {
   if(n <= 2)
      return n;
   return 2*pell(n-1) + pell(n-2);
}
int main() {
   int n = 6; // given n
   cout << pell(n) <<"\n"; // Pell number at that position.
   return 0;
}

Ausgabe

70

Erklärung des obigen Codes

In diesem Ansatz verwenden wir die Rekursion, indem wir pell(n-1) && pell(n-2) aufrufen, bis n kleiner oder gleich 2 ist, weil We wissen, dass die geschriebenen Zahlen bis 2 mit der angegebenen Zahl übereinstimmen. Die Gesamtzeitkomplexität des obigen Programms beträgt O(N), wobei N die angegebene Zahl ist.

Iterative Methode

Bei dieser Methode verwenden wir dieselbe Formel wie oben, verwenden jedoch eine for-Schleife anstelle einer rekursiven Funktion, um die Zahl zu berechnen.

Beispiel

#include <iostream>

using namespace std;
int main() {
   int n = 6; // given n.
   int p0 = 0; // initial value of pn-2.
   int p1 = 1; // initial value of pn-1.
   int pn; // our answer.

   if(n <= 2) // if n <= 2 we print n.
      cout << n <<"\n";
   else {
      for(int i = 2; i <= n; i++) { // we are going to find from the second number till n.

         pn = 2*p1 + p0;
         p0 = p1; // pn-1 becomes pn-2 for new i.
         p1 = pn; // pn becomes pn-1 for new i.
      }

      cout << pn << "\n";
   }
   return 0;
}

Ausgabe

70

Erklärung des obigen Codes

Im angegebenen Programm durchlaufen wir von 2 nach n und aktualisieren einfach den Wert von pn-2 auf pn-1, pn-1 Der Wert wird auf aktualisiert pn, bis n erreicht ist.

Fazit

In diesem Artikel haben wir das Problem gelöst, die N-te Zaubernummer mithilfe von Rekursion und Iteration zu finden. Wir haben auch ein C++-Programm zur Lösung dieses Problems und einen vollständigen Weg zur Lösung dieses Problems (normal und effizient) gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen Sprachen schreiben.

Das obige ist der detaillierte Inhalt vonFinden Sie die Pell-Nummer mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!