C++ 中使用 Pell 数查找

在数字方面，斐波那契数列和佩尔数列具有相似的递推关系。佩尔数由递推关系定义。

p(n)=2*p(n-1)+p(n-2)

它们的初始值为 p(0)=0 & p(1)=1。

以下是前几个佩尔数：0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461,... 编写一个名为 int pell(int n) 的函数来返回 P_n。

示例

为了在C++中找到佩尔数，我们可以编写一个简单的算法，该算法遍历序列并根据前两个佩尔数计算每个佩尔数。该算法可以通过两种不同的方式实现：递归或迭代。

方法一：递归方法

让我们举一个例子来说明C++中递归方法求佩尔数。

输出

Enter the position of the Pell number to find: 8
The Pell number at position 8 is: 408

说明

为了使用递归，我们 calculatePellNumber (n-1) 和 calculatePellNumber (n-2) 直到 n 等于或小于 2，因为我们知道直到 2 的佩尔数与输入相同。上述程序的总时间复杂度为 O(N)，其中 N 是指定数字。

• 函数 calculatePellNumber 使用佩尔数递推关系递归计算第 n 个佩尔数。
• 为了找到佩尔数的位置，主函数请求用户输入。
• 传入输入位置后，它调用 calculatePellNumber 函数并输出结果。

方法二：迭代方法

让我们举一个例子来说明C++中迭代方法求佩尔数。

输出

Pell number at position 10: 2378

说明

在提供的程序中，我们从 2 遍历到 n，以更新 prevprevPell (n-2) 的值到 prevPell (n-1)，以及 prevPell (n-1) 的值到 currentPell，直到达到 n。

• position 变量表示要查找佩尔数的位置。
• P(n-2) 表示初始化为 0 的 "PREVPREVPELL" 数。
• P(n-1) 表示初始化为 1 的 "PREVPELL" 数。
• 循环通过从第二个数字迭代到指定位置来确定佩尔数。
• 使用佩尔数递推关系，更新当前的佩尔数。
• 最后，打印指定位置的佩尔数。

结论

我们使用递归和迭代解决了第N个佩尔数难题。此外，我们还学习了问题的C++程序以及我们解决它的所有正常和高效方法。同样的程序可以用各种语言编写，例如 C、Java、Python 等。