создать возможный тур коня (рис. 2.1ЛЗ, а). Это должно включать построение пути и затем распечатку результата (рис. 2.1.13, б). Построение пути сводится к выбору начальной позиции (рис. 2.1.13, е) и затем построению маршрута из этой позиции.

Здесь у нас есть достаточно хороший способ выбора начальной позиции, например считывая два целых числа (/, J), принимающих значения от 1 до 8. Мы также видим, что распечатка результатов предполагает распечатку целых значений, которые хранятся в соответствующем шахматной доске массиве (BOARD (/, J)). Поэтому теперь нам нужно сосредоточиться на том, как построить путь, начинающийся в поле (/, /).

Из того факта, что целые числа хранятся в массиве BOARD (/, J), следует необходимость присвоить всем элементам массива начальные значения, равные О (р.чс. 2.1.13, г). Таким образом, ход на поле {J, J) возможен при BOARD (/, 7)=0. Далее, выход за пределы доски можно обнаружить, проверив принадлежность значений / и J отрезку значений целых чисел [I, 8].

Выход за пределы доски можно обнаружить также и по другой схеме (рис. 2.1.14). Добавим по два дополнительных ряда полей к каждому краю массива BOARD и занесем в каждое новое поле некоторое начальное значение, например 99. Тогда попытка выйти за пределы доски обнаруживается по ненулевому значению рассматриваемого поля.

Закончив с присваиванием начальных значений массиву BOARD, вернемся опять к задаче построения тура из произвольного поля (/, J). Мы должны попытаться разбить этот этап на последовательность меньших этапов, сводящихся к операторам if-then-e!se, do-vhi!e или while-do.

Здесь мы начинаем ощущать, что нам не обойтись без основного цикла, в котором некоторый индекс, скажем К, пробегает множество всех возможных полей, на которые можно пойти с поля (/, J). Движение коня приостанавливается, когда /(>8. Из этого следует разбиение обсуждаемого этапа, представленное на рис. 2.1.15, а.

При попытке пойти на новое поле из поля (/, J) может произойти одно из двух: либо ход возможен, и тогда мы заменяем значение (/, J) на новое, присваивая К значение 1, либо ход невозможен, и тогда значение К увеличивается на 1 (рис. 2.1.15, б).

Остается еще определить значение К для поля (/, J). Для этой цели создается специальная таблица (рис. 2.1.16), в которой указываются модификации значений / и / для определения поля К- Теперь мы можем завершить построение нашей окончательной структурированной блок-схемы, которая приведена на рис. 2.1.17.

Реализация этого алгоритма на Фортране приведена на следующем рисунке (рис. 2.1.18). В качестве упражнения напишите и пропустите на машине программу для этого алгоритма и проверьте, можею ли

СозЗоть Возможный турконя

Выфать нача/гьте

Расгсчтать peay-ibmamb/

Построить путь из nom{l,J)

Построить пс/Шь

Распечатать результаты

Вбфать начальное noeiJ.J)

Рис. 2.1.113. Разработка алгоритма возможного тура копя методом сверху-вниз.

Рис. 2.1.14. ПервоначЕльная конфигурация на доске.

Попытаться пойти m/<-oem/reu3{r,J); получить ноВое значение К

Рис. 2.1.15. Продолжение разработки алгоритма «тур коня» методом сверху-вниз.

К Х-перемещате J-nepeHemeime-

1 2 3 4 5 6 7 8

-2 -1 +1 +2 +2 +1 -1 -2

+1 +2 +2 .+1 -1 -2 -2 -1

Рис. 2.1.16. Таблица модификации значений / и / для хода на новое поле /С.