C++ を使用してペル番号を検索する

指定された問題では、整数 n が与えられており、その位置の呪文番号である P_n を見つける必要があります。さて、ご存知のとおり、スペル番号は次の式で与えられるシーケンスの一部です - P_n = 2*P_n-1 P_n-2

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

メソッドの解決策を見つける

Nowこの問題は、再帰と反復という 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

上記のコードの説明

このメソッドでは、 pell(n-1) && pell( n- 2) 2 までの綴りの数値は指定された数値と同じであることがわかっているため、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 まで移動し、単純に の値を更新します。 pn-2 を pn-1 に更新し、n に達するまで pn-1 の値を pn に更新します。

結論

この記事では、再帰と反復を使用して検索を解決しました。 N番目の呪文番号。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを、C、Java、Python などの他の言語で作成できます。

以上がC++ を使用してペル番号を検索するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。