Глава 4

черепаха вычерчивает траекторию движения, если в верхней, то черепаха передвигается свободно и ничего не вычерчивает. В этой задаче вы будете моделировать действия черепахи и создавать компьютеризованный эскиз пути.

Используйте массив floor размером 20 на 20 с нулевыми начальными условиями. Считывайте команды из содержащего их массива. Все время отмечайте текущую позицию черепахи и положение пера - нижнее или верхнее. Предполагайте, что черепаха всегда стартует из позиции О, О на полу с верхним положением пера. Ваша программа должна подавать команды черепахе в соответствии со следующими обозначениями:

Предположим, что черепаха находится где-то возле центра комнаты. Следующая программа управления черепахой начертила бы квадрат 12 на 12 и оставила бы перо в верхней позиции:

5, 12 3

5,12

5, 12 3

5,12

Если черепаха передвигается с пером, находящимся в нижней позиции, устанавливайте соответствующие элементы массива floor равными 1. При подаче команды 6 (печать) отображайте звездочкой или каким-либо другим символом все значения 1 в массиве, где бы они ни были. Все нули, где бы они ни были, отобразите пробелами. Напишите программу, реализующую рассмотренные возможности отображения траектории передвижения черепахи. Добавьте другие команды для повышения мощности вашего языка управления траекторией черепахи.

4.24. (Путешествие коня) Одной из наиболее интересных шахматных головоломок является задача о путешествии коня, впервые предложенная математиком Эйлером. Вопрос заключается в следующем: может ли шахматная фигура, называемая конем, обойти все 64 клет-

Рис. 4.25. Восемь возможных ходов конем

ки шахматной доски, побывав на каждой из них только один раз. Рассмотрим эту интересную задачу более подробно.

Конь ходит L-образно (на две клетки в каком-либо направлении и затем на одну клетку в перпендикулярном направлении). Таким образом, из клетки в середине пустой доски конь может сделать восемь разных ходов, (пронумерованных от О до 7) как показано на рис. 4.25.

a) Нарисуйте на листе бумаги шахматную доску 8 на 8 и попытайтесь выполнить путешествие коня вручную. Пометьте цифрой 1 первую клетку, куда вы ходите конем, цифрой 2 вторую, цифрой 3 третью и т.д. Перед началом путешествия определите, на сколько ходов вперед вы будете думать, памятуя о том, что полное путешествие состоит из 64 ходов. Как далеко вы уйдете? Что препятствует вашим планам?

b) Теперь разработайте программу передвижения коня по шахматной доске. Доску представим двумерным массивом board 8 на 8. Каждой клетке дадим нулевое начальное значение. Опишем каждый из восьми возможных ходов в терминах их горизонтальной и вертикальной компонент. Например, ход типа О, как показано на рис. 4.25, содержит перемещ;ение на две клетки горизонтально направо и на одну клетку вертикально вверх. Ход 2 состоит из перемещ;ения на одну клетку горизонтально налево и на две клетки вертикально вверх. Горизонтальные перемещения налево и вертикальные перемещения вверх будем отмечать отрицательными числами. Восемь ходов, которые могли бы быть описаны двумя одномерными массивами, horizontal и vertical, выглядят следующим образом:

0 1 2 3 4 5 6 7

horizontal[0] = 2

horizontal[1] = 1

horizontal[2] = -1

horizontal[3] = -2

horizontal[4] = -2

horizontal[5] = -1

horizontal[6] = 1

horizontal[7] = 2

vertical[0] = -1 vertical[1] = -2 vertical[2] = -2 vertical[3] = -1 vertical[4] = 1 vertical[5] = 2 vertical[6] = 2 vertical[7] = 1

Пусть переменные currentRow и currentColumn указывают строку и столбец текущей позиции коня. Чтобы сделать ход типа moveNum-ber, где moveNumber - число от О до 7, ваша программа использует операторы

currentRow += vertical[moveNumber]; currentColumn +=[moveNumber];

Введите счетчик, который изменяется от 1 до 64. Записывайте последний номер каждой клетки, на которую передвинулся конь. Помните, что для контроля каждого возможного хода конем нужно видеть, был ли уже конь на этой клетке. И, конечно, проверяйте каждый возможный ход, чтобы быть уверенным в том, что конь не вышел за пределы доски. Теперь напишите программу передвижения коня по доске. Запустите программу. Сколько ходов сделал конь?

с) После попытки написать и запустить программу путешествия коня вы, вероятно, получили более глубокие представления о задаче. Вы будете использовать их для создания эвристики (или стратегии) передвижения коня. Эвристика не гарантирует успеха, но при тщательной разработке обычно существенно повышает шансы на успех. Вы можете заметить, что клетки на краях доски более трудны для обхода, чем клетки в центре доски. Наиболее трудны для обхода или даже недоступны четыре угловые клетки.

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

Мы можем разработать эвристику доступности путем классификации каждой клетки в соответствии с ее доступностью (в терминах хода конем, конечно) и перемещения коня на наиболее недоступную клетку. Мы пометим двумерный массив accessibility числами, указывающими, со скольких клеток доступна каждая клетка. На пустой доске каждая центральная клетка оценивается как 8, а каждая