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

Реализация рекурсии

Программный стек

Многие компиляторы языков программирования (в частности компиляторы Си и Си++) используют так называемый программный стек для размещения аргументов под­про­грамм (функций) и локальных переменных. Программный стек – некоторая область памяти, используемая программой для размещения своих объектов. Рас­смот­рим в качес­тве примера следующую программу, состоящую из трех функций – main, f1, f2.

void main(void){

char x,y;

int z;

// 1

x=f1(x,z); // 3

………………………………………………

z=f2(z); // 7

}

//---------------------

char f1(char t, int u){

float q;

// 2,5

…………………………………………………

}

//---------------------

int f2(int k){

char p=7;

// 4

p=f1(1,2); // 6

………………………………………………………

}

В процессе работы, программа проходит ряд точек, отмеченных в программе комментариями:

· 1 – после входа в функцию main

· 2 – после входа из main в f1

· 3 –после выхода из f1 в main

· 4 –после входа в f2 в main

· 5 – после входа в f1 из f2

· 6 – после выхода из f1 в функции f2

· 7 – после выхода из f2 в функции main

При входе в функцию программа помещает в программный стек значения аргументов в байты памяти, отводимой для параметров и локальных перемен­ных, после чего вершина стека поднимается (Push). При выходе из функции, вершина стека опускается до уровня, предшествующего входу (Pop). В таблице 1 изображено состояние стека в различных точках программы. По горизонтали – адреса байтов программного стека, по вертикали – номера точек.

Таблица 1. Состояние стека в процессе выполнения программы

Примечания:

- здесь не учитывается выравнивание адресов на границу слова, двойного слова,

- длина типа int – 4 байта,

- не учитывается что адрес точки возврата при обращении к функции тоже помещается в стек.

Использование механизма программного стека для распре­де­ле­ния памяти для параметров и локальных переменных (класс памяти automatic) приводит к тому, что никаких дополнительных усилий для реализации рекурсии уже не требуется. Каждое новое обращение к рекурсивной функции помещает в стек новое поколение параметров и локальных переменных.

Некоторые языки программирования не допускают исполь­зо­вания рекурсивных функций, то есть таких функций, которые обращаются сами к себе прямо или косвенно через другие функции. Используя стек, который функция должна обслуживать сама, программист, тем не менее, может реализовать рекурсивные алгорит­мы. Типичными задачами, решаемыми с помощью рекурсии, являются задачи перебора с возвратами (Back Track), а также алгоритмы, в которых часть работы выполняется как вся работа. В качестве примеров рассмотрим две задачи: обход шахматной доски ходом коня и вычисление определенного интеграла.

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

struct STACK{

int i,j; // координаты клетки

int move; // номер хода, которым покидаем клетку

}; // элемент стека

bool Horse(int n, STACK *stack);

//-----------------------------------

static bool Move(int N, int i1,int j1, int n, int *i2, int *j2){

// Ход коня. Конь ходит из клетки i1,j1 ходом номер n

// и попадает в клетку *i2,*j2

// N - размер доски

// Возвращает true при успехе

switch(n){

case 0:

*i2=i1+1;

*j2=j1+2;

break;

case 1:

*i2=i1+2;

*j2=j1+1;

break;

case 2:

*i2=i1+2;

*j2=j1-1;

break;

case 3:

*i2=i1+1;

*j2=j1-2;

break;

case 4:

*i2=i1-1;

*j2=j1-2;

break;

case 5:

*i2=i1-2;

*j2=j1-1;

break;

case 6:

*i2=i1-2;

*j2=j1+1;

break;

case 7:

*i2=i1-1;

*j2=j1+2;

break;

default:

// сюда можно попасть только при ошибке в программе

*i2=INT_MAX;

*j2=INT_MAX;

}

return (*i2>=0 && *i2<N && *j2>=0 && *j2<N);

}

//-----------------------------------

bool Horse(int n, STACK *stack){

// n - размер доски.

// результат будет получен в стеке stack.

// Каждый раз, когда покидаем клетку, ее координаты

// и номер хода помещаем в стек.

// возврат true - успех

bool **Board=NULL; // в массиве доска n*n помечаем факт посещения клетки

int i,j; // текущие координаты клетки

int v; // указатель стека

int BegMove,k,i2,j2;

bool out=true,Good;

// выделим память для доски

Board=new bool * [n];

for(i=0;i<n;i++){

Board[i]=new bool[n];

}

// Board[i][j]==true означает, что клетка посещалась

// Ни одна клетка еще не посещалась

for(i=0;i<n;i++){

for(j=0;j<n;j++){

Board[i][j]=false;

}

}

v=-1; // стек пуст

i=0;j=0; // начальная клетка

BegMove=0; // Номер хода, с которого начинается перебор

M:

// ищем допустимый ход из текущей клетки

Good=false; // предикат "Ход найден"

for(k=BegMove;k<8;k++){

if(Move(n,i,j,k,&i2,&j2) && !Board[i2][j2]){

Good=true;

break;

}

}

if(Good){

// текущую клетку и номер хода помещаем в стек

v++; stack[v].i=i; stack[v].j=j; stack[v].move=k;

// пометить клетку, как посещенную

Board[i][j]=true;

BegMove=0;

i=i2; j=j2;

// может обошли все ?

if(v==n*n-2){

// последнюю клетку - в стек

v++; stack[v].i=i2; stack[v].j=j2;

goto finish;

}

goto M; // все повторить для очередной клетки

} else { // ход не найден

// взять из стека, если он не пуст

if(v<0){ // стек пуст - задача не имеет решения

out=false;

goto finish;

}

// взять из стека

i=stack[v].i; j=stack[v].j; BegMove=stack[v].move+1; v--;

Board[i][j]=false;

goto M;

}

finish:

// освободим память

for(i=0;i<n;i++){

delete [] Board[i];

}

delete [] Board;

return out;

}

Общая схема решения задачи перебора с возвратами

В общем случае схема решения задачи перебора с возвратами имеет вид:

bool BackTrack(параметры){

// опустошить стек

// задать начальные значения переменным

bool Good=false; // Good – решение найдено

M:

bool Find=Найти следующий допустимый узел в дереве решений();

if(Find){

// данные узла поместить в стек

if(пройдены все пути в дереве){

Good=true;

// решение находится в стеке

goto finish;

}

goto M; // повторить процесс исходя

// из нового узла дерева решений

} else { // новый узел не найден

// взять из стека предыдущий узел, если стек не пуст

if(v<0){ // стек пуст - задача не имеет решения

Good=false;

goto finish;

}

// взять из стека данные предшествующего узла

// и сделать его текущим

goto M;

}

finish:

// приберём за собой (освободим память, закроем файлы…)

return Good;

}