Рекурсия

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

А сейчас предлагаю разобрать задачи, предложенные в этой теме господином Долинским.

Малая автоматизация тестирования

Очень важный момент описан Михаилом Долинским, касающийся автоматизации тестирования задач. На мой взгляд это незаменимый инструмент для опытных команд, которые сдают весь контест на +ноль. Жаль, что в свое время наша команда его не использовала.

Суть идеи заключается в создании двух батников, которые должны находится в той же директории, что и *.exe файл откомпилированной программы: test.bat (для проверки одного теста) и all.bat (для проверки всех тестов). Помимо батников нужно заготовить набор локальных тестов, корректность которых не вызывает сомнений.  Эти тесты должны находится все в той же директории.

Я проверил метод на задаче "Путешествие шахматного коня". Заготовил три теста. Тест представляет собой пару файлов x.in и x.out, где x – это порядковый номер теста.

Train 1.2 (19Dec2009) – Очередь(Поиск в ширину)

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

Одним из самых ярких применений очереди можно пронаблюдать на примере алгоритма Поиска в ширину (BFS).

Задача "Путешествие шахматного коня" (Поиск в ширину)
Технические моменты:
Для того, чтобы было удобно перебирать все соседние клетки, достижимые из текущей, шагом коня, предлагаю воспользоваться массивом движений:

1. int moveX[8] = {-2,-2,-1,-1,1,1,2,2};
2. int moveY[8] = {-1,1,-2,2,-2,2,-1,1};

Основная идея:
Рассмотрим работу поиска в ширину пошагово на основе тестового примера (A5 C2). Для более удобного представления шахматной доски в виде матрицы будет считать буквенную часть координаты номером строки, а числовую – номером столбца.

Увеличение размера системного стека

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

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

В данном примере под системный стек будет выделено 64000000/1024/1024 Мб = 61.035 Мб

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

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

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

Основная идея:
Последовательно перебираем символы в строке и действуем по следующему принципу:

Русские буквы на dl.gsu.by

Для решения задач использую Visual Studio 2005, компилятор C++ 9.0. Во время решения столкнулся с проблемой вывода русских букв. Первый раз это произошло в задаче “О скобках”, где нужно было вывести “Да” или “Нет” в качестве ответа.
Проблема заключается в том, что для проверяющей системы выходные файлы должны быть в кодировке CP886(DOS). Из проблемы вышел таким образом

1. ...
2. using namespace std;
3. ...
4. void output(bool value)
5. {
6.     locale rus("rus_rus.866");
7.     wcout.imbue(rus);
8.     if (value)
9.         wcout<<L"Да";
10.     else
11.         wcout<<L"Нет";
12.     exit(0);
13. }
14.  

Долинский TRAINS (part 1)

Technorati Теги: Долинский,Список тренировок

В ближайшее время мы разберем темы представленные в вводном курсе по олимпиадному программированию от Михаила Долинского. (Книга).

Список справочных материалов:

Русские буквы на dl.gsu.by
Увеличение размера системного стека
Малая автоматизация тестирования


Список тренировок:

Train 1.1. (12Dec2009) – Стек (Поиск в глубину)
Train 1.2 (19Dec2009) – Очередь(Поиск в ширину)

Введение

Итак, сегодня 27 сентября 2009 года. Сегодня я создал свой первый блог. Не знаю какая ему заготовлена судьба. Время покажет.

На начальном этапе обычно встает вопрос: "О чем писать?". Передо мной такой вопрос не стоял. Если писать, то только о том, что знаешь лучше всего, либо о том, чем занимаешься дольше всего. Как правило, эти понятия совпадают.

С первого курса я участвовал в олимпиадах по спортивному программированию. Это очень увлекательное занятие.