Информатика и технология программирования


Обход шахматной доски


В качестве примера рассмотрим проектирование функции для поиска последовательности обхода конем шахматной доски.

Шаг 1. Алгоритм обхода можно разбить на последовательность шагов. Каждый шаг характеризуется начальным состоянием - текущим положением коня. Алгоритм на каждом шаге предполагает проверку возможности сделать ход в каждом из 8 допустимых направлений. Схема алгоритма имеет вид:


void step(int x0, int y0)
{ // формальные параметры -


// текущая позиция коня


// приращения координат для 8 ходов


static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода


if (x &#60 0 || x &#62=7 || y &#60 0 || y &#62=7 )
return; // выход за пределы доски


for (i=0; i&#60 8; i++)
step(x0+xy[i][0], y0+xy[i][1]);
// выполнить следующий ход


}

Шаг 2. Предыдущий шаг дает полный перебор возможных последовательностей ходов коня. Функция имеет результат void, то есть является безусловной. Далее необходимо определить, как производить выбор необходимой последовательности. Очевидно, функция должна давать логический результат - 0, если при выполнении очередного хода в данном направлении задача не решается и 1, если решается успешно. При этом цикл, в котором происходит рекурсивный вызов - просмотр очередных ходов, выполняется до первого успешного вызова:


int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода


if (x &#60 0 || x &#62=7 || y &#60 0 || y &#62=7 )
return(0); // выход за пределы доски


for (i=0; i&#60 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода


return(0); // последовательность не найдена


}

Шаг 3. Далее необходимо определить условия начала и завершения рекурсивного процесса, а также условия взаимодействия шагов между собой. Условием завершения процесса является обход всех 64 полей доски. При этом не должно производиться повторное попадание на то же самое поле.


Начало  Назад  Вперед



Книжный магазин