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

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

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

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

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

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

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

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

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

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

Jairman,

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

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

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

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

T_g,

Ага

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

xmoonlight, ага

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

xmoonlight, десятки.

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

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

longclaps, это не ДЗ.

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

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

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

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

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

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

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

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

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