На поле 4 х 4 клетки могут принимать одно из двух состояний (условно "." или "о").
За один ход игры можно выбрать некоторую клетку и изменить её состояние на противоположное, при этом "перевернутся" все клетки, расположенные на слева/справа и сверху/снизу от выбранной. (Игрушка от "Буки", если не ошибаюсь)
.... ..о.
..о. оо.о
.... -> ..о.
.... ..о.
В начале игры, все клетки находятся в произвольном состоянии.
Требуется составить алгоритм, переводящий клетки в одинаковое состояние за минимальное количество ходов (и попробуйте доказать, что этот алгоритм "минимален").
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
M>На поле 4 х 4 клетки могут принимать одно из двух состояний (условно "." или "о"). M>За один ход игры можно выбрать некоторую клетку и изменить её состояние на противоположное, при этом "перевернутся" все клетки, расположенные на слева/справа и сверху/снизу от выбранной. (Игрушка от "Буки", если не ошибаюсь)
Ошибаешься. Если ты имеешь в виду Лохотронщика, то там игра несколько другая.
Описанная тобой игрушка была в Братьях Пилотах.
M>
M>В начале игры, все клетки находятся в произвольном состоянии. M>Требуется составить алгоритм, переводящий клетки в одинаковое состояние за минимальное количество ходов (и попробуйте доказать, что этот алгоритм "минимален").
В Ru.math эта задача была решена в случае поля N*N.
С четным N там все просто, а вот с нечетным довольно весело.
Алгоритм для четных N — берем клетку и считаем число неправильных клеток справа-слева и сверху-снизу от нее, включая ее саму. Если число четно — пропускаем, нечетно — переворачиваем.
Для нечетных: чтобы задача была разрешима, нужно чтобы четность числа неправильных клеток а строке совпадала с четностью числа неправильных клеток в столце с таким же номером (если мне склероз не изменяет). Тогда можно просто переворачивать все неправильно повернутые клетки.
Здравствуйте, mrhru, Вы писали:
M>На поле 4 х 4 клетки могут принимать одно из двух состояний (условно "." или "о"). M>За один ход игры можно выбрать некоторую клетку и изменить её состояние на противоположное, при этом "перевернутся" все клетки, расположенные на слева/справа и сверху/снизу от выбранной. (Игрушка от "Буки", если не ошибаюсь)
А что делать, если по условию переворачиваются только 4 соседних с выбранной?
Здравствуйте, m.a.g., Вы писали:
M>>На поле 4 х 4 клетки могут принимать одно из двух состояний (условно "." или "о"). M>>За один ход игры можно выбрать некоторую клетку и изменить её состояние на противоположное, при этом "перевернутся" все клетки, расположенные на слева/справа и сверху/снизу от выбранной. (Игрушка от "Буки", если не ошибаюсь)
MAG>А что делать, если по условию переворачиваются только 4 соседних с выбранной?
Ты хотел сказать не больше 4-х соседних? У угловых клеток и клеток, примыкающих к бокам, соседей меньше.
Здравствуйте, Lexey, Вы писали:
L>Ошибаешься. Если ты имеешь в виду Лохотронщика, то там игра несколько другая. L>Описанная тобой игрушка была в Братьях Пилотах.
В Пилотах была как составная часть, а была еще и как отдельная игрушка.
...
L>В Ru.math эта задача была решена в случае поля N*N. L>С четным N там все просто, а вот с нечетным довольно весело.
L>Алгоритм для четных N — берем клетку и считаем число неправильных клеток справа-слева и сверху-снизу от нее, включая ее саму. Если число четно — пропускаем, нечетно — переворачиваем.
А это "минимальный" алгоритм?
Евгений, с приветом (но без остроумной подписи, к сожалению )
Здравствуйте, mrhru, Вы писали:
M>В Пилотах была как составная часть, а была еще и как отдельная игрушка.
May be.Мне не попадалась.
L>>В Ru.math эта задача была решена в случае поля N*N. L>>С четным N там все просто, а вот с нечетным довольно весело.
L>>Алгоритм для четных N — берем клетку и считаем число неправильных клеток справа-слева и сверху-снизу от нее, включая ее саму. Если число четно — пропускаем, нечетно — переворачиваем.
M>А это "минимальный" алгоритм?
Здравствуйте, Lexey, Вы писали:
MAG>>А что делать, если по условию переворачиваются только 4 соседних с выбранной? L>Ты хотел сказать не больше 4-х соседних? У угловых клеток и клеток, примыкающих к бокам, соседей меньше.
Да, конечно.
... << Павел Фомичев [Музыка Эльфов] Листопад >> ...
Здравствуйте, Lexey, Вы писали:
L>>>Алгоритм для четных N — берем клетку и считаем число неправильных клеток справа-слева и сверху-снизу от нее, включая ее саму. Если число четно — пропускаем, нечетно — переворачиваем.
M>>А это "минимальный" алгоритм?
L>Да, afair.
Да, разумеется. Дело в том, что при четных N "четность" клетки меняется ТОЛЬКО при переворачивании ее. Поэтому если она "нечетна" то ее придется перевернуть.
Здравствуйте, mrhru, Вы писали:
M>На поле 4 х 4 клетки могут принимать одно из двух состояний (условно "." или "о"). M>За один ход игры можно выбрать некоторую клетку и изменить её состояние на противоположное, при этом "перевернутся" все клетки, расположенные на слева/справа и сверху/снизу от выбранной. (Игрушка от "Буки", если не ошибаюсь)
M>
M>В начале игры, все клетки находятся в произвольном состоянии. M>Требуется составить алгоритм, переводящий клетки в одинаковое состояние за минимальное количество ходов (и попробуйте доказать, что этот алгоритм "минимален").
В свое время целый вечер потратил на решение. Зато теперь могу объяснить как оптимально преводить любую позицию в любую другую. Я приведу только структуру решения не углубляясь в "технические" детали, которые при желании можете проверить сами.
Для простоты будем считать, что поле заполнено единицами и нулями.
Назовем дополнительной матрицу образованную следующим образом. Для каждого поля исходной матрицы нарисуем "крест" состоящий из объединения строки и столбца, которым принадлежит данная клетка. Если кол-во единиц в этом кресте нечетно, то ставим в соответствующее поле дополнительной матрицы 1, если четно 0.
Верно следующее утверждение.
1. Ход в игре соответсвует изменению состояния ОДНОЙ соответсвующей клетки в дополнительной матрицы.
Теперь, если нам удастся доказать, что для дополнительной матрицы любого вида существует ровно одна исходная, то мы сможем сопоставить исходной игре тривиальную игру на дополнительных матрицах, где элементарно получается оптимальное решение. Так вот, взаимно однозначное соответсвие исходных и дополнительных матриц следует из следующего красивого утверждения.
2. Дополнительной к дополнительной матрице является исходная.
Доказательство этих двух утверждений я оставляю читателям в качестве самостоятельного упражнеия (тем более, что сам я их забыл).
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, mrhru, Вы писали:
... (извиняюсь)
Вот то, что мне пришло в голову:
Для переворачивания только одной клетки необходимо "явно" перевернуть и все клетки в "кресте" ею образуемом, что очевидно. Остальные клетки при этом остаются в исходных состояниях.
Применяя последовательно этот метод ко всем неперевернутым клеткам, мы, естественно, "обнулим" матрицу. Одновременно запоминаем число "явно" переворачиваемых клеток.
В итоге, для получения "минимального" алгоритма, "явно" переверачиваем один раз только те клетки, у которых число их "явного" переворачивания на предыдущем этапе — нечетное.
Привет, MichaelP!
MP>Верно следующее утверждение. MP>1. Ход в игре соответсвует изменению состояния ОДНОЙ соответсвующей клетки в дополнительной матрицы. MP>Теперь, если нам удастся доказать, что для дополнительной матрицы любого вида существует ровно одна исходная, то мы сможем сопоставить исходной игре тривиальную игру на дополнительных матрицах, где элементарно получается оптимальное решение. Так вот, взаимно однозначное соответсвие исходных и дополнительных матриц следует из следующего красивого утверждения. MP>2. Дополнительной к дополнительной матрице является исходная.
MP>Доказательство этих двух утверждений я оставляю читателям в качестве самостоятельного упражнеия (тем более, что сам я их забыл).
Хорошее решение! С чистой совестью ставлю заработанные тобой 12 баллов!
На себя же попробую взять ответственность доказать оба утверждения.
1. Если клетка находится в одной строке с инвертируемой или в одном столбце с ней, но с ней не совпадает, то количество инвертируемых клеток, которые имеют для нее значение при построении дополнительной матрицы, равно 4. Если же она стоит где-то еще, то количество инвертируемых клеток, которые находятся в ее строке или столбце, равно 2. Каждое инвертирование добавляет или убирает единицу. Следовательно четность числа единиц для этих фишек не изменяется. Клетка, которая находится в центре инвертирования имеет 7 инвертируемых клеток в строке и столбце. Следовательно у нее и только у нее меняется четность числа единиц в строке и столбце.
2. Значение в дополнительной матрице в каждой клетке равно сумме в GF(2) всех элементов исходной матрицы, стоящих с инвертируемым значением в одной строке или в одном столбце.
Введем следующие обозначения:
4
r = SUM a - сумма элементов i-ой строки по модулю 2;
i j=1 ij
4
c = SUM a - сумма элементов j-ого столбца по модулю 2;
j i=1 ij
s - сумма всех элементов матрицы.
Тогда
a' = r + c + a , где суммирование ведется по модулю 2.
ij i j ij
Далее,
4 4
a'' = SUM a' + SUM a' + a' = 6 * r + 2 * s + 6 * c + a = a ,
ij q=1 iq p=1 pj ij i j ij ij
где умножение на натуральное число предполагает сумму сответствующего числа слагаемых.
Итак, исходя из доказанного, мы имеем взаимнооднозначное соответствие между решениями прямой задачи и дополнительной. Количество ходов в решении прямой и соответствующей ей обратной задачи совпадает. Таким образом, оптимальному решению прямой задачи соответствует оптимальное решение дополнительной, которое очевидно — убрать все, что лишнее, и добавить, чего не хватает.
Оптимальное число ходов: строим дополнительные матрицы к исходной и итоговой, считаем количество несовпадающих элементов.
)
Apapa.gif)
