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

@seregahlevnoj · Регистрация: 18.06.2020

Студворк — интернет-сервис помощи студентам

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

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

Python
1
2
3
4
5
6
7
def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)
 
print(fib(int(input())))

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

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

Python
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())))

@Infeeqs · 13.07.2020, 18:25

seregahlevnoj, изучи рекурсию и всё поймёшь

@Catstail · 13.07.2020, 18:38

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

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

- оба решения нехороши.

Python
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))

@palva · 14.07.2020, 07:53

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

@seregahlevnoj · 14.07.2020, 09:57 **[ТС]**

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

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

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

изучи рекурсию и всё поймёшь

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

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

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

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

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

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

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

def fib(n,c=0,p=1): # Обычная рекурсия
if (n==0):
return c
else:
return fib(n-1, c+p,c)

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

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

@palva · 14.07.2020, 10:54

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

@seregahlevnoj · 14.07.2020, 11:13 **[ТС]**

Благодарю, вы интересно описываете все словами. Более привычно видеть пример в коде. Тогда решение, кмк, легче воспринимается.

@palva · 14.07.2020, 21:35

seregahlevnoj, а разве у вас не было кода? Вы с него начали и попросили объяснить.

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

@Infeeqs 8 / 8 / 0 Регистрация: 15.02.2020 Сообщений: 195
	13.07.2020, 18:25
	seregahlevnoj, изучи рекурсию и всё поймёшь 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	14.07.2020, 07:53
	Если n больше двух, то приходится вычислять два предыдущих числа Фибоначчи и их складывать. Вычислять можно при помощи той же самой функции, но с другим параметром. Единственная логическая трудность здесь та, что мы обращаемся к функции, которая еще не закончила прежнюю работу. Можно это представить себе так, что у функции может быть несколько работ, которые она может приостанавливать и переходить к какой-нибудь другой существующей работе или же начать новую работу. Или можно считать, что написано много вариантов функции с разными именами. Каждый раз, когда надо обратиться к функции мы выбираем тот вариант, который не занят работой. 1

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	14.07.2020, 10:54
	seregahlevnoj, Когда вы печатаете переменные из программы, то программа использует те значения, которые относятся к работе, которую она выполняет. Для каждого входа в программу создается контекст исполнения (работа), которая содержит значения параметров, локальных переменных и место, на которой работа была прервана. После выхода из программы контекст уничтожается (затирается контекстами других работ) Так что у параметров и переменных одновременно существует много разных значений в разных контекстах. 0

@seregahlevnoj 0 / 0 / 0 Регистрация: 18.06.2020 Сообщений: 13
	14.07.2020, 11:13 [ТС]
	Благодарю, вы интересно описываете все словами. Более привычно видеть пример в коде. Тогда решение, кмк, легче воспринимается. 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	14.07.2020, 21:35
	seregahlevnoj, а разве у вас не было кода? Вы с него начали и попросили объяснить. 0

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

Решение