C++를 사용하여 Pell 번호 찾기

주어진 문제에서 P_n을 찾는 데 필요한 정수 n이 주어집니다. , 즉 해당 위치의 펠 번호입니다. 자, 우리가 알다시피, pell number는 이 공식에 의해 주어진 시리즈의 일부입니다 -P_n =2*P_n-1 + P_n-2

처음 두 개의 시작 숫자 - P₀ =0 및 P₁ =1

해결책을 찾기 위한 접근 방식

이제 재귀 및 반복의 두 가지 접근 방식으로 이 문제를 해결할 것입니다.

재귀적 접근

이 공식에서는 Pell Number 공식을 재귀적으로 적용하고 n번 반복합니다.

예시

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

출력

70

위 코드 설명

이 접근 방식에서 우리는 2가 주어진 숫자와 같을 때까지 펠 숫자를 알고 있으므로 n이 2보다 작거나 같을 때까지 pell(n-1) &&pell(n-2)을 호출하여 재귀를 사용합니다. 위 프로그램의 전체 시간 복잡도는 O(N)입니다. , 여기서 N은 주어진 숫자입니다.

반복적 접근

이 접근 방식에서는 위와 같은 공식을 사용하지만 재귀 함수 대신 for 루프를 사용하여 숫자를 계산합니다.

예시

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

출력

70

위 코드 설명

주어진 프로그램에서 우리는 2에서 n까지 순회하고 n에 도달할 때까지 pn-2의 값을 pn-1로, pn-1을 pn으로 간단히 업데이트합니다.

결론

이 기사에서는 재귀와 반복을 사용하여 N 번째 펠 번호를 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.