使用 C++ 查找佩尔数
c++server side programmingprogramming
在给定的问题中，我们给定一个整数 n，我们需要找到 Pn，即该位置的佩尔数。现在，正如我们所知，佩尔数是通过以下公式给出的一系列的一部分 −Pn = 2*Pn-1 + Pn-2
前两个起始数字 − P0 = 0 和 P1 = 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) // 如果 n <= 2，我们打印 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 个 pell 号的问题。我们还学习了此问题的 C++ 程序以及解决此问题的完整方法(常规和高效)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。
