Задача питон числа фибоначчи

Задача «Числа Фибоначчи»

Добрый день! Объясните, пожалуйста, на пальцах, как работает этот код. Я смотрю по компилятору (например для цифры 6) и, все равно, не понимаю, как он отрабатывает. Ответ он выдает правильный.

Условие
Напишите функцию fib(n), которая по данному целому неотрицательному n возвращает n-e число Фибоначчи. В этой задаче нельзя использовать циклы — используйте рекурсию.

def fib(n): if n == 1 or n == 2: return 1 else: return fib(n - 1) + fib(n - 2) print(fib(int(input())))

Если что, это не мое решение, но мне интересно разобраться.

Мое решение более костыльное:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

def fib(n): global index_0 global index_1 global i global index_n index_n = index_0 + index_1 i += 1 index_0, index_1 = index_1, index_n if n == 1: return(1) elif i != n: return fib(n) else: return index_n index_0 = 0 index_1 = 1 i = 1 index_n = 0 print(fib(int(input())))

Задача про числа Фибоначчи
Добрый день, у меня возникла проблема с решением задачи: "Даны целые числа от 1 до 50. Определить.

Задача 7. «Числа Фибоначчи»
Задание: Написать функцию Fib(N) вычисляющую N-е число последовательности Фибоначчи. Всё это надо.

Введите размер массива N и заполните массив из N элементов числами Фибоначчи. Первые два числа Фибоначчи равны 1, а кажд
Введите размер массива N и заполните массив из N элементов числами Фибоначчи. Первые два числа.

Задача (числа фибоначчи)
Найти количество чисел Фибоначчи на промежутке от m до n, которые делятся на 3.

Задача на Числа Фибоначчи
Числа Фибоначчи определяются по следующему закону: a1=1, a2=1, an+1=an+an-1. Суммировать подряд.

Сообщение было отмечено seregahlevnoj как решение

Решение

Сообщение от seregahlevnoj

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

def fib(n,c=0,p=1): # Обычная рекурсия if (n==0): return c else: return fib(n-1, c+p,c) def fibg(): # Генератор c,p=0,1 while (True): q=c+p yield q p=c c=q fib_gen=fibg() for i in range(1,31): print(i,next(fib_gen))

Если n больше двух, то приходится вычислять два предыдущих числа Фибоначчи и их складывать. Вычислять можно при помощи той же самой функции, но с другим параметром. Единственная логическая трудность здесь та, что мы обращаемся к функции, которая еще не закончила прежнюю работу. Можно это представить себе так, что у функции может быть несколько работ, которые она может приостанавливать и переходить к какой-нибудь другой существующей работе или же начать новую работу. Или можно считать, что написано много вариантов функции с разными именами. Каждый раз, когда надо обратиться к функции мы выбираем тот вариант, который не занят работой.

В задаче рекурсия в рекурсии

Добавлено через 33 секунды

Сообщение от Infeeqs

В задаче рекурсия в рекурсии

Добавлено через 11 минут

Сообщение от palva

Если n больше двух, то приходится вычислять два предыдущих числа Фибоначчи и их складывать. Вычислять можно при помощи той же самой функции, но с другим параметром. Единственная логическая трудность здесь та, что мы обращаемся к функции, которая еще не закончила прежнюю работу. Можно это представить себе так, что у функции может быть несколько работ, которые она может приостанавливать и переходить к какой-нибудь другой существующей работе или же начать новую работу. Или можно считать, что написано много вариантов функции с разными именами. Каждый раз, когда надо обратиться к функции мы выбираем тот вариант, который не занят работой.

Я понимаю, что вы хотите сказать. Однако, на пальцах , как отрабатывает программа мне не ясно. Я через компилятор пытаюсь отследить и вижу следующее.
Как только n = 2 или 1, то функция принимает значение 1, тем самым, как бы, съедая, эти значения. Потом происходит рекурсия в рекурсии и процесс повторяется.
n=
6
5
4
3
2 — процесс пошел
первый раз оно съедает до 3х, потом до 4х, а потом магическим образом выводит ответ — в итоге таки доходит до суммы двух предыдущих значений.
Я только начал изучать рекурсию. Мне не ясно, куда деваются все эти «съеденные» значения функции. В задачах перед этим с подобным выводом выводится сумма значений.

Добавлено через 11 минут

Сообщение от Catstail

Благодарю, немного помучился с заданием переменных через global. Не знал, что можно прямо в функции задать так параметры и return. Так просто выглядит.

За генератор также спасибо!

seregahlevnoj, Когда вы печатаете переменные из программы, то программа использует те значения, которые относятся к работе, которую она выполняет. Для каждого входа в программу создается контекст исполнения (работа), которая содержит значения параметров, локальных переменных и место, на которой работа была прервана. После выхода из программы контекст уничтожается (затирается контекстами других работ) Так что у параметров и переменных одновременно существует много разных значений в разных контекстах.

Источник

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

Числа Фибоначчи – это ряд чисел, в котором каждое следующее число равно сумме двух предыдущих.

Иногда ряд начинают с нуля.

В данном случае мы будем придерживаться первого варианта.

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

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

Получим от пользователя номер элемента, значение которого требуется вычислить. Присвоим номер элемента переменной n .

Поскольку значения первых двух элементов ряда Фибоначчи нам уже известны и вычисления начинаем с третьего, количество проходов по телу цикла должно быть на 2 меньше значения n , то есть n — 2 .

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

1. Сложить fib1 и fib2 , присвоив результат переменной для временного хранения данных, например, fib_sum .
2. Переменной fib1 присвоить значение fib2 .
3. Переменной fib2 присвоить значение fib_sum .

После окончания работы цикла вывести значение 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)

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

Номер элемента ряда Фибоначчи: 10 Значение этого элемента: 55

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

Вывод ряда чисел Фибоначчи с помощью цикла for

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

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

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.

Источник

Рекурсивный метод нахождения чисел Фибоначчи

Программа принимает на вход число членов последовательности Фибоначчи и при помощи рекурсии вычисляет все числа, входящие в эту последовательность.

Решение задачи

1. Принимаем на вход число членов последовательности и записываем его в отдельную переменную.
2. Это число передается в качестве аргумента в рекурсивную функцию, которая будет вычислять n -й член последовательности.
3. В качестве базового условия принимаем то обстоятельство, что число членов последовательности Фибоначчи не может быть меньше единицы либо равно ей. При наступление этого условия рекурсия останавливается.
4. В противном случае функция вызывается вновь следующим образом: в качестве аргумента нашей рекурсивной функции передается введенное число, уменьшенное на единицу, и к этому прибавляется эта же функция с аргументом, уменьшенным уже на 2.
5. Каждый вызов функции возвращает одно число, которое мы потом выводим на экран.

Исходный код

Ниже дан исходный код, который осуществляет вывод всех членов последовательности Фибоначчи заданного размера. Результаты работы программы также даны ниже.

Объяснение работы программы

1. Пользователь вводит число и оно записывается в переменную n .
2. Передаем число n в качестве аргумента в рекурсивную функцию, которая вычисляет n-ый член последовательности.
3. Так как первый член последовательности Фибоначчи по определению не может быть меньше 1, в качестве базового условия принимаем n
4. В противном случае функция вызывается вновь следующим образом: fibonacci(n-1) + fibonacci(n-2) .
5. Результаты выводятся на экран при помощи цикла for .

Результаты работы программы

Пример 1: Введите число членов последовательности:5 Последовательность Фибоначчи: 0 1 1 2 3 Пример 2: Введите число членов последовательности:7 Последовательность Фибоначчи: 0 1 1 2 3 5 8

Примечания переводчика

Данный пример приведен только с целью подробного ознакомления с алгоритмами рекурсии. Как вы можете заметить, данный код крайне неэффективен и не экономичен с вычислительной точки зрения, поскольку для вычисления n-го члена последовательности нам необходимо вычислять все предыдущие. И так мы делаем ровно n раз. Когда числа n являются большими, данный код абсолютно не применим. И, разумеется, для решения этой задачи есть другие, более эффективные, алгоритмы.

Источник

Числа Фибоначчи на Python

Статьи

Введение

В статье разберём 3 способа получения ряда Фибоначчи на Python. Первые два способа будут с использованием циклов, а третий – рекурсивный.

Числа Фибоначчи – бесконечная последовательность чисел, каждое из которых является суммой двух предыдущих и так до бесконечности.

Числа Фибоначчи циклом while

Для начала создадим переменную, в которую будет вводиться длина ряда:

n = int(input('Введите длину ряда: '))

Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:

Создадим переменную i, которая будет равняться двум:

Добавим цикл, который не закончится, пока переменная i будет меньше переменной n:

Числа Фибоначчи на Python:

n = int(input('Введите длину ряда: ')) f1 = f2 = 1 print(f1, f2, end=' ') i = 2 while i < n: f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=' ') # Выводится f2 i += 1 print()

Числа Фибоначчи циклом for

Создадим переменную, в которую будет вводиться длина ряда:

n = int(input('Введите длину ряда: '))

Далее создадим две переменные (f1 и f2), которые будут равняться начальным единицам и выведем их:

Добавим цикл, который начинается с 2, и заканчивается на n:

for i in range(2, n): f1, f2 = f2, f1 + f2 # f1 приравнивается к f2, f2 приравнивается к f1 + f2 print(f2, end=' ') # Выводится f2

Числа Фибоначчи на Python:

n = int(input('Введите длину ряда: ')) f1 = f2 = 1 print(f1, f2, end=' ') for i in range(2, n): f1, f2 = f2, f1 + f2 print(f2, end=' ')

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

Для начала создадим рекурсивную функцию, назовём её fibonacci и добавим ей параметр n:

Добавим условие, что если n = 1, или n = 2, то возвращается единица, так как первый и второй элементы ряда Фибоначчи равны единице. Если же условие не срабатывает, то элементы складываются:

def fibonacci(n): if n == 1 or n == 2: # Если n = 1, или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице. return 1 return fibonacci(n - 1) + fibonacci(n - 2)

Числа Фибоначчи на Python:

def fibonacci(n): if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) n = int(input()) print(fibonacci(n))

Заключение

В данной статье мы научились вычислять n-ное число ряда Фибоначчи на Python. Надеюсь Вам понравилась статья, удачи! 🙂

Источник