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

[Poika]

Друзья, напишите пожалуйста, где искать решение, или как решить такую задачу.

Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.
В какомто месте произошел разрыв провода.
Что бы найти разрыв, я например могу сначала разделить провод пополам и прозвонить, определить в какой половине находится разрыв, потом поврежденную половину разделитть опять пополам и опять прозвонить и в итоге дойти, скажем до 8 участка провода длиной примерно 8 метров в котором будет разрыв.
Или я могу делить провод на трети каждый раз.
Или сначача искать участки разрыва деля каждый раз пополам и прозванивая, а потом искать третями итд.
Вопрос: На сколько частей надо каждый раз делить провод и прозванивать, чтоб наименьшим количеством разделений и прозвонов найти меленький участок (Наппример 8 метров) который будет содержать разрыв?

Если кто знает, подскажите где почитать решения подобных задач? Очень интересно!

[Aritaborian]

Оптимальнее всего делить на $e$ частей. Ну а ближайшее целое — три.

[Legioner93]

Целевая функция здесь $f(n) = \frac{n-1}{\ln{n}}$, где $n$ -- на сколько частей каждый раз делим участок.
Минимум будет при $n = 2$, поэтому бисекция является оптимальной.

[DimaM]

Можно запустить волну и померить время до прихода отраженной. Нынешние осциллографы дают точность единицы наносекунд.

[Лукомор]

DimaM в сообщении #1203834 писал(а):

Нынешние осциллографы дают точность единицы наносекунд.

Можно и не нынешний...
Есть такой прибор:"Измеритель неоднородности линий"(aka "Рефлектометр") , называется Р5-10 (или более старый Р5-5).
Он как раз для того, чтобы не резать, где не надо...
(Генератор импульсов + осциллограф) в одном корпусе...

-- Пн мар 27, 2017 07:34:18 --

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

Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.

Так не бывает.
В такой длинной линии сигнал затухнет и без повреждения, и на втором конце Вы ничего не услышите.
Поэтому между городами обязательно есть усилительные пункты (обслуживаемые и необслуживаемые).
Расстояние между ними может быть до 50 км, но, обычно, не больше 10 км.
Выяснив, на каком из таких участков повреждение, уже можно уточнять расстояние до повреждения.

[Poika]

Лукомор, спасибо за ответ!
Просто меня интересует вопрос не как телефониста, а как матиматика. Просто как математическая задача. Как наименьшим числом измерений дойти до поврежденного участка. Подумайте сами, ведь вопрос интресный!

-- 27.03.2017, 11:25 --

Aritoborian,
Спасибо за ответ!
Еали можешь обьяани поподробней пожалуйста, или скажи какую теорию почитать на эту тему? Откуда такое решение?

-- 27.03.2017, 11:26 --

Legioner93,
Спасибо за ответ!
Но я так и не понял почему такая функция. Напиши пожалуйста откуда она и где можно про нее почитать?

profrotter:
Замечание за фамильярность.

(Подробно)

Forum Administration в сообщении #27356 писал(а):

I. Нарушения и санкции
1) Нарушением считается:
е) Провокационные и вызывающие сообщения, фамильярность (у нас принято обращаться друг к другу на "Вы"), хамство, оскорбления в адрес участников дискуссии и иных лиц (в том числе не являющихся участниками форума), разжигание флейма, обсуждение в тематических разделах ников*, аватаров*, подписей* собеседников.

[Лукомор]

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

Как наименьшим числом измерений дойти до поврежденного участка. Подумайте сами, ведь вопрос интресный!

На этот вопрос ответил уже Aritaborian, исчерпывающе...

[Legioner93]

Poika
Прозваниваем участок длиной $1$. Каждый раз делим участок на $n$ частей и прозваниваем $(n-1)$ кусков. Действие прекращаем, когда локализуем разрыв на участке длиной $\varepsilon$. Всего подтребуется прозвонов

$$f(n) = \underbrace{(n-1) + (n-1) + \cdots + (n-1)}_{\log_{\frac{1}{n}} \varepsilon} = - (n - 1) \frac{\ln \varepsilon}{\ln n} \sim \frac{n - 1}{\ln n}$$

Эта функция строго возрастает при положительных $n$, поэтому минимальное число прозвонов будет при $n = 2$ (меньшие $n$ невозможны). То есть получили классическую бисекцию.

[wrest]

Лукомор в сообщении #1203897 писал(а):

На этот вопрос ответил уже Aritaborian, исчерпывающе...

Мне кажется тут вопрос немного другой: если мы делим не $1:1$, а в другой пропорции, затем случайно выбираем какую часть проверять, то как матождание количества шагов (за один шаг берем деление отрезка, выбор где проверять,и саму проверку) будет зависеть от пропорции, т.е. будет ли оно минимально если делить ровно пополам, а не $1:e$ например.


upd Зачеркнул лишнее, т.к. проверка на каждом шаге всегда показывает в какой части разрыв.

[Poika]

wrest
Простите, я не очень понял, что Вы имеете ввиду...=(

[wrest]

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

Простите, я не очень понял, что Вы имеете ввиду...=(

Ваш алгоритм может быть изменен:

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

Допустим у меня есть телефонный провод между двумя городами длинной 1000 км.
В какомто месте произошел разрыв провода.
Что бы найти разрыв, я например могу сначала разделить провод

... но не пополам, т.е. на 500-ом километре, а например на 300-ом километре.
Тогда, если повезло и разрыв между 0 и 300 (вероятность везения 0,3), то останется обследовать 300. А если не повезло, то разрыв между 300 и 1000 (вероятность невезения 0,7) и обследовать останется 700.

[Poika]

wrest
Целесообразно ли тогда измерять сначала 300? Или лучше начать всетаки с 500 чтоб измерить наименьшим количеством измерений?

[Dmitriy40]

Так это вопрос что именно Вам надо: или гарантированно минимальное количество измерений (и тогда деление пополам) или как можно быстрее в среднем найти точку разрыва (тогда делить желательно в пропорции золотого сечения, $1:1618$ и сначала измерять короткий участок). Второй способ быстрее лишь в среднем, или с некоторой вероятностью, в худшем случае он медленнее первого.

[Лукомор]

wrest в сообщении #1203915 писал(а):

Тогда, если повезло и разрыв между 0 и 300 (вероятность везения 0,3)

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

[Poika]

Dmitriy40
Спасибо! Подскажите пожалуйста в каком учебнике можно почитать про это? Про золотое сечение слышу первый раз