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

주어진 문제에서 정수 n이 주어졌고 해당 위치의 주문 번호인 P_n을 찾아야 합니다. 이제 우리가 알고 있듯이 철자 번호는 다음 공식에 의해 주어진 수열의 일부입니다 - P_n = 2*P_n-1 + P_n-2

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

Finding Method Solution

이제 이 문제를 재귀와 반복이라는 두 가지 방법으로 해결하겠습니다.

Recursive Method

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

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

위 코드 설명

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

반복 방법

이 방법에서는 위와 동일한 수식을 사용하지만 재귀 함수 대신 for 루프를 사용하여 숫자를 계산합니다.

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

위 코드 설명

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

결론

이 글에서는 재귀와 반복을 사용하여 N번째 주문 번호를 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++를 사용하여 Pell 번호 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!