Сеть компьютеров-2
От: Олег Гашев http://files.rsdn.org/5774/button-debian.png
Дата: 23.03.03 19:35
Оценка:
Попытаюсь усложнить условие задачи. Условие смотритездесь
Автор: Oleg_Gashev
Дата: 20.03.03
. Мы рассматривали сеть из 16 компьютеров. Вопрос оказался довольно простым.

А если так:

m*n компьютеров связаны в сеть в виде решетки m*n.
В памяти каждого имеется своя информация. За один
такт компьютер может передать ИЛИ принять от ОДHОГО
из соседей информацию любого объема.
За сколько тактов и каким образом ВСЕ компьютеры
могут получить ВСЮ информацию?
Либо я найду путь, либо проложу его. © Свифт
Re: Сеть компьютеров-2
От: Pushkin Россия www.linkbit.com
Дата: 24.03.03 11:14
Оценка:
Здравствуйте, Олег Гашев, Вы писали:

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


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

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


Хотя так и осталось не доказанным утверждение (вполне возможно правильное), что стратегия "сначала строки, потом независимо столбцы" наилучшая.
Re[2]: Сеть компьютеров-2
От: Олег Гашев http://files.rsdn.org/5774/button-debian.png
Дата: 24.03.03 21:21
Оценка:
Здравствуйте, Pushkin, Вы писали:

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



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


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


m=1, n=3?
Либо я найду путь, либо проложу его. © Свифт
Re[3]: Сеть компьютеров-2
От: Pushkin Россия www.linkbit.com
Дата: 25.03.03 06:15
Оценка:
Здравствуйте, Олег Гашев, Вы писали:

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


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


ОГ>m=1, n=3?


Да, поймал. Для (m==1 || n==1) простая формула не работает.
Т.е. она ещё проще становится, но слить вместе — совсем крокодил получится.
Но это и не сетка, правда? Ты ещё потребуй ответа для отрицательных m и n
Re[4]: Сеть компьютеров-2
От: mrhru Россия  
Дата: 25.03.03 06:20
Оценка:
Здравствуйте, 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.
Евгений
Re[5]: Сеть компьютеров-2
От: Pushkin Россия www.linkbit.com
Дата: 25.03.03 06:25
Оценка:
Здравствуйте, 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
Re[6]: Сеть компьютеров-2
От: mrhru Россия  
Дата: 25.03.03 06:33
Оценка:
Здравствуйте, Pushkin, Вы писали:

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


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

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


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

P>Поэтому 4+4%2+4+4%2 = 4+4 = 8
Евгений
Re: Сеть компьютеров-2
От: mrhru Россия  
Дата: 25.03.03 06:50
Оценка:
Здравствуйте, Олег Гашев, Вы писали:

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


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

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

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

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

Наверное.
Евгений
Re[2]: Сеть компьютеров-2
От: Pushkin Россия www.linkbit.com
Дата: 25.03.03 06:58
Оценка:
Здравствуйте, mrhru, Вы писали:


M>Обратите внимание на аналогию с программой движения робота в лабиринте.

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


У меня тоже было некое дежа вю. Но думаю, аналогия неполная — там робот один, а здесь можно (и нужно) делать одновременные транзакции. Поэтому думаю, что из "пустого" (без внутренних стенок) лабиринта робот за 8 ходов никак не выберется. Кстати новая номинация в заглохшем конкурсе
Re[4]: Сеть компьютеров-2
От: uzzy Россия  
Дата: 25.03.03 10:38
Оценка:
Здравствуйте, 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==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.
Re[5]: Примечание
От: uzzy Россия  
Дата: 25.03.03 10:39
Оценка:
Деление — целочисленное
Re: Сеть компьютеров-2
От: uzzy Россия  
Дата: 25.03.03 12:07
Оценка:
Здравствуйте, Олег Гашев, Вы писали:

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


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


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

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


Не смотрите то, что я писал раньше , тама косяк... очередной
вот решение (согласно формуле Pushkin-a по алгоритму Михаила Можаева
Автор: Pushkin
Дата: 24.03.03
):
k = {[(m/2)*2] + [(m-2)%2] + (m%2)} + {[(n/2)*2] + [(n-2)%2] + (n%2)}
Re[2]: Сеть компьютеров-2
От: Олег Гашев http://files.rsdn.org/5774/button-debian.png
Дата: 26.03.03 20:49
Оценка:
Здравствуйте, uzzy, Вы писали:

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

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)}


Что не является верным.
Либо я найду путь, либо проложу его. © Свифт
Re[3]: Сеть компьютеров-2
От: uzzy Россия  
Дата: 27.03.03 04:30
Оценка:
Здравствуйте, Олег Гашев, Вы писали:

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


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

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, Что есть на мой взгляд правильно.
Или нет?
Re[4]: Сеть компьютеров-2
От: Аноним  
Дата: 27.03.03 15:38
Оценка:
Здравствуйте, 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
Re[5]: Сеть компьютеров-2
От: uzzy Россия  
Дата: 28.03.03 04:17
Оценка:
Здравствуйте, Аноним, Вы писали:

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


Не знаю... но мне C# подтвердил, мою правоту... на других языках не проверял, в том числе и С/С++, но я практически уверен, что и на них будет:
(-1)%2 = -1
Re[6]: Сеть компьютеров-2
От: Pushkin Россия www.linkbit.com
Дата: 28.03.03 06:20
Оценка: 5 (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
Охота вам спорить на эту тему? Лучше бы доказали, что для нормальных сеток (не цепочек) алгоритм Можаева оптимален. Или наоборот.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.