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
Охота вам спорить на эту тему? Лучше бы доказали, что для нормальных сеток (не цепочек) алгоритм Можаева оптимален. Или наоборот.
Сеть компьютеров-2
От: Олег Гашев
Дата: 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
От: Олег Гашев
Дата: 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
От: Олег Гашев
Дата: 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
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.