Инвертирование шахматной доски, Задачка на логику... Опции

[Zxzc]

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

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

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

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

Сообщение отредактировано: Zxzc - 1.05.2006 22:36

[Zxzc]

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

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

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


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



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

Сообщение отредактировано: volvo - 3.05.2006 14:24