Xpoint
   [напомнить пароль]

Детская задачка (оптимизация перебора вариантов)

Метки: [без меток]
2006-10-06 22:32:24 [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]

Наверняка задача известная, но я почему-то услышал ее только сегодня:

По дну реки проложен кабель, а в нем 2 в степени n (варианты — 2 n или даже просто n) изолированных проводов. Все провода одного цвета. У монтера есть лодка и простейший тестер — батарейка с лампочкой (вариант — отвертка с лампочкой, показывающая наличие фазы, и к одному берегу подходит линия электропередач). Монтеру требуется "прозвонить" кабель (опознать концы каждого провода), переплывая реку минимальное число раз.

Точно знаю, что есть простое красивое решение в 3 "ходки" и сложное некрасивое (зато свое:) — в 2. Но знатоки утверждают, что существует простое красивое решение в 2 "ходки". Буду благодарен, если подскажете, в каком направлении его искать.

спустя 1 год 1 месяц [обр] Антон Клесс(0/25)[досье]
если число жил в кабеле четное — делаем n/2 скруток с одной стороны и с другой стороны должны получить столько же "звонящих" пар жил, если нечетное — то непонятно..
спустя 14 часов [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]

Антон Клесс[досье], это и есть первое из известных мне решений. Потом свободные концы пар тоже скручиваются, замыкая все провода в одну сплошную последовательную цепь, и на другом берегу, последовательно раскручивая первые скрутки, однозначно идентифицирует все концы. Если число проводов нечетное, то оставшийся "не у дел" провод определяется методом исключения, это не проблема. Но переплывать реку приходится трижды.

А мое решение - вначале разбиваем провода на группы по схеме: два оставляем свободными, скручиваем следующие 2, потом следующие 4, потом следующие 8 и т.д. (пока для простоты рассматриваем первый случай - когда число проводов из ряда степеней двойки). Каждая группа отвечает за один разряд в нумерации проводов в двоичной системе. На другом берегу определяем принадлежность проводов к каждой группе и "донумеровываем" их: из двух ни с чем не связанных проводов одному "присваиваем" 0 и оставляем его свободным, другому "присваиваем" 1 и скручиваем его с теми проводами из каждой группы, в нумерации которых есть единица в соответствующем этой группе двоичном разряде.

Теперь опять переплываем реку, легко находим нулевой (ни с чем не связанный) и первый (связанный со всеми группами) провода из двух свободных, а затем, поочередно распутывая группы, определяем номер каждого провода по его связи с другими разрядами.

Если число проводов не из ряда степени двойки, алгоритм тоже применим, для последней (неполной) группы отбрасываем младшие разряды. Тогда, например, для 12 проводов у нас получатся 2 группы по 4 провода, но по возвращении с другого берега мы их не перепутаем: в первой "четверке" (которая соответствует четверке:) будет провод 100, не связанный с другими разрядами, а в другой (которая на самом деле неполная "восьмерка") все провода будут иметь "внешние связи".

Получается, что "ходок" действительно две, но на каждом шаге много мороки... :)

спустя 5 дней [обр] Антон Клесс(0/25)[досье]
недетская это задачка. детская — где решение само по себе крайне просто, но неочевидно. а тут надо хотя бы 9 классов школьного образования иметь на уровне отличника по точным наукам =)
спустя 3 дня [обр] Илья Cтpeльцын aka SelenIT(2/171)[досье]
Антон Клесс[досье], так может это я перемудрил, а настоящее решение простое и "детское"? ;)
Powered by POEM™ Engine Copyright © 2002-2005