Из подвального помещения многоэтажной новостройки, на последний этаж были проведены N одножильных электрических проводов. Т.к. все провода были абсолютно одинаковыми (включая и цвет изоляции), то перед проведением электропроводки последнего этажа необходимо было идентифицировать их – однозначно определив и разметив начало и конец каждого провода. С учётом того что лифт ещё не был подключён, перед находящимся на подвале электриком стояла непростая задача: Минимум сколько раз необходимо подняться на последний этаж, чтобы выполнить поставленную перед собою работу имея при себе лишь индикаторную лампочку (индикаторная лампочка загорается при прикосновении ею к одному из концов провода, если другой конец провода подключён к фазе) и маркер для разметки проводов. Электрик также заметил, что в подвале есть находящийся под напряжением доступная фаза. Как только электрик описал подробный алгоритм своих действий, позволяющий выполнить поставленную задачу независимо от количества проводов, он вдруг заметил, что есть ещё один – не такой очевидный как первый, но более быстрый с точки зрения выполняемых элементарных действий алгоритм. От нас же требуется следующее: - определить, сколько раз всё же нашему электрику пришлось подняться на последний этаж в течение всей работы; - подробно описать как первый придуманный им алгоритм выполнения работы, так и модифицированную часть второго - более быстрого алгоритма.
1. подключаем один конец провода к фазе, маркируем его (например "1") и едем наверх 2. там находим провод под током маркеруем его так же "1" 3. присоединяем к нему любой другой провод, промаркировав "2" едем вниз 4. находим тот что под током. маркитуем "2" 5. повторяем действия 1-4, пока не кончатся провода Стого имеем N/2 (с округлением в большую сторону) поездок.
Up Grade: 1. подклюкаем два провода на фазу и маркируем их (например "1" и "1а"). едем наверх 2. находим провода под током, но не маркируем 3. подключаем к проводам под током по свободному проводу, маркируем "2" и "2а". едем вниз 4. находим провода под током, но не маркируем 5. повторяем действия 1-4, пока не кончатся провода 6. далеее, в зависимости от того, где мы находимся (вверху или внизу): отключаем провод "1" - если внизу, "2" - если вверху. переписываем номера маркированных проводов, отмечая какие из них под током. поднимаемся или спускаемся 7. находим узлы под током. переписываем номера маркированных проводов, отмечая какие из них под током. маркируем неотмеченные провода числами на 1 меньше, чем у отмеченного в том же узле, ставя букву "а" в соответствии с записями сделанными в действии (6). если мы сейчас находимся внизу отключаем провод "1" от фазы и проверяем не пропало ли напряжение в проводах какие былы под током. записываем под током "1" или нет и едем опять наверз или вниз. 8. Маркируем неотмеченные провода провода в узлах сверяясь с записями. В итоге имеем: N/4+1 (с округлением в большую сторону) поездок.
Для очень большого количества проводов можно подключить к фазе сразу несколько проводов тогда количество поездок будет равно N/2M+M-1, г8де M число проводов на фазе
1) Ставим 1 на любом проводе и запитываем его. 2) Группируем оставшиеся провода в парные скрутки (если N четно, то один провод, исключая 1, останется без пары) 3) Идем наверх, там курим. 4) Тестируя проводку индикатором ищим фазу, ставим 1. 5) Соединяем 1 с любым неотмеченым проводом и ставим на нем двойку, находим индикатором его пару и ставим на нем 3. 3 соединяем с любым неотмеченым проводом, ставим на нем 4, находим индикатором пару четверки и ставим на нем 5. Продолжаем в том же духе пока не закончаться провода( при четном N пары для одного не найдется, поэтому его отмечать ненадо). Таким образом у нас получилось последовательное соединение всех проводов(шаги 2, 5), за исключением одного при четном N. 7) Возвращаемся обратно, курим. 8) Разъединяем поочередно скрутки, пока не найдем ту, при разрыве которой, фаза остается лишь на 1 и на одном из разомкнутой пары, - ставим на нем 2, а на его паре 3. Соединяем 2 и 3. Опять ищем скрутку, при размыкании которой, фаза остается лишь на отмеченых проводах и на одном проводе из разомкнутой пары,- ставим на нем четверку, а на его паре 5. Продолжаем в том же духе, пока не кончаться провода. При четном N, провод находящийся не в скрутке не отмечаем. 9) Курим и идём за пивом. Вот таким макаром мы идентифицировали все провода, поднявшись наверх всего один раз. При четном N, останется один неотмеченный провод, собственно это его и идентифицирует. При N=1; N=2 можно вообще не подниматься. Итак, найден алгоритм, оптимизирующий работу электрика до минимум затраты времени и энергии. А какие там алгоритмы придумал электрик, это одному автору известно, а я в ромашку играть не люблю.))) P.S. При решении задачи, использовались правила группировки алгебр Ли, четыре банки пива фисташки и сигареты.))
Сообщение отредактировал Kreativshik - Сб, 29.06.13, 17:18
Электрик то кстати дуб дубом, этож надо тянуть одноцветные провода.. Про его индикатор я вообще молчу. Я б на его месте уволился бы и больше ни когда не работал электриком, чтобы не позориться. )
Kreativshik с пунктами 1-7 всё нормально. Что же касается п.8 то тут у меня вопрос к вам: предположим, что в первом цикле вы раскрутили пару 2-3 последним и перед вторым циклом у вас остались n-3 штук разъединённых и абсолютно идентичных проводов, разъясните, пожалуйста, ваши последующие действия, шаг за шагом поподробнее не упуская не каких операций …
Вы шо то путаете, после нахождения пары 2-3 ни одна скрутка не остается разомкнутой. Ну давайте я первые шаги постараюсь вам разъяснить, но если ясности не прибавится, то проблема уже, простите, в вас, а не в формулировке восьмого пункта. В общем берем любую скрутку, размыкаем ее и тестером проверяем остальные скрутки на наличие фазы. Если фаза присутствует хотя бы на одной неотмеченной скрутке, то соединяем обратно разомкнутую скрутку, берем следующую скрутку и делаем тоже самое, и так продолжаем до тех пор, пока не найдем такую скрутку, при разрыве которой, фаза останется лишь на отмеченных проводах (в начале это у нас 1) и на одном проводе из разомкнутой пары - его отмечаем двойкой, а его пару тройкой. Соединяем 2-3. Далее опять начинаем поочередно размыкать и соединять неотмеченные скрутки, пока не найдем ту, при разрыве которой, фаза останется лишь на отмеченных проводах (это уже 1, 2 3) и на одном из разомкнутой скрутке - его отмечаем четверкой, а его пару пятеркой. Соединяем 4-5. Далее опять поочередно размыкаем и соединяем .... Хватит или продолжить?
Лучше конечно другу позвонить помочь, пусть он на верх и поднимается. )) Взять частотный генератор ну или хотя бы тестер, а на крайний случай и пробник с чувствительностью не менее 40кОм пойдет, всетаки под фазой опасненько работать. А там плинты ставим и спокойно кроссируем.
Kreativshik т.к в ваших ответах было очень много спорных моментов, то я постараюсь остановится хотя бы на основных из них: 1.
Цитата ( Kreativshik)
Вы шо то путаете, после нахождения пары 2-3 ни одна скрутка не остается разомкнутой. Ну давайте я первые шаги постараюсь вам разъяснить, но если ясности не прибавится, то проблема уже, простите, в вас, а не в формулировке восьмого пункта.
Цитата ( Kreativshik)
8) Разъединяем поочередно скрутки, пока не найдем ту, при разрыве которой, фаза остается лишь на 1 и на одном из разомкнутой пары, - ставим на нем 2, а на его паре 3. Соединяем 2 и 3. Опять ищем скрутку, при размыкании которой, фаза остается лишь на отмеченых проводах и на одном проводе из разомкнутой пары,- ставим на нем четверку, а на его паре 5. Продолжаем в том же духе, пока не кончаться провода. При четном N, провод находящийся не в скрутке не отмечаем.
Из ваших вышеприведённых утверждений однозначно следует то, что я должен был соединить разъединённые вами провода… 2.
Цитата ( Kreativshik)
Итак, найден алгоритм, оптимизирующий работу электрика до минимум затраты времени и энергии
Цитата ( Kreativshik)
В общем берем любую скрутку, размыкаем ее и тестером проверяем остальные скрутки на наличие фазы. Если фаза присутствует хотя бы на одной неотмеченной скрутке, то соединяем обратно разомкнутую скрутку, берем следующую скрутку и делаем тоже самое, и так продолжаем до тех пор, пока не найдем такую скрутку, при разрыве которой, фаза останется лишь на отмеченных проводах (в начале это у нас 1) и на одном проводе из разомкнутой пары - его отмечаем двойкой, а его пару тройкой. Соединяем 2-3. Далее опять начинаем поочередно размыкать и соединять неотмеченные скрутки, пока не найдем ту, при разрыве которой, фаза останется лишь на отмеченных проводах (это уже 1, 2 3) и на одном из разомкнутой скрутке - его отмечаем четверкой, а его пару пятеркой. Соединяем 4-5. Далее опять поочередно размыкаем и соединяем ....
Из вышеприведённых ваших утверждений следует что: - Либо Вы и впрямь считаете что решение, при котором, по идее, осуществляется абсолютный полный перебор, оптимален… - либо вы были не внимательны ко второй части моего вопроса…
Цитата ( marutand)
- подробно описать как первый придуманный им алгоритм выполнения работы, так и модифицированную часть второго - более быстрого алгоритма.
Из выше поставленного вопроса однозначно следует, что есть хотя бы 1 алгоритм, избегающий полного перебора всех возможных вариантов… хотя оба алгоритма придуманных, как вы выразились «дуб дубом» электриком избегают полный перебор. Имея в виду высокий уровень вашей математической подготовленности с одной стороны, что очевидно из решённых вами задач форума, и ваше нижеприведённое высказывание с другой:
Цитата ( Kreativshik)
А какие там алгоритмы придумал электрик, это одному автору известно, а я в ромашку играть не люблю.)))
Я всё же склоняюсь к последнему варианту, и прошу вас впредь, при решении задач поставленных мною, быть повнимательнее к их условиям … 3.Что же касается соответствия вашего ответа, на вопросы, поставленные в задаче то…
Цитата ( marutand)
перед находящимся на подвале электриком стояла непростая задача: Минимум сколько раз необходимо подняться на последний этаж, чтобы выполнить поставленную перед собою работу
Цитата ( marutand)
От нас же требуется следующее:
К сожалению, вы дали исчерпывающий ответ лишь на вопрос, поставленный перед электриком… Но учитывая ваши глубокие знания по проведению электромонтажных работ:
Цитата ( Kreativshik)
Электрик то кстати дуб дубом, этож надо тянуть одноцветные провода.. Про его индикатор я вообще молчу. Я б на его месте уволился бы и больше ни когда не работал электриком, чтобы не позориться. )
Цитата ( Kreativshik)
Взять частотный генератор ну или хотя бы тестер, а на крайний случай и пробник с чувствительностью не менее 40кОм пойдет, всетаки под фазой опасненько работать. А там плинты ставим и спокойно кроссируем.
а так же то, что вы всё таки уловили основную суть задачи…
Ваш ответ Зачтён…
А сейчас посмотрим, какой подход предпринял наш электрик для решения поставленной задачи. Он сразу же понял что необходимо: 1.Провести фазу на последний этаж; - для этого он пронумеровал маркером один из проводов, присвоив ему, номер 1 и присоединил его к имеющейся на подвале фазе. 2.Из отдельных проводов получить единую цепь, чтобы в последующем разными отсоединениями и «замерами» идентифицировать провода; С этой целю он: - находясь на подвале, попарно присоединил все оставшиеся провода (при чётном N останется ещё один отдельный провод); - затем поднялся на последний этаж и в первую очередь индикатором нашёл другой конец подсоединённой к фазе провода 1,и пронумеровал его; - т.к. внизу он все провода присоединил попарно, то сразу понял, что если присоединить конец любого провода к проводу 1 (т.е. к фазе), то только на конце его пары появится напряжение. Соответственно он взял любой провод и, пронумеровав его под номером 2, присоединил к проводу 1. Затем он индикатором нашёл единственный находящийся под напряжением провод и, дав ему, номер 3 «назначил» его фазой для следующего цикла. Далее он аналогичным образом выполнил указанную процедуру до тех пор, пока не были пронумерованы все провода (для нечётных N). Если же либо после присоединения очередного провода, пары находящейся под фазой не было, либо в конце оставался 1одинокий провод, то он получал последний номер N (для чётных N). - пронумеровав последний провод и поняв, что в результате всех предыдущих действий ему фактический удалось получить один присоединённый к фазе провод, он спустился в подвал… 3.Разработать алгоритм позволяющий выполнить идентификацию проводов как можно быстрее, т.е при возможности рассечь многочисленные варианты полного перебора; Вернувшись в подвал, он сразу же понял, что за просто можно решить поставленную перед ним задачу применив метод полного перебора в его чистом виде, т.е. путём многочисленных разъединений, соединений и индикаций поочерёдно найти единственный для данного цикла, находящийся под напряжением конец, тем самым фактический пронумеровав все пары строго по очереди от 2 до N. Но сосредоточившись он понял что вместо того чтобы бессмысленно мотаться по проводу туда сюда, неоднократно зря разъединив и соединив пары, он может после каждого разъединения сделать кое что и тем самым значительно ускорить свои работы. Так что же мог придумать наш умница…?
Вариант 1
Электрик, сразу же заметив, что когда он разъединяет одну из пар, тем самым он фактический делит свой составной провод на две части, все узлы одной из которых присоединены к фазе и соответственно все узлы другой не присоединены к фазе, перешёл к описанию алгоритма. Вкратце его суть состоял в следующем: - Разъединив одну из пар он, начиная с концов разъединённой пары, станет «индицировать» все места соединений проводов, параллельно сосчитав, сколько раз при этом загорится лампочка индикатора (mi). Естественно это будет означать, что в первой, не обесточенной части нашего провода оказались 2mi проводов и, следовательно, находящийся под фазой провод должен быть маркирован цифрой 2mi, а его пара цифрой (2mi +1), а провода должны быть снова соединены. Повторив указанную процедуру (N-1)/2 (для нечётных N) или (N-2)/2 раз (для чётных N) он пронумерует все провода. Для чётных проводов последний одинокий провод получит номер N. Закончив описание, он почувствовал, что подъем на последний этаж и спуск сделали своё «чёрное» дело и он устал до такой степени, что не в силах выполнить доже элементарные расчеты варианта 1. И вдруг к нему пришло осветление..., и он сразу же приступил к выполнению последней стадии работ, согласно не такому уж очевидному как первый, но зато не требующему никаких счётов и расчётов, более быстрому алгоритму. Так что же придумал наш умница, на сей раз…?
Вариант 2
- Предварительно присвоив обоим проводам одной и той же пары один и тот же номер, он разъединил все пары. Очевидно, что в этом случае под напряжением осталось тот провод, чей второй конец на последнем этаже присоединён к фазе. При первом цикле естественно конечным проводом фазы будет провод 1, а напряжение будет только лишь на проводе 2. Следовательно, найдя при помощи индикатора единственный провод, на котором есть напряжение, электрик перенумеровал его в 2, а потом, найдя его пару по предварительному номеру, перенумеровал его в 3 и вновь присоединил их. Естественно найденный после очередного цикла второй i+1 провод пары (i,i+1)станет для следующего цикла конечным проводом фазы, а напряжение будет только лишь на первом проводе i+2 пары (i+2,i+3). Поступив аналогичным образом для всех проводов, т.к. N был чётным он фактический за (N-2)/2 раза перенумеровал все провода кроме последнего «одинокого» провода, которому он присвоил номер N. Если бы N был нечетным, то он бы перенумеровал все провода за (N-1)/2 раза. 4.Сделать всё это минимум раз промаршировав по лестницам «вверх – вниз». Закончив свой умственно-физический труд, он на радость себе зафиксировал, что: - за всю работу поднялся на последний этаж в минимальное количество раз – т.е. всего лишь один раз… - благодаря разработанному им алгоритму ему в последней стадии работ удалось избежать полного перебора вариантов, тем самым значительно укоротив общее время выполнения всех работ…
Сообщение отредактировал marutand - Чт, 04.07.13, 15:06
