Здравствуйте fAX, Вы писали:
fAX>Сегодня, к сожалению, спешу, поэтому много не напишу. Задачи сегодня не очень сложные (как, впрочем, и предыдущие).
fAX>1. Есть кабель. fAX>2. В кабеле 11 одинаковых проводов. fAX>3. Один конец кабеля находится достаточно далеко от другого. fAX>4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля. fAX>5. Любые другие пометки запрещены.
fAX>Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода. fAX>Примечание 1: "Поезка" = туда-обратно. fAX>Примечание 2: Нет необходимости ездить, чтобы снять замыкания.
fAX>Удачи!!!
Соединяем провода так.
1 --- обозначим его a
2 по 2 --- кучки _b,_d
2 по 3 --- кучки _c,_e
Едем на тот конец.
Для каждого провода находим те, с кем он прозванивается.
Там находится одиночный провод --- обозначим его A. Одиночные концы сошлись
Находятся две кучки по два провода --- B1,B2 и D1,D2.
Находятся две кучки по три провода --- C1,C2,C3 и E1,E2,E3.
Тогда
a — A
_b — B, _d — D или _b — D, _d — B
_c — C, _e — E или _c — E, _e — C
Соединения легко находятся. Так (1) звонится с а, а (2) --- нет. В (1) и (2) --- 4 элемента. В (3) 2 элемента. В (4) 1 элемент.
1. соединение (4) говорит нам где какая кучка _c или _e соответствует C, а какая E. Обозначим c-C, e-E. Соответственно виден e3-E3.
2. соединение (1) (A-соединен только с 1 элементом из _b и _d) дает соответствие (_b или _d соответствует b и D) обозначим b-B и d-D. И найден b1-B1.
3. соединение (1) находим с1-С1 и е1-Е1, так с и где е мы уже знаем по пункту 1.
4. соединение (2) дает d1-D1, c2-C2, e2-E2.
5. соединение (3) дает d2 — D2, c3 — C3.
А интересно, можно ли распознать больше 11 проводов?
Re[2]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
Здравствуйте fAX, Вы писали:
fAX>1. Есть кабель. fAX>2. В кабеле 11 одинаковых проводов. fAX>3. Один конец кабеля находится достаточно далеко от другого. fAX>4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля. fAX>5. Любые другие пометки запрещены.
fAX>Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода. fAX>Примечание 1: "Поезка" = туда-обратно. fAX>Примечание 2: Нет необходимости ездить, чтобы снять замыкания.
Пусть на конце 1 провода маркируются буквами A-K, а на конце 2 — a-k
::: иллюстрация ::: комментарии ниже :::
1 2 3 4
* *-* *-*-* *-*-*-*-*
A B C D E F G H I J K
5 6 7 8 9
a * *
b * * *
c * * | *
d * * * * |
e * * * | *
f * * * | | *
g * * * * * * | |
h * * * * * * |
i * * * * * *
j * * * * * *
k * * * * * *
На конце 1
замкнуть
"1"=A, "2"=(B-C), "3"=(D-E-F), "4"=(G-H-I-J-K)
На конце 2
прозвонить, сгруппировать и промаркировать
"1"=a, "2"=(b,c) и так далее.
Получено однозначное соответствие A-a, теперь нужно уточнить соответствие в группах 2...4
На конце 1
прозвонить и сгруппировать.
Aa — уже был определен
для остальных:
B=5 --> Bb, Cc
B=6 --> Bc, Cb
D=5 --> Dd
D=6 --> De
D=7 --> Df
и так далее.
Неразрешенными остались только j и k. Пусть на них претендуют J и K.
Соединим "10"=(A-J)
На конце 2
Если "10"=(a,j) — то Jj, Kk. Иначе — наоборот.
Итого
Полторы поездки.
Более коротким способом — не придумал.
На мой взгляд, — если не заниматься одновременной коммутацией и прозвонкой (на одной и той же стороне) — для 11 проводов это минимальное количество поездок.
Перекуём баги на фичи!
Re[3]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
Идея индукционного алгоритма в том, что к имеющемуся решению задачи
(2 группы по 1 + 2 гр. по 2 + 2 гр. по 3) можно добавить:
13 = +1 провод — еще одна группа из 1 провода — на втором конце не коммутируем его
14 = +2 провода — еще одна группа из 2 проводов, один не коммутируем, а второй — коммутируем с ранее некоммутированным из группы из 3
15 = +3 провода — еще одна группа из 3
Все эти решения — на первом конце группы максимум из 3 проводов.
Далее
16 = 12 (1.1.2.2.3.3) + 4 — даже не нужно разрешать неоднозначность для последней группы
16 = 12+4
17 = 12+5 = 13+4
18 = 12+6 (предел: в решении для 12 на 2 конце есть 5 групп + новая нулевая) = 13+5 = 14+4
19 = 13+6 = 14+5 = 15+4
Прямые потомки решения для 15 проводов имеют резерв 7 (столько групп на 2 конце, + новая нулевая).
Сегодня, к сожалению, спешу, поэтому много не напишу. Задачи сегодня не очень сложные (как, впрочем, и предыдущие).
1. Есть кабель.
2. В кабеле 11 одинаковых проводов.
3. Один конец кабеля находится достаточно далеко от другого.
4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля.
5. Любые другие пометки запрещены.
Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода.
Примечание 1: "Поезка" = туда-обратно.
Примечание 2: Нет необходимости ездить, чтобы снять замыкания.
Здравствуйте Кодт, Вы писали:
К>Здравствуйте fAX, Вы писали:
К>На мой взгляд, — если не заниматься одновременной коммутацией и прозвонкой (на одной и той же стороне) — для 11 проводов это минимальное количество поездок.
Ещё полшага :) (по-моему, т.е. если я сам не ошибся, то можно меньше ;) :super: :shuffle: ).
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Re[2]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
От:
Аноним
Дата:
12.08.02 16:40
Оценка:
Здравствуйте fAX, Вы писали:
fAX>1. Есть кабель. fAX>2. В кабеле 11 одинаковых проводов. fAX>3. Один конец кабеля находится достаточно далеко от другого. fAX>4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля. fAX>5. Любые другие пометки запрещены.
fAX>Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода. fAX>Примечание 1: "Поезка" = туда-обратно. fAX>Примечание 2: Нет необходимости ездить, чтобы снять замыкания.
А что делает прозвонка?
Re[3]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
Здравствуйте Аноним, Вы писали:
А>А что делает прозвонка?
Если не шутка , то проверяет, есть ли контакт между двумя точками. Применительно к задаче, позволяет находить группы проводов.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Re[4]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
От:
Аноним
Дата:
12.08.02 16:45
Оценка:
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте Аноним, Вы писали:
А>>А что делает прозвонка? fAX>Если не шутка :-), то проверяет, есть ли контакт между двумя точками.
Эти точки на одном конце провода?
Re[5]: Прозвонка длинного кабеля (ЗаЗа - номер 101 ;-) )
Здравствуйте Аноним, Вы писали:
А>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте Аноним, Вы писали:
А>>>А что делает прозвонка? fAX>>Если не шутка :-), то проверяет, есть ли контакт между двумя точками.
А>Эти точки на одном конце провода?
1 -------------------------------------------------- a
2 -------------------------------------------------- b
3 -------------------------------------------------- c
Если поставить перемычку между b и c, то 2 и 3 будут "звониться", а 1 и 2, например, нет.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)