16 компьютеров связаны в сеть в виде решетки 4*4.
В памяти каждого имеется своя информация. За один
такт компьютер может передать ИЛИ принять от ОДHОГО
из соседей информацию любого объема.
За сколько тактов и каким образом ВСЕ компьютеры
могут получить ВСЮ информацию?

К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К

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

OG>16 компьютеров связаны в сеть в виде решетки 4*4.
OG>В памяти каждого имеется своя информация. За один
OG>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>из соседей информацию любого объема.
OG>За сколько тактов и каким образом ВСЕ компьютеры
OG>могут получить ВСЮ информацию?
OG>
OG>

OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>

12 тактов:

такты:
1: 3-й ряд берет инфу из 4-го
2: 2-й ряд берет инфу из 3-го
3: 1-й ряд берет инфу из 2-го
4: 2-й ряд берет инфу из 1-го
5: 3-й ряд берет инфу из 2-го
6: 4-й ряд берет инфу из 3-го
дальше тоже самое для столбцов

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

U>12 тактов:

По крайней мере, за 8 можно:

1: 1->2, 3->4
2: 2->4
3: 4->2
4: 2->1, 4->3

И так же для стообцов

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

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

U>>12 тактов:

ММ>По крайней мере, за 8 можно:

ММ>1: 1->2, 3->4
ММ>2: 2->4
ММ>3: 4->2
ММ>4: 2->1, 4->3

ММ>И так же для стообцов

Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...
по крайней мере я шел из этих рассуждений .

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

U>Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...
U>по крайней мере я шел из этих рассуждений .

Виноват, поправлюсь:

1: 1->2, 4->3
2: 2->3
3: 3->2
4: 2->1, 3->4

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

Ответ лежит в промежутке [6..8] Меньше точно нельзя, т.к., например, из левого верхнего угла в правый нижний можно дойти только за 6 ходов.

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

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

U>>Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...
U>>по крайней мере я шел из этих рассуждений .

ММ>Виноват, поправлюсь:

ММ>1: 1->2, 4->3
ММ>2: 2->3
ММ>3: 3->2
ММ>4: 2->1, 3->4
ММ>

Странно... я когда считал такой вариант ... у меня получались два раза больше .
Пойду учить арифметику.

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

OG>16 компьютеров связаны в сеть в виде решетки 4*4.
OG>В памяти каждого имеется своя информация. За один
OG>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>из соседей информацию любого объема.
OG>За сколько тактов и каким образом ВСЕ компьютеры
OG>могут получить ВСЮ информацию?
OG>
OG>

OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>|   |   |   |
OG>К - К - К - К
OG>

Меньше 6-ти быть не может, т.к. из (1.1) в (4.4) быстрее не передашь.
(столбец,ряд)

Я нашёл только 8:

свёртка:
1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

развёртка назад:
5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.

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

ММ>1: 1->2, 4->3
ММ>2: 2->3
ММ>3: 3->2
ММ>4: 2->1, 3->4

Нерационально с точки зрения лишней передачи данных, т.к. многие компы передают ненужную информацию.
По количеству передач — у меня меньше: у тебя (8+4+4+8)*2=48, у меня (8+4+2+1)*2=30 , однако кол-во ходов всё равно не меняется.

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

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

OG>>16 компьютеров связаны в сеть в виде решетки 4*4.
OG>>В памяти каждого имеется своя информация. За один
OG>>такт компьютер может передать ИЛИ принять от ОДHОГО
OG>>из соседей информацию любого объема.
OG>>За сколько тактов и каким образом ВСЕ компьютеры
OG>>могут получить ВСЮ информацию?
OG>>
OG>>

OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>|   |   |   |
OG>>К - К - К - К
OG>>

L>Меньше 6-ти быть не может, т.к. из (1.1) в (4.4) быстрее не передашь.
L>(столбец,ряд)

L>Я нашёл только 8:

L>свёртка:
L>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
L>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
L>3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
L>4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

L>развёртка назад:
L>5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
L>6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
L>7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
L>8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.
L>

Если уж пошел вопрос об оптимизации транзакций тогда так:
такты:
1:
1.1 -> 2.1
1.2 -> 2.2
3.1 -> 3.2
4.1 -> 4.2
4.3 -> 3.3
4.4 -> 3.4
1.4 -> 1.3
2.4 -> 2.3
2:
2.1 -> 2.2
4.2 -> 3.2
3.4 -> 3.3
1.3 -> 2.3
дальше все как у тебя

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

U>Если уж пошел вопрос об оптимизации транзакций тогда так:
U>такты:
U>1:
U> 1.1 -> 2.1
U> 1.2 -> 2.2
U> 3.1 -> 3.2
U> 4.1 -> 4.2
U> 4.3 -> 3.3
U> 4.4 -> 3.4
U> 1.4 -> 1.3
U> 2.4 -> 2.3
U>2:
U> 2.1 -> 2.2
U> 4.2 -> 3.2
U> 3.4 -> 3.3
U> 1.3 -> 2.3
U>дальше все как у тебя

А смысл? Те же 8 транзакций на первом шаге, 4 — на втором.

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

L>Здравствуйте, Михаил Можаев, Вы писали:

ММ>>1: 1->2, 4->3
ММ>>2: 2->3
ММ>>3: 3->2
ММ>>4: 2->1, 3->4

L>Нерационально с точки зрения лишней передачи данных, т.к. многие компы передают ненужную информацию.
L>По количеству передач — у меня меньше: у тебя (8+4+4+8)*2=48, у меня (8+4+2+1)*2=30 , однако кол-во ходов всё равно не меняется.

Либо опять у меня с арифметикой проблемы либо твой вариант имеет : (8+8+2+1) + (8+4+2+1) = 34
Это число все-таки — количестов операций обмена инфо.
А вот вариант который я предложил (в ответ на твой) как раз имеет 2*(8+4+2+1) = 30.
С уважанием.

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

L>А смысл? Те же 8 транзакций на первом шаге, 4 — на втором.

Виноват ... просто твой x — я понимал... как 1-4 во второом такте, однозначно сегодня не мой день.

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

U>Если уж пошел вопрос об оптимизации транзакций тогда так:
Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.

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

Y>Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.

Ты в корне не прав. Если обе проги работают по пол-часа, но одна из них занимает все 100% процессорного времени и имеет приоритет High, а другая — 50% и приоритет Normal, то при выборе из этих двух, любой нормальный пользователь выберет вторую, просто потому, что при использовании второй проги компьютер для него на эти пол-часа не умрёт.

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

К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К
|   |   |   |
К - К - К - К

L>Я нашёл только 8:

L>свёртка:
L>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
L>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
L>3: (x.2)->(x.3), где x=2,3 => вся инфа в (2.3) и (3.3), простаивает весь периметр (12 компов);
L>4: (2.3)->(3.3) => всё есть в (3.3), простаивают 14 компов;

L>развёртка назад:
L>5: (3.3)->(2.3) => полная инфа в каждом из (2,3) и (3.3);
L>6: (x.3)->(x.2), где x=2,3 => полная инфа в каждом из внутреннего квадрата;
L>7: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
L>8: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.

Решение в 7 тактов:
Свёртка:
1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
Круговой обмен:
3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Развёртка назад:
6: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
7: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех всё есть.

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

WR>Решение в 7 тактов:
WR>Свёртка:
WR>1: (1.x)->(2.x), (4.x)->(3.x), где x=1,2,3,4 => вся инфа есть в столбцах 2 и 3;
WR>2: (x.1)->(x.2), (x.4)->(x.3), где x=2,3 => вся инфа есть во внутренних четырёх компах, ряды 1 и 4 простаивают (8 компов);
WR>Круговой обмен:
WR>3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
WR>4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
WR>5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Неправда, в (2,2) и (3,3) неполная!!!
WR>Развёртка назад:
WR>6: (x.2)->(x.1), (x.3)->(x.4), где x=2,3 => полная инфа в каждом компе столбцов 2 и 3;
WR>7: (2.x)->(1.x), (3.x)->(4.x), где x=1,2,3,4 => у всех

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

WR>>Круговой обмен:
WR>>3: (2.2)->(2.3), (3.3)->(3.2) => вся инфа в (2.3) и (3.2), простаивает весь периметр (12 компов);
WR>>4: (2.3)->(3.3), (3.2)->(2.2) => вся инфа в (2.2) и (3.3), простаивает весь периметр (12 компов);
WR>>5: (3.3)->(3.2), (2.2)->(2.3) => полная инфа в каждом из внутреннего квадрата, простаивает весь периметр (12 компов);
Y>Неправда, в (2,2) и (3,3) неполная!!!

Ага, я тоже хотел сначала так сделать
Даёт полную инфу только в (3.2) и (2.3). К сожалению это не получилось использовать.

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

Очень бы хотелось увидеть решение автора.
Или хотя бы ответ.
Считает ли он, что задача закрыта?

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

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

P>Очень бы хотелось увидеть решение автора.
P>Или хотя бы ответ.
P>Считает ли он, что задача закрыта?

Меньше 8 тактов решение не вижу.