22. Работа с файлами: представление файлов, наборы функций для работы с файлами
23. Рекурсивные алгоритмы. Понятие рекурсии, возможности и эффективность, решаемые классы задач
Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.
Рекурсия и эффективность алгоритмов. Рекурсивное программирование дает нам общий подход к решению задач – разбиению их на аналогичные подзадачи меньшей размерности, либо на задачи, представляющие собой шаги в возможных направлениях ее решения. Так или иначе, рекурсивные вызовы образуют древовидную структуру, количество вершин в которой определяет эффективность алгоритма (выражаемую обычно через трудоемкость). Разница между различными типами алгоритмов состоит в способе получения подзадач, их размерности, способе соединения полученных результатов.
· рекурсивное или обычное разделение. Идея разделения восходит к технологическому приему - модульному программированию (3.6). В своем первоначальном варианте она предполагает разбиение на задачи различной природы. Нерекурсивное разделение позволяет достичь определенного эффекта за счет разбиения задачи на множество идентичных задач меньшей размерности с последующим объединением результата. Типичным примером здесь является сортировка однократным слиянием (4.6). Применение того же самого алгоритма рекурсивно к полученным подзадачам дает следующий класс алгоритмов – рекурсивное разделение. Как правило, независимость полученных подзадач подразумевает соответствующее разделение исходных данных задачи на непересекающиеся подмножества – этому и соответствует сам термин разделение. Эффективность (и трудоемкость) таких алгоритмов, зависит от затрат на само разделение и от пропорций разделяемых частей: лучшему случаю соответствует деление на равные части (логарифмические зависимость), худшему – выделение единственного элемента (линейные зависимости).
· жадные алгоритмы. Идеальным случаем можно считать алгоритм, способный «выбрать из нескольких зол» единственно правильное. В основе его так же лежит принцип разделения, но в каждой точке он имеет основание выбрать одну из подзадач.Обычно это делается на основании особенностей организации обрабатываемых данных или их избыточности. Типичный пример: двоичный поиск в упорядоченных данных (4.6). Основой жадных алгоритмов является всегда довольно спорное утверждение: движение «по линии наименьшего сопротивления» в каждой точке приведет к желаемому результату.
· полный перебор (исчерпывающий, комбинаторный перебор). Перечисленные выше подходы основаны на всевозможных «ухищрениях», основанных на особенностях предметной области алгоритма. Если же ничего не помогает, то остается полный перебор всех возможных вариантов решения задачи (8.4).
· динамическое программирование. В процессе порождения дерева рекурсивных вызовов возможно повторение подзадач с одними и теми же данными. Если запоминать результат их выполнения, то эффективность алгоритма может быть значительно увеличена.
Основные принципы рекурсивного решения:
· рекурсивная функция решает задачу для двух оставшихся частей строк с длинами k1 и k2, возвращая в виде результата максимальную длину найденной подпоследовательности;
· шаг рекурсии заключается в проверке пары очередных символов и получении аналогичных подзадач меньшей размерности за счет отбрасывания этих символов;
· если пара очередных символов совпадает, то они оба отбрасываются, а длина подпоследовательности увеличивается на 1. При этом производится рекурсивный вызов с сокращением длин обеих строк v=F(k1-1,k2-1)+1;
· если пара очередных символов не совпадает, то возникают две подзадачи, в которых одна строка укорачивается, а другая остается неизменной. Из результатов двух рекурсивных вызовов выбирается максимальный и возвращается в неизменном виде, т.к. текущий шаг не удлиняет цепочку совпадений;
· рекурсивный алгоритм завершается, когда заканчивается хотя бы одна строка, в этом случае функция возвращает 0 совпадений.
