C++を使用してペル数を見つける

与えられた問題では、P _nを見つけるために必要な整数nが与えられます。 、つまり、その位置のペル数。さて、私たちが知っているように、ペル数はこの式で与えられるシリーズの一部です-P _n =2 * P _n-1 + P _n-2

最初の2つの開始番号-P₀ =0およびP₁ =1

解決策を見つけるためのアプローチ

次に、再帰的アプローチと反復的アプローチの2つのアプローチでこの問題を解決します。

再帰的アプローチ

この式では、ペル数の式を再帰的に適用し、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 ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムをC、Java、Python、その他の言語などの他の言語で作成できます。