Шахматная доска используется во множестве математических задач. Рассмотрим задачи о перемещении коня по шахматной доске.
Задача 1.
Задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача имеет решение, и не единственное. Её можно решить с помощью теории графов. Каждая клетка соответствует вершине графа, ход коня - ребру, соединяющему две вершины. Задача сводится к нахождению гамильтонова цикла в этом графе. Задачи решать многие математики, один из них Леонард Эйлер.
Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся непройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.
Задача 2.
Ответим на вопрос: за сколько ходов конь может дойти до каждой клетки доски?
Конь "меняет" цвет клетки одним ходом, значит попасть в соседнюю клетку можно за три хода: Б-Ч-Б-Ч или Ч-Б-Ч-Б.
Если конь еще не посетил некоторую клетку, и в нее можно попасть из клетки с номером n, то в нее можно попасть (n+1) способом. Все клетки с номером n будем обрабатывать одновременно.
Зададим систему координат на шахматной доске. Изменить сумму координат конь может максимум на три (если сдвиг по ОХ - 2, то по ОY - 1 и наоборот).
Задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача имеет решение, и не единственное. Её можно решить с помощью теории графов. Каждая клетка соответствует вершине графа, ход коня - ребру, соединяющему две вершины. Задача сводится к нахождению гамильтонова цикла в этом графе. Задачи решать многие математики, один из них Леонард Эйлер.
Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся непройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.
Задача 2.
Ответим на вопрос: за сколько ходов конь может дойти до каждой клетки доски?
Конь "меняет" цвет клетки одним ходом, значит попасть в соседнюю клетку можно за три хода: Б-Ч-Б-Ч или Ч-Б-Ч-Б.
Если конь еще не посетил некоторую клетку, и в нее можно попасть из клетки с номером n, то в нее можно попасть (n+1) способом. Все клетки с номером n будем обрабатывать одновременно.
Зададим систему координат на шахматной доске. Изменить сумму координат конь может максимум на три (если сдвиг по ОХ - 2, то по ОY - 1 и наоборот).
Комментариев нет:
Отправить комментарий