Study & Dev | Blog Archive | Структуры данных и алгоритмы. Теория. Классические задачи программирования

Структуры данных и алгоритмы. Теория. Классические задачи программирования

January 9, 2007

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

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

Рекурсия и переборные задачи

Наиболее часто рекурсию применяют при решении переборных задач. Подобными задачами заполнены многие популярные книжки, они являются неотъемлемой частью практически любой олимпиады по информатике начиная со средней школы и ПТУ не говоря уже о ВУЗах. Мы рассмотрим схему применения рекурсии при решении такого класса задач как задачи с возвратом (backtracking). Давайте конкретно разберем схему применения backtracking при решении задачи с шахматным конем.

Пример: Задана шахматная доска размером N*N. Каждая клетка данной доски пронумерован по порядку от 1 до N^2. Конь перемещается по обычным шахматным правилам. Нам необходимо найти такой способ прохода по всем клеткам при котором мы посетим именно все поля и только один раз. В качестве начальных данных выступают размеры доски и начальная позиция коня (его координаты по обоим осям). Решение должно быть именно рекурсивным.

На приведенном изображении в центре доски находится сам конь. Цифры вокруг него показывают возможные клетки для первого хода. Для того чтобы иметь унифицированный способ вычисления всех клеток, куда можно переместиться из текущей позиции рекомендуется использовать вспомогательный массив размером 2*8. Здесь первая строка для заданного столбца K это приращение по оси OY, соответственно значение второй строки это приращение по оси OX. Пример подобной матрицы приводится ниже (**):

1	2	-1	1	-1	-2	2	-2
2	1	2	-2	-2	1	-1	-1

Перед запуском нашей рекурсивной функции, назовем ее Horse, функция main должна выполнить подготовительную работу – заполнить исходную матрицу нулями – будем считать, что значение каждой клетки отличное от нуля – это номер порядковый хода, который привел в эту позицию, ноль, соответственно будем считать признаком того, что в эту клетку мы еще не пришли. В качестве параметров при вызове функции Horse должны передаваться координаты текущей клетки (I, J), а также номер хода S.

В каждом рекурсивном вызове глубины S делается попытка разместить коня во все возможные клетки, в которые можно напрямую попасть из текущей (I,J) клетки доски для этого к текущей координате (I, J) по очереди добавляются коэффициенты смещения (**). Разумеется, что каждую из получившихся координат необходимо проверять на предмет того, не вышли ли мы за границы шахматной доски. Итак, получив новую координату (I1, J1) мы проверяем, можем ли мы сделать туда ход, т.е. пуста ли данная клетка (т.е. равна нулю). Если такой ход возможен, то мы его делаем, помещая в клетку нашего массива значение A[I1, J1] = S. Сделав такой ход, мы упрощаем оригинальную задачу, теперь нам нужно обойти уже N^2 – S клеток доски. Отдельно стоит отметить существование так называемых «тупиков» - это такие состояния, где мы еще не заполнили всех клеток, но при этом из текущего состояния некуда ходить. То что мы пришли в тупик означает что, где-то на предыдущих стадиях пути мы ошиблись и выбрали неверный путь, следовательно, нам нужно вернуться и повторить с момента ошибки выбрав уже другую клетку. А теперь внимание: именно так и поступает любой рекурсивный алгоритм поиска: на некотором шаге вложенности рекурсии (стадия спуска) когда мы принимаем решение о том какой именно из множества возможных путей выбрать, то сохраняется в стеке локальной памяти функции все значения переменных и параметров, каждая из последующих копий функции будет работать со своими копиями переменных. Поэтому когда мы на стадии подъема откатываемся к предыдущему состоянию то благодаря сохранившимся значениям переменных уже знаем какие именно пути мы прошли а какие остались. В этом работа рекурсивного поиска похожа на то, как ищут туристы ищут в лесу путь домой. Или на то как машина, играющая с человеком в шахматы или иную игру перебирает (ищет, использует эвристические методы) для принятия решения как ходить.

Пример исходного кода алгоритма приводится ниже:

```
#include "stdio.h"
```
```
 
```
```
#include <algorithm>
```
```
using namespace std;
```
```
 
```
```
const N = 6;
```
```
 
```
```
const int arrSteps [2] [8] = {
```
```
	{1,	2,	-1,	1,	-1,	-2,	2,	-2},
```
```
	{2,	1,	2,	-2,	-2,	1,	-1,	-1}
```
```
};
```
```
 
```
```
int arrDesk [N][N];
```
```
 
```

bool horse (int II , int JJ , int level){

```
	if (N*N == level - 1){
```

		printf ("------- Found Solution -----------\n");

```
		for (int i=0; i < N; i++){
```
```
			for (int j=0; j < N; j++)
```
```
				printf ("%3d" , arrDesk[i][j]);
```
```
			printf ("\n");
```
```
		}
```

		printf ("------- End Of Solution -----------\n");

```
		return true;
```
```
	}
```
```
 
```
```
	for (int k=0; k < 8; k++){
```
```
		 int i1 = II + arrSteps [0][k];
```
```
		 int j1 = JJ + arrSteps [1][k];
```

		 if (i1 >= 0 && i1 < N && j1 >= 0 && j1 < N && arrDesk[i1][j1] == 0)

```
		 {
```
```
			arrDesk [i1][j1] = level;
```
```
			horse (i1 , j1 , level + 1);
```
```
			arrDesk [i1][j1] = 0;
```
```
		 }
```
```
 
```
```
	}
```
```
}
```
```
 
```
```
void main (void){
```
```
	for (int i=0; i < N; i++)
```
```
		for (int j=0; j < N; j++)
```
```
			arrDesk [i][j] = 0;
```
```
 
```
```
	arrDesk [0 ][0] = 1;
```
```
	horse (0 , 0 , 2);
```
```
}
```

Замена рекурсии стеком

В том случае когда необходимо реализовать перебор, но при этом необходимо уменьшить накладные расходы на рекурсию, то можно заменить ее с помощью стека. Далее приводится пример кода, в котором решается задача поиска самого большого пятна на шкуре леопарда. В прямоугольной матрице размером N*M заполненной нулями и единицами необходимо найти наибольшую область из сплошных единиц. Далее приводится решение с использованием средств рекурсии и с помощью стека. Замена возможна именно благодаря тому, что технически рекурсия реализуется с помощью запоминания возможных вариантов развития стратегии решения и возврата к ним по дисциплине LIFO. Особо следует отметить, что замена рекурсии с помощью стека должна быть проведена тогда когда рекурсия имеет очень большое значение уровня, в этой ситуации у нас может банально не хватить стековой памяти компьютера, а благодаря тому, что стек мы можем разместить в динамической памяти, то ограничения на его размер менее чувствительны.

```
#include "stdio.h"
```
```
#include "stdlib.h"
```
```
 
```
```
const N = 10;
```
```
const M = 10;
```
```
/*
```

 Задача со шкурой леопарда

 необходимо в матрице заполнненной нулями и единицами

 надо посчитать площать самого большого пятна из единичек

```
 
```

 демонстрируется как рекурсивное так и нерекурсивное решение с помощью стека

```
*/
```
```
 
```
```
int globCounter ;
```

 // рекурсивное решение

int recursive_calc (int ii , int jj , int * arrSkin){

	if (ii < 0 || ii >= N || jj < 0 || jj>=M) return 0;

```
	int elt = arrSkin [ii*N + jj];
```
```
	if (elt == 1){
```
```
		arrSkin [ii*N + jj]  = globCounter;
```

		int top = recursive_calc (ii - 1 , jj , arrSkin);

		int bottom = recursive_calc (ii + 1 , jj , arrSkin);

		int left = recursive_calc (ii  , jj-1 , arrSkin);

		int right = recursive_calc (ii  , jj+1 , arrSkin);

		return  1 + top + bottom + left + right;

```
	}
```
```
	return 0;
```
```
}
```
```
 
```
```
void main (void){
```
```
	int arrSkin [N][M];
```
```
	int i , j;
```
```
	for (i=0; i < N; i++)
```
```
		for (j = 0; j < M; j++)
```
```
			arrSkin[i][j] = rand () % 2;
```
```
 
```

	printf ("--------- Before ------------\n");

```
	for (i=0; i < N; i++){
```
```
		for (j = 0; j < M; j++)
```
```
			printf ("%1d" , arrSkin [i][j]);
```
```
		printf ("\n");
```
```
	}
```
```
 
```
```
	int maxZone = -1;
```
```
	globCounter = 2;
```
```
	int colorZone = -1;
```
```
 
```
```
	for (i=0; i < N; i++){
```
```
		for (j = 0; j < M; j++)
```
```
			if (arrSkin[i][j] == 1){
```

				int candi_maxZone = recursive_calc (i , j  , &arrSkin[0][0]);

```
				if (candi_maxZone > maxZone ){
```
```
					maxZone = candi_maxZone; 
```
```
					colorZone = globCounter;
```
```
				}
```
```
				globCounter++;
```
```
			}
```
```
	}
```
```
 
```

	printf ("MaxZone Size Is %d And Color Is %d \n" , maxZone , colorZone);

```
 
```

	printf ("--------- After  ------------\n");

```
	for (i=0; i < N; i++){
```
```
		for (j = 0; j < M; j++)
```
```
			printf ("%3d" , arrSkin [i][j]);
```
```
		printf ("\n");
```
```
	}
```
```
 
```
```
}
```

Для нерекурсивного решения необходимо подключить класс stack из библиотеки stl. Далее приводится пример функции нерекурсивного решения. Для того чтобы проверить ее работу следует заменить в вышеприведенном листинге вызов функции “recursive_calc” на “ stack_calc”.

int stack_calc (int ii , int jj , int * arrSkin){

```
	typedef pair <int , int > PINT;
```
```
 
```
```
	stack <PINT> st;
```
```
	st.push (PINT(ii , jj));
```
```
	int countSpots = 0;
```
```
 
```
```
	while (!st.empty()){
```
```
		PINT p = st.top ();
```
```
		st.pop ();
```
```
		ii = p.first;
```
```
		jj = p.second; 
```
```
 
```

		if (ii < 0 || ii >= N || jj < 0 || jj>=M) continue;

```
 
```
```
		int elt = arrSkin [ii*N + jj];
```
```
		if (elt == 1){
```
```
			countSpots++;
```
```
			arrSkin [ii*N + jj]  = globCounter;
```
```
			st.push  ( PINT(ii - 1 , jj ));
```
```
			st.push ( PINT(ii + 1 , jj ));
```
```
			st.push ( PINT(ii  , jj - 1 ));
```
```
			st.push ( PINT(ii  , jj + 1 ));
```
```
		}
```
```
	}
```
```
	return countSpots;
```
```
}
```

Задачи

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

Задания: далее приводится список задач предполагающих решение с использование рекурсии и методов backtracking для поиска решения.

1) Задача о восьми ферзях: на шахматной доске необходимо расположить восемь ферзей, так чтобы ни один из них не находился под боем другого.

2) Во время поездки на поезде девочка заменила в названии поезда каждую букву ее номером в русском алфавите и получила запись из единиц и двоек "211221-21221". Определить откуда и куда идет поезд?

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

4) В написанном выражении ((((1?2)?3)?4)?5)?6 вместо каждого знака ? вставить знак одной из 4 арифметических операций +,-,*,/ так, чтобы результат вычислений равнялся 35 (при делении дробная часть в частном отбрасывается). Найти все решения.

5) Вводится строка не более чем из 6 цифр и некоторое целое число R. Расставить знаки арифметических операций ("+", "-", "*", "/"; минус не является унарным, т.е. не может обозначать отрицательность числа; деление есть деление нацело, т.е. 11/3=3) и открывающие и закрывающие круглые скобки так, чтобы получить в результате вычисления получившегося выражения число R. Лишние круглые скобки ошибкой не являются.

 <strong>Например:</strong> Строка 505597, R=120: ((5+0)*((5*5)-(9/7)))=120.

6) Составить программу, которая печатает все различные представление числа N в виде всевозможных произведений (сумм) K натуральных чисел (N, K-вводятся, 1

Categories: Структуры данных и алгоритмы

Study & DevО программировании и не только

Структуры данных и алгоритмы. Теория. Классические задачи программирования

Замена рекурсии стеком

Задачи

Поиск

Недавнее

Архив

Разделы