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
ММ>И так же для стообцов
Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ...
по крайней мере я шел из этих рассуждений .
Здравствуйте, uzzy, Вы писали:
U>Если судить по рисунку... то компы не имеют связи каждый с каждым, то есть 2->4 не возможна из-за отсутствия связи ... U>по крайней мере я шел из этих рассуждений .
Здравствуйте, Михаил Можаев, Вы писали:
ММ>Здравствуйте, 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
дальше все как у тебя
Здравствуйте, 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.
С уважанием.
Здравствуйте, uzzy, Вы писали:
U>Если уж пошел вопрос об оптимизации транзакций тогда так:
Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.
Здравствуйте, yogi, Вы писали:
Y>Ну её "оптимизацию транзакций" тут надо кол-во шагов уменьшить. Если у меня две проги работают по полчаса и приводят к одинаковому результату, то для меня (как пользователя) монопенисуально какая из них якобы оптимальнее.
Ты в корне не прав. Если обе проги работают по пол-часа, но одна из них занимает все 100% процессорного времени и имеет приоритет High, а другая — 50% и приоритет Normal, то при выборе из этих двух, любой нормальный пользователь выберет вторую, просто потому, что при использовании второй проги компьютер для него на эти пол-часа не умрёт.
К - К - К - К
| | | |
К - К - К - К
| | | |
К - К - К - К
| | | |
К - К - К - К
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). К сожалению это не получилось использовать.
Здравствуйте, Pushkin, Вы писали:
P>Здравствуйте, Oleg_Gashev, Вы писали:
P>Очень бы хотелось увидеть решение автора. P>Или хотя бы ответ. P>Считает ли он, что задача закрыта?