Python程序查找第n个斐波那契数

在下面的教程中，我们将了解如何使用 Python 查找第 n 个斐波那契数。我们可以定义一个斐波那契数，其中下一个数是前两个数的和。

斐波那契数列的前两个元素分别是 0 和 1。我们可以通过将前两个元素相加来计算数列的第三个元素，得到第三项为 0 + 1，等于 1。同样，第四项将是第二项和第三项的总和，即 1 + 1 = 2，依此类推。由这些数字组成的数列称为斐波那契数列。

递推关系将斐波那契数定义如下：

F_n = F_{n - 1} + F_{n - 2}

有多种方法可以使用 Python 编程语言查找第 n 个斐波那契数。其中一些如下：

1. 使用递归查找第 n 个斐波那契数
2. 使用动态规划查找第 n 个斐波那契数
3. 使用动态规划和空间优化查找第 n 个斐波那契数
4. 使用数组查找第 n 个斐波那契数

在这些方法中，最基本的是递归方法和动态方法。

让我们通过示例详细了解这些方法的工作原理。

使用递归查找第 n 个斐波那契数

递归一词用于定义自身。在 Python 这样的编程语言中，递归是指函数调用自身的进程。通过正确且恰当的代码，递归将创建一个有限循环。

让我们考虑以下代码片段以更好地理解。

示例

输出

12th Element of the Fibonacci Series: 144

说明

在上面的代码片段中，我们定义了一个名为 Fibonacci_Series() 的函数，它接受一个参数 n。

此外，我们知道斐波那契数列的前两项是 0 和 1。如果输入为 n = 1 或 n = 2（斐波那契数列的第一项或第二项），我们使用 if-else 条件语句返回 0 或 1。如果 n 的值大于 2，则函数将调用自身，输入值会减小。正如我们所见，代码返回 (Fibonacci_Series(n - 1) + Fibonacci_Series(n - 2))。在此，函数会以较小的值调用自身，直到达到 n = 1 和 n = 2 的基本值，并且我们之前知道，n = 1 返回 0，n = 2 返回 1。然后将返回的值连续相加，以生成斐波那契数列。

使用动态规划查找第 n 个斐波那契数

动态规划也利用递归；但是，它主要利用 if-else 条件语句。在这些语句中，斐波那契数的值存储在一个变量中。通过递归，重复的加法使我们能够获得这个斐波那契数。

让我们考虑以下示例来理解这一点。

示例

输出

12th Term of Fibonacci Series: 144

说明

在上面的代码片段中，我们将函数定义为 Fibonacci_series()，它接受变量 x 作为参数。我们创建了一个名为 fib_Array 的一维数组，其第零个和第一个索引处的元素为 0 和 1。然后，如果提供的输入（“x”）小于或等于 2（也等于数组 fib_Array 的长度），则对于 x = 1 返回 0 作为第一个数字，对于 x = 2 返回 1 作为第二个数字。如果 x 的值大于 2，我们使用递归调用并插入前两个数据元素。但是，我们没有直接返回第 n 个斐波那契数，而是将每个求和的元素附加到 fib_Array 数组中。最后，我们返回数组的最后一个元素（即第 n 个元素），并为用户打印该值。

使用动态规划和空间优化查找第 n 个斐波那契数

此方法与动态规划几乎完全相同。然而，动态规划利用递归来实现重复加法，而此方法则使用 for 循环。

让我们考虑以下示例来理解这一点。

示例

输出

12th element of the Fibonacci Series: 144

说明

在上面的代码片段中，我们定义了一个函数并赋值了两个变量 m = 0 和 n = 1。这些元素是斐波那契数列的第一项和第二项。然后，我们使用 if-elif-else 条件语句，其中程序对于输入值 x = 1 返回 0，对于输入值 x = 2 返回 1。如果 x 的值大于 2，我们使用 for-loop，其中 i 的范围是 (2, x + 1)。我们使用一个变量 o 来存储数列中前两个元素的总和。一旦 o 获得 m + n 的值，m 的值就会被重新赋值为 n。随后，n 的值会被重新赋值为 o 的值。这个过程会继续，并且值 3 会持续重新赋值，直到循环终止。循环终止后，函数返回 n 的值，该值存储了第 n 个斐波那契数。

使用数组查找第 n 个斐波那契数

在此方法中，我们通过使用 for-loop 进行重复加法来创建大小为 x 的数组。因此，将返回第 n 个斐波那契数。

让我们考虑以下示例来理解这一点。

示例

输出

12th element of the Fibonacci series: 144

说明

在上面的代码片段中，我们定义了函数。在函数内部，我们创建了一个数组来查找斐波那契数列的第 n 个元素。然后，我们使用 for-loop 通过重复添加前两个元素来将数列的元素添加到数组中。最后，返回第 n 个元素并为用户打印。