Python教程-使用Python查找第n个斐波那契数的程序
在以下教程中，我们将了解如何使用Python查找第n个斐波那契数。我们可以定义斐波那契数，其中后续的数字是前两个数字的和。
斐波那契数列的前两个元素分别为0和1。我们可以通过将前两个元素相加来计算数列的第三个元素，并且将得到的第三个项为0 + 1，等于1。同样，第四个项将是第二个和第三个项的和，即1 + 1 = 2，依此类推。这种数字的序列被称为斐波那契数列。
递推关系定义了斐波那契数如下：
Fn = 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的长度，它将返回1作为x = 2的第二个数和0作为x = 1的第一个数。如果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。这些元素是斐波那契数列的第一个和第二个元素。然后，如果提供的输入（'x'）小于2，也就是数组fib_Array的长度，它将返回0作为x = 1的第一个数和1作为x = 2的第二个数。如果x的值大于2，我们使用for循环，在范围（2, x + 1）内的i中进行迭代。我们使用变量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个元素，并将其打印给用户。
