使用C++找到Pell数

1. 什么是Pell数

Pell数是一个整数数列，满足递推式 $P_n = 2 P_{n-1} + P_{n-2}$ ，其中 $P_0=0$ , $P_1=1 $。即 Pell数列的前几项如下：0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378……

Pell数与斐波那契数列非常相似，但是有一点不同，即 $P_1 = 1$，而在斐波那契数列中 $F_1 = F_2 = 1$。因此，我们也可以认为Pell数是一个以比 $F_n$ 略大的增长速度增长的数列。

2. 如何使用C++找到Pell数

2.1 初步思路

我们可以用C++语言来计算Pell数列。初步思路是使用递归函数来计算每个Pell数。但是，此方法的效率非常低，因为递归计算会导致重复计算。例如，上一个Pell数是$P_{n-1}$，而上一个上一个Pell数是$P_{n-2}$，但在计算 $P_n$ 时，“$P_{n-1}$”和“$P_{n-2}$”的计算要在两次递归中进行。这将导致很多重复计算，从而降低计算速度。

2.2 迭代算法

解决上述问题的一种方法是使用迭代算法而不是递归算法。使用迭代算法，我们可以按顺序计算每个Pell数并将其存储在数组中。开始时，我们将数组中的前两个值设置为 0 和 1。然后，我们使用for循环迭代下一个Pell数，直到达到所需的数量。

在以下例子中，我们使用迭代算法来计算前50个Pell数。请注意，数组 calcPell 中存储了这些Pell数。

#include <iostream>
using namespace std;
int main()
{
    const int LENGTH = 50;
    long long calcPell[LENGTH];
    calcPell[0] = 0;
    calcPell[1] = 1;
    for (int i = 2; i < LENGTH; i++)
        calcPell[i] = 2 * calcPell[i-1] + calcPell[i-2];
    for (int i = 0; i < LENGTH; i++)
        cout << calcPell[i] << " ";
    return 0;
}

该程序的输出如下：

0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 471744 1140577 2758074 6658579 16075268 38809017 93693112 226195935 546083620 1318363233 3182810396 7683984019 18550778438 44785540833 108121860374 261029260187 630180382797 1521390029800 3672960431993 8867310888970 21407582209977 51620183103812 124560285596669 300769342716304 726055463028033 1753120035317386 4238593155705973 10230077228695500 24704331319480805 59628149022179814 144079707346488005 347876536323369524 840792938347034117 2029277577519183424 4902026580844370405

2.3 优化迭代算法

我们还可以使用额外的技巧来优化迭代算法。首先，我们可以使用常量和变量来存储迭代次数和存储数组值的位置。其次，我们可以使用两个变量来存储上一次计算的结果，避免对数组的访问。这将略微提高算法的速度。

以下是带有优化迭代算法的完整C ++代码。

#include <iostream>
using namespace std;
const int LENGTH = 50;
int main()
{
    long long a = 0, b = 1, c;
    for (int i = 0; i < LENGTH; i++)
    {
        cout << a << " ";
        c = 2 * b + a;
        a = b;
        b = c;
    }
    return 0;
}

输出与前一个例子相同：

0 1 2 5 12 29 70 169 408 985 2378 5741 13860 33461 80782 195025 471744 1140577 2758074 6658579 16075268 38809017 93693112 226195935 546083620 1318363233 3182810396 7683984019 18550778438 44785540833 108121860374 261029260187 630180382797 1521390029800 3672960431993 8867310888970 21407582209977 51620183103812 124560285596669 300769342716304 726055463028033 1753120035317386 4238593155705973 10230077228695500 24704331319480805 59628149022179814 144079707346488005 347876536323369524 840792938347034117 2029277577519183424 4902026580844370405

3. 总结

本文介绍了Pell数，并提出了用C++计算Pell数列的方法，包括使用递归算法和迭代算法。虽然递归算法是一种简单方法，但迭代算法是一种更有效的算法。优化算法可以进一步提高速度。