Здравствуйте, uzzy, Вы писали:
U>Здравствуйте, Аноним, Вы писали:
А>>(1-2)%2=(-1)%2=1
U>Не знаю... но мне C# подтвердил, мою правоту... на других языках не проверял, в том числе и С/С++, но я практически уверен, что и на них будет: U>(-1)%2 = -1
Я птица-говорун, даю спррравку
В программировании (C/C++)
(-1) % 2 = -1
В математике
(-1) mod 2 = 1
PS
Охота вам спорить на эту тему? Лучше бы доказали, что для нормальных сеток (не цепочек) алгоритм Можаева оптимален. Или наоборот.
. Мы рассматривали сеть из 16 компьютеров. Вопрос оказался довольно простым.
А если так:
m*n компьютеров связаны в сеть в виде решетки m*n.
В памяти каждого имеется своя информация. За один
такт компьютер может передать ИЛИ принять от ОДHОГО
из соседей информацию любого объема.
За сколько тактов и каким образом ВСЕ компьютеры
могут получить ВСЮ информацию?
Здравствуйте, Олег Гашев, Вы писали:
ОГ>Здравствуйте, 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.
Здравствуйте, Олег Гашев, Вы писали:
ОГ>А если так:
ОГ>m*n компьютеров связаны в сеть в виде решетки m*n. ОГ>В памяти каждого имеется своя информация. За один ОГ>такт компьютер может передать ИЛИ принять от ОДHОГО ОГ>из соседей информацию любого объема. ОГ>За сколько тактов и каким образом ВСЕ компьютеры ОГ>могут получить ВСЮ информацию?
Обратите внимание на аналогию с программой движения робота в лабиринте.
Помните такую?
Если мы будем подсчитывать не такты, а количество передач между компьютерами,
то получим задачу о минимальной длине программы выодящей робота из (в данном
случае — прямоугольного) лабиринта. Начав с произвольной клетки-компьютера,
надо побывать во всех остальных.
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) простая формула не работает. 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;
. Мы рассматривали сеть из 16 компьютеров. Вопрос оказался довольно простым.
ОГ>А если так:
ОГ>m*n компьютеров связаны в сеть в виде решетки m*n. ОГ>В памяти каждого имеется своя информация. За один ОГ>такт компьютер может передать ИЛИ принять от ОДHОГО ОГ>из соседей информацию любого объема. ОГ>За сколько тактов и каким образом ВСЕ компьютеры ОГ>могут получить ВСЮ информацию?
Давайте посморим на эту задачу по другому. Как мы находим решение? Снала мы передаем информацию по верикали, потом по горизонтали. Взьмем для простоты линейный вариант- 3 компьютера по вертикали. Нам нужно 4 такта передать всю информацию. Теперь рассмотрим схему 1х3. Она ничем не отличается от предыдущей, но в формуле используется 1(m).
Теперь давайте рассмотрим схему 1х1х3. По Вашей формуле получается
>\
ОГ>Давайте посморим на эту задачу по другому. Как мы находим решение? Снала мы передаем информацию по верикали, потом по горизонтали. Взьмем для простоты линейный вариант- 3 компьютера по вертикали. Нам нужно 4 такта передать всю информацию. Теперь рассмотрим схему 1х3. Она ничем не отличается от предыдущей, но в формуле используется 1(m).
ОГ>Теперь давайте рассмотрим схему 1х1х3. По Вашей формуле получается
>>\
Во — первых: в формуле используется целочисленное деление (то есть: ((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
Не знаю... но мне C# подтвердил, мою правоту... на других языках не проверял, в том числе и С/С++, но я практически уверен, что и на них будет: (-1)%2 = -1