Блог

В математических терминах последовательность Fn чисел Фибоначчи определяется рекуррентным соотношением

Fn = Fn-1 + Fn-2

С начальными значениями

F0 = 0 и F1 = 1.

Способ 1 ( Используйте рекурсию ) :

# Function for nth Fibonacci number

def Fibonacci(n):
	if n<= 0:
		print("Incorrect input")
	# First Fibonacci number is 0
	elif n == 1:
		return 0
	# Second Fibonacci number is 1
	elif n == 2:
		return 1
	else:
		return Fibonacci(n-1)+Fibonacci(n-2)

# Driver Program

print(Fibonacci(10))

# This code is contributed by Saket Modi

Выход:

34

Метод 2 ( Используйте Динамическое программирование ) :

# Function for nth fibonacci number - Dynamic Programming
# Taking 1st two fibonacci numbers as 0 and 1

FibArray = [0, 1]

def fibonacci(n):
	if n<0:
		print("Incorrect input")
	elif n<= len(FibArray):
		return FibArray[n-1]
	else:
		temp_fib = fibonacci(n-1)+fibonacci(n-2)
		FibArray.append(temp_fib)
		return temp_fib

# Driver Program

print(fibonacci(9))

# This code is contributed by Saket Modi

Выход:

21

Метод 3 ( Используйте динамическое программирование с оптимизацией пространства) :

# Function for nth fibonacci number - Space Optimisation
# Taking 1st two fibonacci numbers as 0 and 1

def fibonacci(n):
	a = 0
	b = 1
	if n < 0:
		print("Incorrect input")
	elif n == 0:
		return a
	elif n == 1:
		return b
	else:
		for i in range(2, n):
			c = a + b
			a = b
			b = c
		return b

# Driver Program

print(fibonacci(9))

# This code is contributed by Saket Modi

Выход:

21

Способ 4 ( С использованием Массивов ) :

# creating an array in the function to find the nth number in fibonacci series. [0, 1, 1, ...]

def fibonacci (n):
if n<= 0:
	return "Incorrect Output"
data = [0, 1]
if n > 2:
		for i in range (2, n):
			data.append(data[i-1] + data[i-2])
	return data[n-1]

# Driver Program

print(fibonacci(9))

# This Code is contributed by Prasun Parate (prasun_parate)

Выход :

144

Объяснение:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
как мы знаем, что у ряда Фибоначчи является суммой двух предыдущих терминов, так что если мы войдем в 12 в качестве входных данных в программу, так что мы должны вам 144 в качестве выходного. И вот что получается в результате.

Способ 5 ( С Использованием Прямой Формулы ) :

Формула для нахождения n-го числа Фибоначчи выглядит следующим образом:

# To find the n-th Fibonacci Number using formula
from math import sqrt
# import square-root method from math library
def nthFib(n):
	res = (((1+sqrt(5))**n)-((1-sqrt(5)))**n)/(2**n*sqrt(5))
	# compute the n-th fibonacci number
	print(int(res),'is',str(n)+'th fibonacci number')
	# format and print the number
	
# driver code
nthFib(12)

# This code is contributed by Kush Mehta

Выход:

144 is 12th fibonacci number