суббота, 26 декабря 2009 г.

Train 1.1. (12Dec2009) – Стек (Поиск в глубину)

Итак приступим. На текущий момент нам необходимо знать и понимать что такое стек и какой базовый набор операций он поддерживает. О стеке я впервые узнал из этой книги 2004 года издания.  Сейчас мы не будем разбирать внутреннюю реализацию стека, а воспользуемся готовой STL-вской. Здесь можно получить всю справочную информацию по этому вопросу.

Задача  Скобки
Глоссарий:
Стек: stack<char> s
Вершина стека: s.top()
Открывающая скобка: ‘(’, ‘{’, ‘[’
Закрывающая скобка:  ‘)’, ‘}’, ‘]’ 
Парные скобки: интуитивно понятно


Основная идея:
Последовательно перебираем символы в строке и действуем по следующему принципу:
1. Если текущий символ  открывающаяся скобка, добавляем ее в стек.
2. Если текущий символ закрывающая скобка, смотрим на символ, находящийся в вершине стека. Если в вершине стека находится открывающая скобка, парная текущей, тогда выталкиваем ее из стека.
Положительный ответ:
1. После всех итераций со скобками имеем пустой стек.
Отрицательный ответ:
1.  Текущий символ закрывающаяся скобка и стек пуст
2. Текущий символ – закрывающая скобка, вершина стека не является парной для текущей.
3. После всех итераций со скобками стек не пуст.

Исходный код: Здесь

Задача “Разрезание листа”(Поиск в глубину)

Основная идея:
1. Заполняем исходную матрицу единицами
2. Вырезанные клетки помечаем ноликами.
3. Последовательно перебираем все клетки матрицы. Если текущая клетка равна 1, то запускаем из нее поиск в глубину (DFS), последовательно перебирая все клетки достижимые из текущей. В процессе обхода помечаем пройденные клетки ноликами.
4. Количество запусков DFS и будет ответом.

Исходный код: Здесь

Комментарий: Если попытаться запустить тест на максимальных размерностях в режиме Debug, то получим Stack overflow. Это связано с тем, что размер системного стека, отводящийся под рекурсию равен 1 или 2 МБ, а наша реализация потребовала больше. В режиме Release все будет работать, потому что в нем не хранятся данные для отладки. Поэтому для отладки максимального теста нужно явно увеличить размер системного стека. Это можно сделать с помощью следующей команды:

#pragma comment (linker, "/STACK:64000000")

При этом размер  системного стека будет равен ~ 64 Мб.

Комментариев нет:

Отправить комментарий