Python找到第`n`个斐波那契数

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

原文：https://www.javatpoint.com/python-program-to-find-the-nth-fibonacci-number

在下面的教程中，我们将了解如何使用 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 这样的编程语言中，递归指的是函数调用自身的过程。有了正确的代码，递归将创建一个有限循环。

为了更好地理解，让我们考虑下面的代码片段。

示例:

# defining the function for Fibonacci Series
def Fibonacci_Series(n): 
    # using if-else conditional statement
    if n < 0:
        print("Oops! Incorrect input")
    # First Fibonacci number is 0
    elif n == 0: 
        return (0) 
    # Second Fibonacci number is 1 
    elif n == 1:
        return (1)
    else:
        return (Fibonacci_Series(n - 1) + Fibonacci_Series(n - 2)) 
# printing the 12th element of the Fibonacci Series
print("12th Element of the Fibonacci Series:", Fibonacci_Series(12))

输出:

12th Element of the Fibonacci Series: 144

说明:

在上面的代码片段中，我们定义了一个函数为斐波那契数列()，该函数接受一个参数为 n 。

而且，我们知道斐波那契数列的前两个元素是 0 和 1 。在输入为 n = 1 或 n = 2 (斐波那契数列的第一项或第二项)的情况下，我们使用 if-else 条件语句返回 0 或 1 。如果 n 的值大于 2 ，函数将以较低的输入值调用自身。我们可以观察到代码返回**(斐波那契数列(n - 1) +斐波那契数列(n - 2))** 。在这里，函数以较低的值调用自己，除非它达到 n = 1 和 n = 2 的基值，并且我们从前面知道， n = 1 返回 0 ， n = 2 返回 1 。然后，返回值被连续相加以产生斐波那契数列的序列。

用动态规划法求第n个斐波那契数

动态编程也使用递归；然而，它主要利用 if-els e 条件语句。在语句中，斐波那契数的值存储在一个变量中。借助递归，重复加法让我们得到这个斐波那契数。

让我们考虑下面的例子来理解同样的事情。

示例:

# defining the function to find the nth Fibonacci Number
def Fibonacci_series(x):
    # Taking First two terms of the Fibonacci Series as 0 and 1
    fib_Array = [0, 1]
    # Here, as we know that the first two terms of Fibonacci Series are 0 and 1,
    # we append the remaining values (Fibonacci numbers from index 2 to x)
    # in the array using recursion and return the last element. 
    # In the range function, we take range(2, x + 1) instead of range(2, x).
    # This is because range function in python iterates until the value
    # before the upper limit. So, if we take from 2 to x, it would only
    # iterate from second to (x - 1)th element.
    for n in range(2, x + 1):
        fib_Array.append(fib_Array[n - 1] + fib_Array[n - 2])
    return fib_Array[x]
print("12th Term of Fibonacci Series:", Fibonacci_series(12))

输出:

12th Term of Fibonacci Series: 144

说明:

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

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

这种方法几乎与动态规划完全相同。然而，动态编程利用递归来完成循环加法，而这种方法利用 for循环。

让我们考虑下面的例子来理解同样的事情。

示例:

# defing the function to return the nth element of the Fibonacci Series
def Fibonacci_series(x): 
    # assiging the variables
    m = 0
    n = 1
    # using the if-elif-else conditional statements
    if x < 0:
        print("Wrong input") 
    elif x == 0:
        return m 
    elif x == 1: 
        return n
    else:
        # using the for-loop 
        for i in range(2, x + 1): 
            o = m + n
            m = n 
            n = o 
        return n 
# printing the twelveth term of the Fibonacci Series
print("12th element of the Fibonacci Series:", Fibonacci_series(12))

输出:

12th element of the Fibonacci Series: 144

说明:

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

用数组求第n个斐波那契数

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

让我们考虑下面的例子来理解同样的事情。

示例:

# defining the function
def Fibonacci_series(x): 
  # creating an array in the function
   fib_Array = [0] * (x + 1)
   fib_Array[1] = 1
   # adding elements of the series to the array using addition of previous two elements.
   for n in range (2, x + 1):
      fib_Array[n] = fib_Array[n - 1] + fib_Array[n - 2] 
   return fib_Array[x]
if __name__ == "__main__":
   print("12th element of the Fibonacci series:", Fibonacci_series(12))

输出:

12th element of the Fibonacci series: 144

说明:

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

---