Как вычислять Числа Фибоначчи с помощью Разделяй и Властвуй?

Question

[Jairman]

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

Само задание:

Comments

[xmoonlight]

Откуда такие задания?
Огласите весь список, пожалуйста! :)

[Jairman]

xmoonlight, куда вам написать?)

[Jairman]

xmoonlight, вообще это нам в школе задают, некоторые я и без подсказок делаю, а остальные требуют гугления и кучи вопросов

[tsarevfs]

Я думаю от вас хотят рекурсивное решение, которое явным образом из определения получается.

[xmoonlight]

Jairman, сюда напишите: линк или книга/учебник какая?

[T_g]

xmoonlight, просто пачка задачек по теме:
https://docs.google.com/document/d/1sl8PnHRFl9iEzk...

[Mikhail Osher]

google "divide and conquer fibonacci". намного проще в гугле результат найти, чем тут спрашивать

[T_g]

tsarevfs, среди формул есть первая и четвертая, дающие вполне себе логарифмическое решение в стиле разделяй и властвуй.

[xmoonlight]

T_g, Спасибо, я прочитал все задания.
Это одна единственная задача, разделённая на мелкие части.

Jairman,

вообще это нам в школе задают, некоторые я и без подсказок делаю, а остальные требуют гугления и кучи вопросов

Это действительно школьные домашние задания?!
И труд детей так сегодня эксплуатируют?

[T_g]

xmoonlight, Да, школьные). А что не так с трудом? Эти задачки писать час-полтора. А если не могут разобраться, вполне могут ко мне подойти, обсудить.

[xmoonlight]

T_g, А Вы - препод?)

[xmoonlight]

T_g,

Ага

Понял.
И в каком классе это должны делать сегодня ученики, да ещё и с ред-лайном?

[T_g]

xmoonlight, ага

[xmoonlight]

T_g, Для какого класса школы задания-то?)))

[T_g]

xmoonlight, десятки.

[longclaps]

среди формул есть первая и четвертая,

T_g, первая и четвертая, она же вывернутая первая ) К чему деток заставлять штаны надевать через голову, есть же быстрый итеративный алгоритм:

def fib(n):
    a, b, c = 1, 0, 1
    for ch in f'{n:b}':
        a, b, c = a * a + b * b, (a + c) * b, b * b + c * c
        if ch == '1':
            a, b, c = a + b, a, b
    return b

[xmoonlight]

longclaps, это не ДЗ.

[xmoonlight]

T_g, Ну, тогда сдвигайте редлайн до бесконечности))
Кстати, эта задача (ту, что Вы решаете) - решается не сложностью, а функциональным пересечением. (если Вы препод - то поймёте)

[longclaps]

xmoonlight, да пофиг, все эти тождества тупо проступают здесь,
a = a * a + b * b
не похоже ли на кое-что?
Так зачем натирать себе мозгИ рекурсией? Чай не на хаскель задача.

[xmoonlight]

longclaps, Именно про это я и написал выше)

[longclaps]

T_g, рэбе, вы нас оставили? Отчего разделять и властвовать нельзя в более изящных рамках:

def fib(n, a=1, b=0):
    return fib(n - 1, a + b, a) if n else b

[T_g]

longclaps, итеративный алгоритм - просто матричная формула с бинарным возведением в степень. По факту, реккурент раскрытый динамикой.
А вот использование явной формулы дает плохую оценку времени.
Вообще, ограничений в этой задачке нет, так что полный простор для творчества. Эта задачка включена в дз, чтобы разбирались в разных подходах, а не лепили сразу знакомый, да и учились оценивать алгоритм на адекватность.

[longclaps]

T_g, я понимаю, что вы понимаете специфику предложеных решений. Просто идея скрестить ужа с ежом, фибоначи с рекурсией, порождает либо ублюдка О(expN), либо унылую, но с какой-то идеей линейность, либо крокодила на базе тождества №1.

[Александр Алексеев]

Я не понял, нужно заполнить массив числами фибоначчи или вычислить конкретное число под заданным номером? В первом случае задача всё равно решается за линейное время, а для второго есть формула общего члена последовательности фибоначчи. Первый случай ещё можно распараллелить на разных ядрах или GPU.

[Jairman]

ntllct, в задаче всё написано

Answer 1

[Mylistryx]

Вычисление числа Фибоначчи не обязательно реализуется через рекурсию! Если автор пролюбил все занятия по вышке, то ненадо делать за него "лабу". Правилами вроде запрещено запрашивать рения мат.задач.

https://habr.com/ru/post/261159/

Comments

[Jairman]

Если бы вы прочитали задачу, то вы бы поняли, что нужен алгоритм "Разделяй и Властвуй", поэтому все решения с хабара тут не подойдут. Вообще это простая задача, нам нужно использовать формулы 1 и 4, чтобы вызывать рекурсию.

[Jairman]

И поясните мне, что такое занятия по по вышке? Да и решение мне не надо было, нужна была подсказка.

[Mylistryx]

Jairman, а я собственно что сделал?

[Jairman]

Mylistryx, ну, вы в любом случае не помогли бы мне

[Jairman]

Mylistryx, понимаете, нужно решить задачу не любым способом, а нужным

[Mylistryx]

Ну напишите unit test, или вы хотите чтоб я написал за вас? 1750р/час, 1000 - наценка за наглость.

[Jairman]

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

[Mylistryx]

Но тем не менее... Вопрос был задан - я дал ответ, вы не поняли, что-же ваше решение (которого никто не увидел). И изначально это было на 1-2й лаб.работе, 17 лет прошло...

[Jairman]

Ахахахах

[Jairman]

Mylistryx, Я вам уже сколько пытаюсь объяснить, что ваше решение не для этой задачи. А моё решение, которое никто не просил и которое никому не нужно, лежит на гитхабе.
Про какие 17 лет и про какие лаб работы вы говорите я вообще не понимаю

[h8nor]

Вторая строка в поиске https://habr.com/post/423939/ на javascript