Вычислить «неправильное» N-е число Фибоначчи, если F(n) = F(n-1) + F(n-3)

@Dark_Fail · Регистрация: 23.10.2015

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

Ограничение по времени работы программы: 1 секунда
Зададим «неправильные» числа Фибоначчи, в которых n-е число равно сумме n−1-го и n−3-го. Более формально,
F0=F1=F2=1,
Fn=(Fn−1)+(Fn−3), при n>2.
Вычислите n-е «неправильное» число Фибоначчи Попробуйте реализовать рекурсивную функцию, даже если вы знаете другие (более эффективные) способы вычисления.
ВХОДНЫЕ ДАННЫЕ

Программа получает на вход одно целое число n, 0≤n≤35.
ВЫХОДНЫЕ ДАННЫЕ

Программа должна вывести одно искомое число.

ПРИМЕР
ввод
7
вывод
9

@arctblake · 09.12.2015, 08:26

Python
1
2
3
def fib(n, i=1, j=1, k=1, acc=2)
    if n = 0: return i
    else: fib(n-1, j, k, acc, acc+j)

Есть два лишних вычисления, но они ничего не стоят, и зато можно обойтись без специальных случаев

Добавлено через 1 минуту
И да, я пишу с тлф, так что проверь сам

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

Python
1
2
3
def fib(n, i=1, j=1, k=1, acc=2):
    if n < 3: return k
    else: fib(n-1, j, k, acc, acc+j)

Вот так лучше. А первом решении я в конце первой строки забыл двоеточие.

Чтобы получить ответ для n=6

Python
1
print(fib(6))

Добавлено через 8 минут
Че-то я туплю совсем. Вот так правильно

Python
1
2
3
def fib(n, i=1, j=1, k=1, acc=2):
    if n < 3: return k
    else: return fib(n-1, j, k, acc, acc+j)

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

Python
1
2
def fib(n, i=1, j=1, k=1, acc=2):
    return (k if n < 3 else fib(n-1, j, k, acc, acc+j))

@Dark_Fail · 09.12.2015, 17:10 **[ТС]**

так что из этого правильно?!?

@Nik S · 09.12.2015, 21:52

Это вам придется выяснить самостоятельно. Вы даже не поблагодарили человека, за выполненную за вас лабораторную работу, и, к тому же, если вы не в силах проверить самостоятельно эти "программы", кажется мне, что усилия человека, выполнившего за вас эту работу, напрасны.

@plan_z · 05.01.2016, 16:37

Ограничение по времени работы программы: 1 секунда
Зададим «неправильные» числа Фибоначчи, в которых nn-е число равно сумме n−1-го и n−3-го. Более формально,
F0=F1=F2=1,
Fn=Fn−1+Fn−3, при n>2.
Вычислите nn-е «неправильное» число Фибоначчи Попробуйте реализовать рекурсивную функцию, даже если вы знаете другие (более эффективные) способы вычисления.
ВХОДНЫЕ ДАННЫЕ

Программа получает на вход одно целое число nn, 0≤n≤35.
ВЫХОДНЫЕ ДАННЫЕ

Программа должна вывести одно искомое число.

ПРИМЕР
ВВОД 7
ВЫВОД 9

@arctblake · 05.01.2016, 17:07

Не по теме:

:facepalm: да Господи, это что за наглость-то такая? Типа я скопировал задание, вставил, создал тему, а дальше уже ваша забота, ребятки, давайте по-быстрому решите-ка мне. Я блин лично точно такую же задачу решил какому-то другому чуваку недавно. понабрали блин горе-студентов е-мое.

@lamed · 13.01.2016, 17:22

Python
1
2
3
4
5
6
7
8
def Fibo(n):
    if (n in {0,1,2}):
        return 1
    else:
        return Fibo(n-1)+Fibo(n-3)
 
n = int(input())
print(Fibo(n))

@arctblake · 13.01.2016, 19:20

экспоненциальный алгоритм - не лучшее решение

@Кот Ангенс · 17.01.2016, 01:03

@functools.lru_cache

Новые блоги и статьи Все статьи Все блоги /
Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .

@Dark_Fail 0 / 0 / 0 Регистрация: 23.10.2015 Сообщений: 94

	Вычислить «неправильное» N-е число Фибоначчи, если F(n) = F(n-1) + F(n-3) 08.12.2015, 19:08. Показов 5912. Ответов 8 Метки нет (Все метки) Ограничение по времени работы программы: 1 секунда Зададим «неправильные» числа Фибоначчи, в которых n-е число равно сумме n−1-го и n−3-го. Более формально, F0=F1=F2=1, Fn=(Fn−1)+(Fn−3), при n>2. Вычислите n-е «неправильное» число Фибоначчи Попробуйте реализовать рекурсивную функцию, даже если вы знаете другие (более эффективные) способы вычисления. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое число n, 0≤n≤35. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно искомое число. ПРИМЕР ввод 7 вывод 9 0

@Dark_Fail 0 / 0 / 0 Регистрация: 23.10.2015 Сообщений: 94
	09.12.2015, 17:10 [ТС]
	так что из этого правильно?!? 0

@Nik S 1 / 1 / 1 Регистрация: 08.12.2015 Сообщений: 13
	09.12.2015, 21:52
	Это вам придется выяснить самостоятельно. Вы даже не поблагодарили человека, за выполненную за вас лабораторную работу, и, к тому же, если вы не в силах проверить самостоятельно эти "программы", кажется мне, что усилия человека, выполнившего за вас эту работу, напрасны. 0

@plan_z 0 / 0 / 0 Регистрация: 27.12.2015 Сообщений: 73
	05.01.2016, 16:37
	Ограничение по времени работы программы: 1 секунда Зададим «неправильные» числа Фибоначчи, в которых nn-е число равно сумме n−1-го и n−3-го. Более формально, F0=F1=F2=1, Fn=Fn−1+Fn−3, при n>2. Вычислите nn-е «неправильное» число Фибоначчи Попробуйте реализовать рекурсивную функцию, даже если вы знаете другие (более эффективные) способы вычисления. ВХОДНЫЕ ДАННЫЕ Программа получает на вход одно целое число nn, 0≤n≤35. ВЫХОДНЫЕ ДАННЫЕ Программа должна вывести одно искомое число. ПРИМЕР ВВОД 7 ВЫВОД 9 0

@arctblake
	05.01.2016, 17:07
	Не по теме: :facepalm: да Господи, это что за наглость-то такая? Типа я скопировал задание, вставил, создал тему, а дальше уже ваша забота, ребятки, давайте по-быстрому решите-ка мне. Я блин лично точно такую же задачу решил какому-то другому чуваку недавно. понабрали блин горе-студентов е-мое. 0

@arctblake 51 / 51 / 18 Регистрация: 03.12.2015 Сообщений: 167
	13.01.2016, 19:20
	экспоненциальный алгоритм - не лучшее решение 0

@Кот Ангенс 320 / 270 / 128 Регистрация: 24.05.2012 Сообщений: 629
	17.01.2016, 01:03
	`@functools.lru_cache` 0