|
Модераторы: Alx, Fixin |
|
Aellipsis |
|
|||
Новичок Профиль Группа: Участник Сообщений: 9 Регистрация: 5.10.2011 Репутация: нет Всего: нет |
Задано прямоугольное поле, разбитое на ячейки. Некоторые из ячеек закрыты, а некоторые открыты. При изменении состояния какойлибо ячейки, т.е. при ее закрытии или открытии, все ячейки, находящиеся на «кресте» (на общей с ней вертикали или на общей горизонтали), меняют свое состояние на противоположное. Задача состоит в том, чтобы путем переключения определенных ячеек открыть замок, т.е. сделать все его ячейки открытыми. Перебором данную задачу даже при относительно небольших размерах замка решить затруднительно. Однако она просто решается даже в уме по алгоритму, основанному на существовании инварианта в системе замка.
Знает ли кто эту задачу? |
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 2 Всего: 453 |
Обычная игра, одна из разновидностей Quinto...
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
fobbos08 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 3 Регистрация: 18.10.2011 Репутация: нет Всего: нет |
Задачка интересная, уже несколько дней думаю как ее записать, вот только не могу придумать. Aellipsis можешь написать принцип решения? Прост очень интересно знать как она решается.
|
|||
|
||||
Akina |
|
|||
Советчик Профиль Группа: Модератор Сообщений: 20570 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 2 Всего: 453 |
Принцип - уменьшение размера области парными переворотами (нормализация крайних одной горизонтали и одной вертикали) до приведения области в полосу. Непарный переворот - за счёт угловой клетки на пересечении нормализуемых вертикали и горизонтали. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Rigid |
|
|||
Новичок Профиль Группа: Участник Сообщений: 13 Регистрация: 4.1.2007 Репутация: нет Всего: нет |
Алгоритм следующий:
1) запоминаем все ячейки с открытым замком 2) переключаем замки во всех ячейках которые запомнили в пункте 1 3) проверяем, если замок открыт - все ок, иначе двигаем на пункт 1 Обычно решение находится за одну-две итерации |
|||
|
||||
fobbos08 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 3 Регистрация: 18.10.2011 Репутация: нет Всего: нет |
спасибо
буду пробовать |
|||
|
||||
fobbos08 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 3 Регистрация: 18.10.2011 Репутация: нет Всего: нет |
возник вопрос, скорее всего я что то не так делаю, но все же
101 101 010 у этого варианта есть решение? так как у меня не получается его решить |
|||
|
||||
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Интересные и занимательные задачи по программированию | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |