|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Думаю, настало самое подходящее время для того, чтобы рассказать об особенностях использования вложенных рекурсий в программировании. Наверное, в реальных условиях это знание никогда тебе не понадобится, но для школьников и студентов, принимающих участие в олимпиадах по программированию, это может быть очень полезным. Конечно, я не являюсь членом команды ЛИТМО по программированию, но все-таки...
Объяснять, что такое рекурсия не буду, да и не нужно, т.к. каждый второй четко знает, что это такое, а каждый первый хотя бы раз слышал о ней. Самым важным является то, что среды программирования, в которых официально разрешено работать - QBasic 4.5, Turbo (или Borland) Pascal for DOS, Turbo C for DOS. А, это накладывает определенную специфику на реализацию рекурсии.
Самым важным является то, что при реккурентном вызове функции все передаваемые параметры складываются в стек, размер которого всего-навсего 64Кб. Т.е. если надо передать маску 8x8 значений 0/1, то зачем передавать массив размером 64 байта, если можно закинуть туда массив из 4 unsigned int, что будет занимать 8 байт. Значит, так мы можем увеличить глубину перебора. В принципе, можно организовать стек с параметрами самостоятельно, только это будет уже немного не рекурсия.
При переборе всегда возникают проблемы с нехваткой быстродействия, а тестовые машины, как правило, имеют процессор с тактовой частотой не больше 600МГц. Вернее, тут основная проблема с отсутствием терпения у жюри олимпиады. Но время всегда можно сэкономить, нужно только явно представлять, что от тебя требуется. Например, если на квадрате 8x8 требуется выделить четырехсвязную область (т.е. соседними элементами считаются элементы, соприкасающиеся по вертикали или горизонтали, причем соседний элемент соседнего элемента принадлежит области), состоящую из одинаковых чисел, то глупо "разрастаться" рекурсией от каждой ячейки, ведь, если такие области существуют, то работа по определению области будет повторена с тем же результатом столько раз, сколько ячеек в данной области. Нужно ввести ту самую битовую матрицу, о которой я говорил раньше, и отмечать единичкой там не только уже посещенные, но и запрещенные клетки. После того, как область была успешно определена, эту матрицу не нужно никуда девать, просто при работе над следующей клеткой (откуда мы будем отталкиваться в поиске области) в качестве начального параметра нужно передать не пустую (как в превый раз) матрицу, а матрицу, построенную для предыдущей клетки. Таким образом, вполне реально выиграть во времени, не проигрывая в памяти.
Следующий немаловажный трюк заключается в комбинировании глубины перебора. Предположим, что мы должны уничтожить самую большую четырехсвязную область, а затем сдвинуть все, что осталось влево и вниз так, чтобы между клетками с числами не осталось пустых мест. Если задача - убрать как можно большее количество чисел с поля, то полный перебор всех вариантов может затянуться во времени. А если рекурсия построена неправильно, то и вовсе зациклиться. Здесь помогут оценки, т.е. можно реализовать метод ветвей и границ. Правда, этот метод придется немного переработать, т.е. указывать не верхнюю и нижнюю оценки, а оценки "в идеале" и "точно есть". Если значение "в идеале" какой-то ветви ниже значения "точно есть" другой ветви, то первую ветвь можно "закрывать", т.к. она бесперспективна. Если же для одной ветви эти два значения совпадают (а так обязательно должно быть на вершине, но можт случиться и в середине процесса), то вычисления по этой ветви также останавливаем, но полученный для этой ветви результат запоминаем. В противном случае, вычисления придется проводить до самих вершин дерева. Далее нужно выбрать максимальную из таких оценок, она и будет искомым значением. Например, для нашей задачи оценкой "в идеале" будет количество чисел в самом начале (т.е. 64), а за "точно есть" можно принять то, что мы получим, убирая первые попавшиеся области.
И, наконец, самое главное: как правильно скомбинировать рекуррентное выделение области с реккурентным поиском наиболее эффективной области? Тут ничего сложного нет. Для каждой рекурсии нужно сначала оптимизировать использование памяти и время перебора, а затем для вкладываемой рекурсии создать функцию вызова (т.е. функцию, которая вызывет функцию, вызывающую себя). Также неплохо было бы применить уже описанные методы оценки перспективности ветвей. Примеры, фрагменты кода и т.д. я здесь не публикую, т.к. для каждой задачи они будут уникальными, как и сами рекуррентные функции. Самое главное - практика. Чем больше ты напишешь таких программ, чем больше подобных задач ты решишь, тем больше шансов, что ты правильно используешь выделенное тебе время и добьешься успехов.
Удачи.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
