Помощь - Поиск - Пользователи - Календарь
Полная версия: Инвертирование шахматной доски
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Zxzc
Вот интересная задачка:

Стоило Астериксу ступить на шахматную доску, как клетка под ним отобразила свой цвет.
Сможет ли Астерикс перекрасить все клетки доски в единый цвет, если он не может ходить по диагонали?

И соответствующая задача на программирование:

Каково минимально возможное число его ходов?
Lapp
Цитата(Zxzc @ 1.05.2006 17:40) *

.. клетка под ним отобразила свой цвет.

Что это значит?.. Может, изменила свой цвет? преобразила?
Zxzc
Ну, отобразила это от слова отразить(как в Paint), то есть сменила свой цвет на противоположный(черный - на белый; белый на черный)
GoodWind
наступать на клетки, на которых уже был можно?
Lapp
Цитата(Zxzc @ 2.05.2006 6:51) *

Ну, отобразила это от слова отразить

??? blink.gif blink.gif blink.gif
Zxzc, загляни, пожалуйста, в словарь (типа Даля..) и не придумывай новых значений (по сути, противоположных) для нормальных русских слов smile.gif. O'kay?

Касательно задачи.
Вытягиваем всю доску в одну дорожку (змейкой): 64 чередующихся Ч и Б клетки:
Ч Б Ч Б Ч Б Ч Б ...
Астерикс стоит как бы перед первой (левой) клеткой. Далее обозначаю направление хода стрелочкой и пишу его результат. Клетку, где находится Астерикс, выделяю жирным.

->
Б Б Ч Б Ч Б Ч Б ...
->
Б Ч Ч Б Ч Б Ч Б ...
->
Б Ч Б Б Ч Б Ч Б ...
<-
Б Б Б Б Ч Б Ч Б ...
->
Б Б Ч Б Ч Б Ч Б ...
->
Б Б Ч Ч Ч Б Ч Б ...
<-
Б Б Б Ч Ч Б Ч Б ...
->
Б Б Б Б Ч Б Ч Б ...

В результате этой комбинации 4 первых клетки стали белыми, а перед Астериксом лежит та же дорожка, но не в 64 клетки, а в 60. Каждый раз делая эту комбинацию, он будет по 4 клетки превращать в белые. Значит, закончит свою работу за 64/4=16 комбинаций. Каждая комбинация содержит 8 ходов, следовательно всего потребуется 16х8=128 ходов. Почему-то мне кажется, что это число ходов уменьшить нельзя, но я могу ошибаться..
Zxzc
Так, только я решал задачку на плоскости, т.е. за 8 ходов перекрашивал квадрат 2x2 в единый цвет. Но вот вопрос: что значит фраза "соответствующая задачка на программирование"? dry.gif
По-моему это обычная логическая задачка...
Zxzc
Ай-яй-яй!! mad.gif Как же я так! smile.gif За 8 ходов... Вот, я придумал как за 4 хода:
Разделим доску на 16 квадратов(2x2). В каждом квадрате можно выполнить 2 комбинации:
I - проход через квадрат с перекрашиванием.
II - поворот в квадрате с перекрашиванием.
(см. рисунки).
Нажмите для просмотра прикрепленного файла
И на 2 рисунке отражено как можно переходить от квадрата к квадрату с помощью этих комбинаций.
Нажмите для просмотра прикрепленного файла
Таким образом, любая комбинация предусматривает закрашивание квадрата за 4 хода, и всего у нас получиться 16x4=64 хода. Я думаю задачка решена. cool.gif
Ну почему на программирование? dry.gif

excl.gif
Используем формат PNG при прикреплении графики и получаем:

Нажмите для просмотра прикрепленного файла Нажмите для просмотра прикрепленного файла

А теперь сравни размеры (1.87Кб против 243Кб, и 3.47Кб против 192Кб во второй картинке...) Заметь, БЕЗ потери качества
Lapp
Цитата(Zxzc @ 3.05.2006 0:30) *

получиться 16x4=64 хода. Я думаю задачка решена. cool.gif
Ну почему на программирование? dry.gif

Да, красиво! Действительно, идя не по линейке, можно обходить некоторые клетки, что экономит ходы.
Респект! smile.gif

А с программированием - ну, ошиблись они.. sad.gif
Бравый генерал
//offtop
Zxzc, пожалуйста, сохраняй картинки в подходящие форматы: черно-белые картинки - Monochrome Bitmap; картинки, содержащие основные цвета, не содержащие много разных оттенков - GIF, для остальных - JPEG. Про 24-bit Bitmap'ы - забудь, они не для веба smile.gif Это просто просьба. Потому что с диал-ап'ом закачивать такие BMP - весьма жестокое мероприятие... smile.gif
(например, первая картинка сохраненная в формате GIF будет весить всего 3.5 Кб smile.gif)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.