使用 C++ 查找佩尔数

在给定的问题中，我们给定了一个整数 n，我们需要找到 P _n，即该位置的_像素数。现在，正如我们所知，pell number 是由这个公式给出的系列的一部分 -P _n = 2*P _n-1 + P _n-2

前两个起始数字 - P ₀ = 0 和 P ₁ = 1

寻找解决方案的方法

现在我们将通过两种方法解决这个问题：递归和迭代。

递归方法

在这个公式中，我们将递归应用佩尔数公式并进行 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; // 给定 n
   cout << pell(n) <<"\n"; // 那个位置的佩尔号。
   return 0;
}

输出结果

70

上面代码的解释

在这种方法中，我们通过调用 pell(n-1) && pell(n-2) 来使用递归，直到 n 小于或等于 2，因为我们知道直到 2 的 pell 数与给定的数相同。上述程序的总时间复杂度为O(N)，其中 N 是给定的数字。

迭代方法

在这种方法中，我们将使用与上述相同的公式，但使用 for 循环而不是递归函数来计算数字。

示例

#include <iostream>

using namespace std;
int main() {
   int n = 6; // 给定 n.
   int p0 = 0; // pn-2 的初始值。
   int p1 = 1; // pn-1 的初始值。
   int pn; // 我们的回答。

   if(n <= 2) // if n <= 2 we print n.
      cout << n <<"\n";
   else {
      for(int i = 2; i <= n; i++) { // 我们要从第二个数字直到 n。

         pn = 2*p1 + p0;
         p0 = p1; // 对于新的 i，pn-1 变为 pn-2。
         p1 = pn; // 对于新的 i，pn 变为 pn-1。
      }

      cout << pn << "\n";
   }
   return 0;
}

输出结果

70

上面代码的解释

在给定的程序中，我们从 2 到 n 遍历，并简单地将 pn-2 的值更新为 pn-1，将 pn-1 的值更新为 pn，直到我们到达 n。

结论

在本文中，我们使用递归和迭代解决了找到第 N 个像素数的问题。我们还学习了针对这个问题的 C++ 程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。