Сегодня, к сожалению, спешу, поэтому много не напишу. Задачи сегодня не очень сложные (как, впрочем, и предыдущие).

1. Есть кабель.
2. В кабеле 11 одинаковых проводов.
3. Один конец кабеля находится достаточно далеко от другого.
4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля.
5. Любые другие пометки запрещены.

Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода.
Примечание 1: "Поезка" = туда-обратно.
Примечание 2: Нет необходимости ездить, чтобы снять замыкания.

Удачи!!!

Здравствуйте 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

замкнуть (a-b-d-g)="5", (c-e-h)="6", (f-i)="7", (j)="8", (k)="9"

На конце 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 проводов это минимальное количество поездок.

Здравствуйте Кодт, Вы писали:

К>Здравствуйте fAX, Вы писали:

К>На мой взгляд, — если не заниматься одновременной коммутацией и прозвонкой (на одной и той же стороне) — для 11 проводов это минимальное количество поездок.

Ещё полшага :) (по-моему, т.е. если я сам не ошибся, то можно меньше ;) :super: :shuffle: ).

Здравствуйте fAX, Вы писали:

fAX>1. Есть кабель.
fAX>2. В кабеле 11 одинаковых проводов.
fAX>3. Один конец кабеля находится достаточно далеко от другого.
fAX>4. В Вашем распоряжении имеется прозвонка и возможность замыкать между собой любое количество проводов и "прозванивать" провода с другого конца кабеля.
fAX>5. Любые другие пометки запрещены.

fAX>Требуется (чуть не забыл написать) за минимальное количество поездок одинаково отметить концы каждого провода.
fAX>Примечание 1: "Поезка" = туда-обратно.
fAX>Примечание 2: Нет необходимости ездить, чтобы снять замыкания.

А что делает прозвонка?

Здравствуйте Аноним, Вы писали:

А>А что делает прозвонка?
Если не шутка , то проверяет, есть ли контакт между двумя точками. Применительно к задаче, позволяет находить группы проводов.

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Аноним, Вы писали:

А>>А что делает прозвонка?
fAX>Если не шутка :-), то проверяет, есть ли контакт между двумя точками.

Эти точки на одном конце провода?

Здравствуйте Аноним, Вы писали:

А>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте Аноним, Вы писали:

А>>>А что делает прозвонка?
fAX>>Если не шутка :-), то проверяет, есть ли контакт между двумя точками.

А>Эти точки на одном конце провода?

1 -------------------------------------------------- a
2 -------------------------------------------------- b
3 -------------------------------------------------- c

Если поставить перемычку между b и c, то 2 и 3 будут "звониться", а 1 и 2, например, нет.

Здравствуйте 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) A-B1 — C1-E1
(2) B2-D1-C2-E2
(3) D2-C3
(4) E3

Соединения легко находятся. Так (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 проводов?

Здравствуйте KonstantinA, Вы писали:

KA>А интересно, можно ли распознать больше 11 проводов?

Для 12.

   *  *  *--*  *--*  *--*--*  *--*--*
   a1 b1 c1 c2 d1 d2 e1 e2 e3 f1 f2 f3

A1 ?  ?                                *--------G
B1 ?  ?                                |   *----H
C1       ?  ?                          *   |
C2       ?  ?                          |   | *--0
D1             ?  ?                    *   |
D2             ?  ?                    | *-+----I
E1                   ?  ?  ?           * | |
E2                   ?  ?  ?           | * |
E3                   ?  ?  ?           | | *
F1                            ?  ?  ?  * |
F2                            ?  ?  ?    *
F3                            ?  ?  ?      *----0

--------------------------------------------------
A1 <= G
B1 <= H

C1 <= G, C2 <= 0
D1 <= G, D2 <= I

E1 <= G, E2 <= I, E3 <= H
F1 <= G, F2 <= I, F3 <= 0

Емкость еще есть, и существует "индукционный" алгоритм.

Для 15

   *  *  *--*  *--*  *--*--*  *--*--*  *--*--*
   a1 b1 c1 c2 d1 d2 e1 e2 e3 f1 f2 f3 g1 g2 g3

A1 ?  ?                                         *---------H
B1 ?  ?                                         |   *-----I
C1       ?  ?                                   *   |
C2       ?  ?                                   |   | *---0
D1             ?  ?                             *   |
D2             ?  ?                             | *-+-----J
E1                   ?  ?  ?                    * | |
E2                   ?  ?  ?                    | * |
E3                   ?  ?  ?                    | | *
F1                            ?  ?  ?           * | |
F2                            ?  ?  ?             * |
F3                            ?  ?  ?               | *---K
G1                                     ?  ?  ?      * |
G2                                     ?  ?  ?        *
G3                                     ?  ?  ?          *-0

E1 <= H, E2 <= J, E3 <= I
F1 <= H, F2 <= J, F3 <= K
G1 <= I, G2 <= K, G3 <= 0

Идея индукционного алгоритма в том, что к имеющемуся решению задачи
(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 конце, + новая нулевая).

Ну и так далее.