Рис. 2.1.8. Процесс разработки по методу «спсрху-вниз» для блок-схемы на

рис. 2.1.4, б.

-(1, 2) он за один ход может перейти на поля XI, Х2, ХЗ, которые показаны на рис. 2.1.11, а.

Рис. 2.1.9. Выражение функции / как композиции функций g и h.

Рис. 2.1.10. Выражение функции g с использованием конструкции if-then-else,

1 2 3 4 Б 6 7 . 8

Новая позиция

при исходной позиц,ж (I,J)

1 (l-2,J + 1)

2 (l-l,J + 2)

3 (I + 1,J + 2)

4 {I+2,J + 1)

5 (1+2,J-1)

6 (I + I.J-2)

7 (I-I.J-2)

8 n-2,J-l)

Рис. 2.1.11. Возможные ходы коня.

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

Не имея никакой математической теории, которая помогла бы

2 3 4 5 6

Рис. 2.1.12. Произвольный путь коня из поля (5, 6).

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

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

Рассмотрим произвольный маршрут из произвольного поля, например (5, 6) (рис. 2.1.12); целое указывает на Л-е поле, входящее в пройденный путь. Очевидно, что в этом примере после сорок пятого хода на поле (8, 2) конь может пойти только на поле, на котором он уже был, либо сойти с доски. Возможно, более методичный подход позволит получить более длинный маршрут.

Рассмотрим следующую простую стратегию. Начать с произвольного поля. Из заданного поля попытаться пойти сначала на поле 1, как указано на рис. 2.1.11, б (т. е. на два поля вверх и на одно вправо). Если это сделать нельзя, попытаться пойти на поле 2; при неудаче - На поле 3 и т. д. по часовой стрелке. При достижении положения, из которого невозможно пойти ни на одно из перечисленных восьми полей, не сходя с доски или не посещая какое-то поле второй раз, прервать маршрут и зафиксировать (или распечатать) результаты.

Ориентируясь на эту схему, начнем разработку такого алгоритма методом сверху-вниз. Начнем с одного-единственного оператора: