Trouver le numéro de Pell en utilisant C++

Dans le problème donné, on nous donne un entier n et nous devons trouver P_n qui est le numéro de sort à cette position. Or, comme nous le savons, un numéro orthographique fait partie d'une séquence donnée par la formule suivante - P_n = 2*P_n-1 + P_n-2

Deux premiers nombres de départ - P ₀ = 0 et P₁ = 1

Finding Method Solution

Maintenant, nous allons résoudre ce problème par deux méthodes : la récursion et l'itération.

Méthode récursive

Dans cette formule, nous appliquerons de manière récursive la formule Pell Number et ferons n itérations.

Exemple

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

Output

70

Explication du code ci-dessus

Dans cette approche, nous utilisons la récursivité en appelant pell(n-1) && pell(n-2) jusqu'à ce que n soit inférieur ou égal à 2 car nous sachez que les nombres épelés jusqu’à 2 sont les mêmes que le nombre donné. La complexité temporelle globale du programme ci-dessus est O(N), où N est le nombre donné.

Méthode itérative

Dans cette méthode, nous utiliserons la même formule que ci-dessus mais utiliserons une boucle for au lieu d'une fonction récursive pour calculer le nombre.

Exemple

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

Sortie

70

Explication du code ci-dessus

Dans le programme donné, nous passons de 2 à n et mettons simplement à jour la valeur de pn-2 en pn-1, en changeant la valeur de pn-1 La valeur est mise à jour à pn jusqu'à ce que n soit atteint.

Conclusion

Dans cet article, nous avons résolu le problème de la recherche du Nième numéro de sort en utilisant la récursivité et l'itération. Nous avons également appris un programme C++ pour résoudre ce problème et une manière complète de résoudre ce problème (normale et efficace). Nous pouvons écrire le même programme dans d’autres langages, tels que C, Java, Python et d’autres langages.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!