|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 25 Aug 2001 16:43:52
To : Daniel Kamperov
Subject : Задача
--------------------------------------------------------------------------------
Replying to a message of Daniel Kamperov to All:
DK> Существует такой паззл (был реализован, кстати, в "7 госте"):
Там и более сложный в конце реализован ("лицо Стафа") - с тремя состояниями
каждого элемента.
DK> даны 9
DK> элементов, например, цифр, которые могут принимать значения,
DK> например, 0 и 1. Они располагаются в виде матрицы 3x3.
[...]
DK> Можно активировать любой элемент, при этом его значение сменится на
DK> противоположное, при этом изменят своё значение также и его соседи по
DK> горизонтали и вертикали.
[...]
DK> Задача: активируя различные элементы, привести значения всех элементов
DK> матрицы к одному числу - 0 или 1. Можно это сделать как-то, кроме
DK> перебора?
DK> ЗЫ. А как быть с такой ситуацией: элементы могут принимать значения 0,
DK> 1, 2?
Все подобные задачки на самом деле сводятся к решению системы линейных уравнений
(т.е. к линейной алгебре).
================================= Алгоритмы ==================================
From: Max Alekseyev 2:5015/60 06 May 1998 21:56:48
To: Vlad Koshelev
Subj: братья пилоты
==============================================================================
* Crossposted in RU.MATH
Hi, Vlad !
Replying to a message of Vlad Koshelev to All:
VK> В игрульке сабж есть такая задачка: имеется сейф, содержащий 4x4
VK> ручек,
Занумеруем его поля так
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
И будем смотреть на поле как на граф с 16-ю вершинами, в котором ребрами
соединены те вершины, у которых соответствующие им клетки находятся либо в одной
строке, либо в одном столбце.
VK> каждая из которых может принимать одно из 2-х состояний:
VK> повернута вертикально или горизонтально. Требуется перевести все
VK> ручки в горизонтальное положение, причем, поворачивая ручку (i, j),
VK> все ручки строки i и столбца j меняют свое состояние на
VK> противоположное. Алгоритм: горизонтальные ручки представляем, как 0,
VK> вертикальные - 1.
Соответственно, каждому положению будет соответствовать 16-тимерный вектор с
элементами из кольца Z_2={0,1}.
Пусть B - вектор-столбец соответствующий начальному состоянию, E - конечному (к
которому мы хотим привести сейф; в данном случае E=(0,0,0,...,0)).
Тогда решение задачи сводится к отысканию решения уравнения
A*X+B=E
над кольцом Z_2, где X - неизвестный вектор-столбец (соответствующий поворотам
ручек), а A - матрица смежности графа. В нашем случае
[1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0]
[1,1,1,1,0,1,0,0,0,1,0,0,0,1,0,0]
[1,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0]
[1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1]
[1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0]
[0,1,0,0,1,1,1,1,0,1,0,0,0,1,0,0]
[0,0,1,0,1,1,1,1,0,0,1,0,0,0,1,0]
[0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1]
A = [1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0]
[0,1,0,0,0,1,0,0,1,1,1,1,0,1,0,0]
[0,0,1,0,0,0,1,0,1,1,1,1,0,0,1,0]
[0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1]
[1,0,0,0,1,0,0,0,1,0,0,0,1,1,1,1]
[0,1,0,0,0,1,0,0,0,1,0,0,1,1,1,1]
[0,0,1,0,0,0,1,0,0,0,1,0,1,1,1,1]
[0,0,0,1,0,0,0,1,0,0,0,1,1,1,1,1]
В нашем случае она невырождена, поэтому решение можно записать в виде
X=A^{-1}*(E-B)
Кстати, в нашем случае A^{-1}=A (напоминаю, что все действия производятся по mod
2), поэтому решение выглядит так X=A*(E-B).
А если еще учесть, что E - нулевой вектор, то формула принимает вид X=A*B.
VK> Бежим по полученной матрице и проверяем суммы
VK> элементов строки i и столбца j (элемент (i, j) включается в общую
VK> сумму один раз). Если сумма нечетна, ручку (i, j) переворачиваем. Так
VK> за один проход задача решена. То есть
VK> 1 0 1 1 1 0 1 1
VK> 0 1 0 0 Обрабатываем (1, 1) (нумерация с 0) => Сумма = 3 => 1 0 1 1
VK> 1 1 0 1 1 0 0 1
VK> 0 1 0 1 0 0 0 1
^^^^^^^ соответственно, если мы примем это состояние за начальное, т.е.
B=(1,0,1,1,0,1,0,0,1,1,0,1,0,1,0,1), то решение получится
X = (0,0,1,1,1,1,0,0,0,1,0,1,0,0,1,0), что означает, что поворачивать надо ручки
с номерами 3,4,5,6,10,12,15:
- - X X
X X - -
- X - X
- - X -
Это, так сказать, была идея общего решения подобных задач. Теперь ответ на твой
VK> ВОПРОС: Hа чем основан алгоритм? Откуда его можно вывести?
1) Из формулы X=A*B. Так как A - матрица смежности, то первая компонента x1
будет равна сумме элементов первого столбца и первой строки по модулю 2, x2 -
сумме элементов второго столбца и первой строки по mod 2 и т.д. Получаем, что
компоненты вектора X равны 1 только на тех местах, где соответствующая сумма
нечетна. Ч.т.д.
2) Hазовем клетку(ручку) "нечетной", если сумма всех чисел, стоящих с ней в
одной
строке или столбце нечетна. Соответственно, твой алгоритм состоит в поворотах
"нечетных" ручек. Hетрудно видеть, что при таком повороте ручка перестает быть
"нечетной", а все остальные ручки сохраняют свою "четность". Поэтому с каждым
поворотом число "нечетных" ручек уменьшается на 1 и в конце концов становится
равным 0. Hу и последнее наблюдение: состояние без "нечетных" ручек только одно
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Что и требовалось доказать.
VK> Замечания: простой перебор дает 16! ч 4 млрд. вариантов;
Hеправда на самом деле их всего 2^16 (каждую ручку можно повернуть или нет;
двойной поворот=отсутствие оного; повороты разных ручек перестановочны между
собой), а это лишь 65536 вариантов.
VK> ЗЫ. А что делать, если у ручек k состояний? 8|
Все то же самое, только вычисления надо делать над кольцом Z_k={0,1,2,...,k-1}
(то есть по mod k).
Regards, ш.ш
Max ~
==============================================================================
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.6
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Задача |
Daniel Kamperov |
24 Aug 2001 20:26:30 |
 Задача |
Max Alekseyev |
25 Aug 2001 16:43:52 |
|
Re: Задача |
Igor V. Rafienko |
26 Aug 2001 17:11:44 |
  Задача |
Daniel Kamperov |
27 Aug 2001 22:54:10 |
 Re: Задача |
Andrey Dashkovsky |
02 Sep 2001 00:17:16 |
|
Задача |
Vadim Guchenko |
26 Aug 2001 19:38:32 |
|
Задача |
Kluchnikov Eugene |
26 Aug 2001 19:17:59 |
|
Re: Задача |
Igor V. Rafienko |
27 Aug 2001 13:51:26 |
|
Задача |
Kluchnikov Eugene |
27 Aug 2001 18:15:49 |
|
Задача |
Vladimir Namkhoev |
27 Aug 2001 20:03:53 |
|
Re: Задача |
Igor V. Rafienko |
28 Aug 2001 05:00:26 |
 Задача |
Vladimir Namkhoev |
29 Aug 2001 09:57:13 |
|
Задача |
Vladimir Namkhoev |
28 Aug 2001 10:37:31 |
|
Задача |
Vladimir Namkhoev |
28 Aug 2001 11:50:47 |
|
Задача |
Vladimir Namkhoev |
28 Aug 2001 12:50:41 |
|
Задача |
Igor Popyrko |
27 Aug 2001 21:00:00 |
|
|
