Версия для печати темы

Автор: Zxzc 1.05.2006 21:40

Вот интересная задачка:

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

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

Каково минимально возможное число его ходов?

Автор: lapp 2.05.2006 8:25

Что это значит?.. Может, изменила свой цвет? преобразила?

Автор: Zxzc 2.05.2006 10:51

Ну, отобразила это от слова отразить(как в Paint), то есть сменила свой цвет на противоположный(черный - на белый; белый на черный)

Автор: GoodWind 2.05.2006 11:55

наступать на клетки, на которых уже был можно?

Автор: lapp 2.05.2006 12:31

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

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

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

В результате этой комбинации 4 первых клетки стали белыми, а перед Астериксом лежит та же дорожка, но не в 64 клетки, а в 60. Каждый раз делая эту комбинацию, он будет по 4 клетки превращать в белые. Значит, закончит свою работу за 64/4=16 комбинаций. Каждая комбинация содержит 8 ходов, следовательно всего потребуется 16х8=128 ходов. Почему-то мне кажется, что это число ходов уменьшить нельзя, но я могу ошибаться..

Автор: Zxzc 3.05.2006 1:08

Так, только я решал задачку на плоскости, т.е. за 8 ходов перекрашивал квадрат 2x2 в единый цвет. Но вот вопрос: что значит фраза "соответствующая задачка на программирование"?
По-моему это обычная логическая задачка...

Автор: Zxzc 3.05.2006 4:30

Ай-яй-яй!! Как же я так! За 8 ходов... Вот, я придумал как за 4 хода:
Разделим доску на 16 квадратов(2x2). В каждом квадрате можно выполнить 2 комбинации:
I - проход через квадрат с перекрашиванием.
II - поворот в квадрате с перекрашиванием.
(см. рисунки).
 kombo.bmp ( 243.59 килобайт ) Кол-во скачиваний: 897

И на 2 рисунке отражено как можно переходить от квадрата к квадрату с помощью этих комбинаций.
 Shah.bmp ( 192.05 килобайт ) Кол-во скачиваний: 879

Таким образом, любая комбинация предусматривает закрашивание квадрата за 4 хода, и всего у нас получиться 16x4=64 хода. Я думаю задачка решена.
Ну почему на программирование?


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



А теперь сравни размеры (1.87Кб против 243Кб, и 3.47Кб против 192Кб во второй картинке...) Заметь, БЕЗ потери качества

Автор: lapp 3.05.2006 5:00

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

А с программированием - ну, ошиблись они..

Автор: Бравый генерал 3.05.2006 5:08

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