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

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

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

xmoonlight, десятки.

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

xmoonlight, ага

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

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

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

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

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

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

Как применить алгоритм "Разделяй и Властвуй" к неотсортированному массиву?

Мда, задачки пошли в народ. Это всего лишь упражнение на бин.поиск для десятиклашек. Кстати, оценка сложности - n log m, где m размер массива.