Вычислить «неправильное» 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

Новые блоги и статьи Все статьи Все блоги /
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .

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

	Вычислить «неправильное» N-е число Фибоначчи, если F(n) = F(n-1) + F(n-3) 08.12.2015, 19:08. Показов 5855. Ответов 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