Задачка про поиск точки разрыва на проводе

[Dmitriy40]

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

-- 27.03.2017, 15:58 --

Для начала можно например здесь посмотреть вывод "метода золотого сечения".

[Poika]

Прочитал про золотое сечение, посидел подумал, и кажется, что действительно деля отрезок на 2 неравные части в соотношении золотого сечения, набыстрейшим образом найдем участок содержащий разрыв. Но как это обосновать? Возможно ли это доказать математически? Я уверен, что это уже доказали, но нигде не могу найти доказательства.
Сейчас еще нашел теорию итераций Ньютона, кажется она тоже решает моюзадачу, но пока не разобрался как она работает.

[Dmitriy40]

Poika в сообщении #1204037 писал(а):

набыстрейшим образом

Если я правильно понимаю, то не наибыстрейшим, а в большинстве случаев немного быстрее деления пополам. Но зато в некоторых худших случаях - во столько же раз медленнее его же. Иногда худший случай важнее наиболее вероятного.

Метод Ньютона же использует дополнительную информацию (производную) о поведении функции для выбора следующей точки деления отрезка. В вашем случае такой информации нет. Ваша задача больше похожа на поиск значения в отсортированном массиве, чем на поиск нуля (минимума/максимума) функции. И эквиваленты они становятся лишь как раз при отсутствии дополнительной информации о функции.

[Poika]

Да, я тут подумал, и пришел к выводу, что делить пополам лучше чем золотым сечением.
Надо еще подумать про метод итераций Ньютона.
К какому бы решению я бы не пришел, очень хотелоось бы иметь его математичекой доказательство...

[Dmitriy40]

Да вроде не так уж это сложно.
Пойдите с конца, с последнего цикла проверки кусочков. Предположим рассматриваем разбиение на одинаковые кусочки числом $n$. Тогда в худшем случае надо провести $n-1$ измерений для каждого шага разбиения. В лучшем случае 1, в среднем (наиболе вероятно) $n/2$. Задайтесь минимальным размером кусочка (=1). Тогда на последнем цикле разбиений длина всех кусочков будет $n$. На предпоследнем цикле размер будет уже $n^2$, а общее количество проверок $2(n-1)$ (в худшем случае). Ещё на цикл ранее размер уже $n^3$, количество проверок $3(n-1)$. Зависимость легко прослеживается. Ну а всего циклов разбиений будет $L \le n^k$, $k$ - количество циклов разбиений. Отсюда $k=\log_n L$, а количество проверок $k(n-1)=(n-1)\log_n L$. Что при фиксированном $L$ как раз и приводит к формуле Legioner93. Правда если $L$ не является точной степенью $n$, то возможны варианты разбиений, но в любом случае $n=2$ останется оптимальным.
Для разбиений на неравные кусочки доказательство будет примерно аналогичным, только задействуются ещё и вероятности нахождения обрыва в каждой из частей разбиения. Ну и результат получится чуть другим (если я не ошибся, то как раз разбиение на два кусочка в пропорции золотого сечения будет оптимальным).
PS. Это не полноценное доказательство, в паре мест я походу "срезал путь", но как основа пойдёт.

[Poika]

Спасибо большое за помощь! Я понял Ваше доказательство.