Python程序查找第n个斐波那契数|极客笔记

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

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

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

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

F n = Fn-1 + Fn-2

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

使用递归查找第n个斐波那契数
使用动态规划查找第n个斐波那契数
使用动态规划和空间优化查找第n个斐波那契数
使用数组查找第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

解释：

在上面的代码片段中，我们定义了一个函数： 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 条件语句。在这些语句中，斐波那契数的值被存储在一个变量中。借助递归，重复的加法操作使我们能够获得这个斐波那契数。

让我们通过以下示例来理解这一概念。

示例：

# 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

解释：

在上面的代码片段中，我们定义了一个名为 Fibonacci_series() 的函数，它接受变量 x 作为参数。我们创建了一个一维数组 fib_Array ，其数据元素为 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 ，我们使用了 for循环 的 i 在范围 (2, x + 1) 内。我们使用变量 o 来存储数列中前两个元素的和。一旦 o 的值等于 m + n ，则重新分配 m 的值为 n 。随后，将 n 的值重新分配为 o 的值。这个过程继续进行，直到循环终止。一旦循环终止，函数返回存储第n个斐波那契数的 n 的值。

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

在这种方法中，我们通过使用 for循环 反复相加来创建一个大小为 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循环 将系列元素添加到数组中，通过重复相加前面两个元素。最后，第n个元素被返回并打印给用户。

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