Числа Фибоначчи: циклом и рекурсией

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих: 1, 1, 2, 3, 5, 8, 13, ... . Иногда ряд начинают с нуля: 0, 1, 1, 2, 3, 5, ... . В данном случае мы будем придерживаться первого варианта.

Формула:

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2

Пример вычисления:

F3 = F2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F5 = F4 + F3 = 3 + 2 = 5
F6 = F5 + F4 = 5 + 3 = 8
...

Вычисление n-го числа ряда Фибоначчи с помощью цикла while

  1. Присвоить переменным fib1 и fib2 значения двух первых элементов ряда, то есть присвоить переменным единицы.
  2. Запросить у пользователя номер элемента, значение которого он хочет получить. Присвоить номер переменной n.
  3. Выполнять следующие действия n - 2 раз, так как первые два элемента уже учтены:
    1. Сложить fib1 и fib2, присвоив результат переменной для временного хранения данных, например, fib_sum.
    2. Переменной fib1 присвоить значение fib2.
    3. Переменной fib2 присвоить значение fib_sum.
  4. Вывести на экран значение fib2.

Примечание. Если пользователь вводит 1 или 2, тело цикла ни разу не выполняется, на экран выводится исходное значение fib2.

fib1 = 1
fib2 = 1
 
n = input("Номер элемента ряда Фибоначчи: ")
n = int(n)
 
i = 0
while i < n - 2:
    fib_sum = fib1 + fib2
    fib1 = fib2
    fib2 = fib_sum
    i = i + 1
 
print(fib2)

Компактный вариант кода:

fib1 = fib2 = 1
 
n = int(input("Номер элемента ряда Фибоначчи: ")) - 2
 
while n > 0:
    fib1, fib2 = fib2, fib1 + fib2
    n -= 1
 
print(fib2)

Вывод чисел Фибоначчи циклом for

В данном случае выводится не только значение искомого элемента ряда Фибоначчи, но и все числа до него включительно. Для этого вывод значения fib2 помещен в цикл.

fib1 = fib2 = 1
 
n = int(input())
 
if n < 2:
    quit()
 
print(fib1, end=' ')
print(fib2, end=' ')
for i in range(2, n):
    fib1, fib2 = fib2, fib1 + fib2
    print(fib2, end=' ')
 
print()

Пример выполнения:

10
1 1 2 3 5 8 13 21 34 55 

Рекурсивное вычисление n-го числа ряда Фибоначчи

  1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
  2. Во всех остальных случаях вызвать эту же функцию с аргументами n - 1 и n - 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.
def fibonacci(n):
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
 
 
print(fibonacci(10))

Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

Комментарии

Я бы использовал yield при таких вычислениях, намного быстрее(даже не так, а вот так НАМНОГО БЫСТРЕЕ)) и не грузит память

Большое спасибо... Однако, если с помощью цикла,то как получить fib_sum при n=0 и n=1. Именно эти величины требуется получить при изучении материала. Что же касается функции, то результат вообще ни какой. Сами понимаете - брак.