| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Интересные и занимательные задачи по программированию > задача о замке |
| Автор: Aellipsis 10.10.2011, 14:47 |
| Задано прямоугольное поле, разбитое на ячейки. Некоторые из ячеек закрыты, а некоторые открыты. При изменении состояния какойлибо ячейки, т.е. при ее закрытии или открытии, все ячейки, находящиеся на «кресте» (на общей с ней вертикали или на общей горизонтали), меняют свое состояние на противоположное. Задача состоит в том, чтобы путем переключения определенных ячеек открыть замок, т.е. сделать все его ячейки открытыми. Перебором данную задачу даже при относительно небольших размерах замка решить затруднительно. Однако она просто решается даже в уме по алгоритму, основанному на существовании инварианта в системе замка. Знает ли кто эту задачу? |
| Автор: Akina 10.10.2011, 14:58 |
| Обычная игра, одна из разновидностей Quinto... |
| Автор: fobbos08 18.10.2011, 23:18 |
| Задачка интересная, уже несколько дней думаю как ее записать, вот только не могу придумать. Aellipsis можешь написать принцип решения? Прост очень интересно знать как она решается. |
| Автор: Akina 19.10.2011, 08:27 | ||
Принцип - уменьшение размера области парными переворотами (нормализация крайних одной горизонтали и одной вертикали) до приведения области в полосу. Непарный переворот - за счёт угловой клетки на пересечении нормализуемых вертикали и горизонтали. |
| Автор: Rigid 19.10.2011, 09:10 |
| Алгоритм следующий: 1) запоминаем все ячейки с открытым замком 2) переключаем замки во всех ячейках которые запомнили в пункте 1 3) проверяем, если замок открыт - все ок, иначе двигаем на пункт 1 Обычно решение находится за одну-две итерации |
| Автор: fobbos08 19.10.2011, 16:34 |
| спасибо буду пробовать |
| Автор: fobbos08 24.10.2011, 21:22 |
| возник вопрос, скорее всего я что то не так делаю, но все же 101 101 010 у этого варианта есть решение? так как у меня не получается его решить |
