Задача по алгоритмам

307

08 марта 2018, 11:13

Всем привет. Вот задача :

Главный вопрос - как найти индекс нулевого элемента и что делать если их два. Если найти нулевой индекс задачу можно считать решенной. Итак что мы имеем :

По формулам я вывел что, h[ n ] = h[ 1 ]n - h[ 0 ](n-1) + n*(n-1). Т.е. очень легко найти любой элемент если знаешь h[ 1 ], а h[ 0 ] высчитывать не нужно, это высота гирлянды конца А, n - индекс элемента, которого хочешь найти.
Если приравнять h[ n ] = 0, тогда останутся 2 неизвестные В и n. Я так понимаю, их и нужно найти методом дихотомии. Отсюда B = (h[ 0 ] * (n-1) - n*(n-1))/n. Ок. Каким образом находить n?
Продолжение второго : Получаются такие значения, отрицательные показаны красным, положительные синим. Подскажите пжлст как вы видите решение, не нужно реализовывать, я сам все напишу

Answer 1

Собственно все что вам нужно, кроме вышеуказанных формул - это сам бинарный поиск. Дело в том, что какой-то формулы, для нахождения n нет. Нужно его искать путем перебора, но, так как n может быть давольно большим числом, перебор от 0 до самого последнего элемента не эффективен. Просто берете среднее midle между left = 0 и right = n(max) и выводите B. После этого проверяете в какую сторону надо двигаться? Для этого находите элементы правее и левее вашего нулевого элемена h[n]. Если они оба выше 0 (ну или один из них также равен 0), то поздравляю - вы пополи в точку - это тот самый n. Но если левый элемент меньше 0, то это означает, что n находится левее, так что теперь ищем в диапазоне left до right = midle. Если наоборот, то в диапазоне left = midle до right.