Итак приступим. На текущий момент нам необходимо знать и понимать что такое стек и какой базовый набор операций он поддерживает. О стеке я впервые узнал из этой книги 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 Мб.
Комментариев нет:
Отправить комментарий