C++ を使用してペル番号を検索する-C++-php.cn

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

WBOY

リリース： 2023-08-30 18:09:06

転載

996 人が閲覧しました

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

ログイン後にコピー

出力

ログイン後にコピー

上記のコードの説明

このメソッドでは、 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;
}

ログイン後にコピー