Сеть компьютеров-2 - Этюды для программистов

Попытаюсь усложнить условие задачи. Условие смотритездесь. Мы рассматривали сеть из 16 компьютеров. Вопрос оказался довольно простым.

А если так:

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

Здравствуйте, Олег Гашев, Вы писали:

ОГ>m*n компьютеров связаны в сеть в виде решетки m*n.

Ну, если делать по алгоритму Михаила Можаева, то число операций

k = m+m%2 + n+n%2;

Хотя так и осталось не доказанным утверждение (вполне возможно правильное), что стратегия "сначала строки, потом независимо столбцы" наилучшая.

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

P>Здравствуйте, Олег Гашев, Вы писали:

P>Ну, если делать по алгоритму Михаила Можаева, то число операций

P>

P>k = m+m%2 + n+n%2; 
P>

m=1, n=3?

Здравствуйте, Олег Гашев, Вы писали:

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

P>>

P>>k = m+m%2 + n+n%2; 
P>>

ОГ>m=1, n=3?

Да, поймал. Для (m==1 || n==1) простая формула не работает.

Т.е. она ещё проще становится, но слить вместе — совсем крокодил получится.
Но это и не сетка, правда? Ты ещё потребуй ответа для отрицательных m и n

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

P>Здравствуйте, Олег Гашев, Вы писали:

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

P>>>

P>>>k = m+m%2 + n+n%2; 
P>>>

ОГ>>m=1, n=3?

P>Да, поймал. Для (m==1 || n==1) простая формула не работает.

P>Т.е. она ещё проще становится, но слить вместе — совсем крокодил получится.
P>Но это и не сетка, правда? Ты ещё потребуй ответа для отрицательных m и n

А как же для исходной задачи m = n = 4?

k = m + m % 2 + n + n % 2; 
k = 4 + 4 % 2 + 4 + 4 % 2 = 12;

А решения есть уже для 8 ходов?

А для m = n = 2 минимум равен 4 ходам. По формуле — 6.

Евгений

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

P>>>>

P>>>>k = m+m%2 + n+n%2; 
P>>>>

M>А как же для исходной задачи m = n = 4?

M>

M>k = m + m % 2 + n + n % 2; 
M>k = 4 + 4 % 2 + 4 + 4 % 2 = 12; 
M>

M>А решения есть уже для 8 ходов?

M>А для m = n = 2 минимум равен 4 ходам. По формуле — 6.
M>

Кто-то из нас тормозит

Я всегда считал , что 4%2=0
Поэтому 4+4%2+4+4%2 = 4+4 = 8

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

P>Кто-то из нас тормозит

Ой, это наверное я.

P>Я всегда считал , что 4%2=0

Перепутал % с целочисленным делением

P>Поэтому 4+4%2+4+4%2 = 4+4 = 8

Евгений

Здравствуйте, Олег Гашев, Вы писали:

ОГ>А если так:

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

Обратите внимание на аналогию с программой движения робота в лабиринте.
Помните такую?

Если мы будем подсчитывать не такты, а количество передач между компьютерами,
то получим задачу о минимальной длине программы выодящей робота из (в данном
случае — прямоугольного) лабиринта. Начав с произвольной клетки-компьютера,
надо побывать во всех остальных.

Наверное.

Евгений

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

M>Обратите внимание на аналогию с программой движения робота в лабиринте.
M>Если мы будем подсчитывать не такты, а количество передач между компьютерами,
M>то получим задачу о минимальной длине программы выодящей робота из (в данном
M>случае — прямоугольного) лабиринта. Начав с произвольной клетки-компьютера,
M>надо побывать во всех остальных.

У меня тоже было некое дежа вю. Но думаю, аналогия неполная — там робот один, а здесь можно (и нужно) делать одновременные транзакции. Поэтому думаю, что из "пустого" (без внутренних стенок) лабиринта робот за 8 ходов никак не выберется. Кстати новая номинация в заглохшем конкурсе

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

P>Здравствуйте, Олег Гашев, Вы писали:

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

P>>>

P>>>k = m+m%2 + n+n%2; 
P>>>

ОГ>>m=1, n=3?

P>Да, поймал. Для (m==1 || n==1) простая формула не работает.

Можно немного апгрейдить идею, которая не будет работать только для (m==1 && n == 1):

Km = ({m/2}*2) + 2*[m-({m/2}*2)];
Kn = ({n/2}*2) + 2*[n-({n/2}*2)];
K = Km + Kn;

P.S.
Интересно кто-нить видел решетку 1х1.

Деление — целочисленное

Здравствуйте, Олег Гашев, Вы писали:

ОГ>Попытаюсь усложнить условие задачи. Условие смотритездесь. Мы рассматривали сеть из 16 компьютеров. Вопрос оказался довольно простым.

ОГ>А если так:

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

Не смотрите то, что я писал раньше

, тама косяк... очередной
вот решение (согласно формуле Pushkin-a по алгоритму Михаила Можаева):

k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}

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

U>вот решение (согласно формуле Pushkin-a по алгоритму Михаила Можаева):
U>

U>k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}
U>

Давайте посморим на эту задачу по другому. Как мы находим решение? Снала мы передаем информацию по верикали, потом по горизонтали. Взьмем для простоты линейный вариант- 3 компьютера по вертикали. Нам нужно 4 такта передать всю информацию. Теперь рассмотрим схему 1х3. Она ничем не отличается от предыдущей, но в формуле используется 1(m).

Теперь давайте рассмотрим схему 1х1х3. По Вашей формуле получается

>\

k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}+{[(p/2)*2] + [(p-2)%2] + (p%2)}

Что не является верным.

Здравствуйте, Олег Гашев, Вы писали:

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

U>>вот решение (согласно формуле Pushkin-a по алгоритму Михаила Можаева):
U>>

U>>k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}
U>>

ОГ>Давайте посморим на эту задачу по другому. Как мы находим решение? Снала мы передаем информацию по верикали, потом по горизонтали. Взьмем для простоты линейный вариант- 3 компьютера по вертикали. Нам нужно 4 такта передать всю информацию. Теперь рассмотрим схему 1х3. Она ничем не отличается от предыдущей, но в формуле используется 1(m).

ОГ>Теперь давайте рассмотрим схему 1х1х3. По Вашей формуле получается

>>\

ОГ>k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}+{[(p/2)*2] + [(p-2)%2] + (p%2)} 
ОГ>

ОГ>Что не является верным.

Во — первых: в формуле используется целочисленное деление (то есть: ((3/2)*2) = 2).
Во — вторых: для варианта 1х1х3 получаем => (0 + (-1) + 1) + (0 + (-1) + 1) + (2 + 1 + 1) = 4, Что есть на мой взгляд правильно.
Или нет?

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

U
U>Во — первых: в формуле используется целочисленное деление (то есть: ((3/2)*2) = 2).
U>Во — вторых: для варианта 1х1х3 получаем => (0 + (-1) + 1) + (0 + (-1) + 1) + (2 + 1 + 1) = 4, Что есть на мой взгляд правильно.
U>Или нет?

(1-2)%2=(-1)%2=1

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

А>(1-2)%2=(-1)%2=1

Не знаю... но мне C# подтвердил, мою правоту... на других языках не проверял, в том числе и С/С++, но я практически уверен, что и на них будет:
(-1)%2 = -1

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

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

А>>(1-2)%2=(-1)%2=1

U>Не знаю... но мне C# подтвердил, мою правоту... на других языках не проверял, в том числе и С/С++, но я практически уверен, что и на них будет:
U>(-1)%2 = -1

Я птица-говорун, даю спррравку

В программировании (C/C++)
(-1) % 2 = -1

В математике
(-1) mod 2 = 1

PS
Охота вам спорить на эту тему?

Лучше бы доказали, что для нормальных сеток (не цепочек) алгоритм Можаева оптимален. Или наоборот.

	От:	Олег Гашев
	Дата:	23.03.03 19:35
	Оценка:

От:	Pushkin	www.linkbit.com
Дата:	24.03.03 11:14
Оценка:

	От:	Олег Гашев
	Дата:	24.03.03 21:21
	Оценка:

От:	Pushkin	www.linkbit.com
Дата:	25.03.03 06:15
Оценка:

	От:	mrhru
	Дата:	25.03.03 06:20
	Оценка:

	От:	uzzy
	Дата:	27.03.03 04:30
	Оценка:

	От:	Аноним
	Дата:	27.03.03 15:38
	Оценка:

	От:	uzzy
	Дата:	28.03.03 04:17
	Оценка: