Find Pell number using C++

In the given problem we are given an integer n and we need to find P_n which is the spell number at that position. Now, as we know, the spelling number is the part of the sequence given by the following formula - P_n = 2*P_n-1 P_n-2

First two starting numbers - P₀ = 0 and P₁ = 1

Find method solution

Now we will solve this problem in two ways: recursion and iteration.

Recursive method

In this formula, we will recursively apply the formula Pell Number and do n iterations.

Example

#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

Explanation of the above code

In this method, we pass pell(n-1) && pell( n-2) to use recursion until n is less than or equal to 2, since we know that the spelled number up to 2 is the same as the given number. The overall time complexity of the above program is O(N), where N is the given number.

Iterative Method

In this method we will use the same formula as above but use a for loop instead of a recursive function to calculate the number.

Example

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

Output

70

Explanation of the above code

In the given program, we traverse from 2 to n and simply Update the value of pn-2 to pn-1 and update the value of pn-1 to pn until n is reached.

Conclusion

In this article, we solved the search using recursion and iteration Question about the Nth spell number. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages, such as C, java, python and other languages.

The above is the detailed content of Find Pell number using C++. For more information, please follow other related articles on the PHP Chinese website!