Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования (Понятие алгоритма, итерационного, рекурсивного алгоритмов).pdf

Введение

Тема данной курсовой работы «Рекурсивные и итерационные алгоритмы: особенности и примеры использования» выбрана не случайно. По моему убеждению, для успешного освоения навыков программирования необходимы глубокие знания базы, на которой строятся практически все популярные в наши дни языки программирования. В частности, так называемые объектно-ориентированные языки программирования, например, C и C++, JavaScript, Python, по сути, имеют схожую структуру, и для освоения базовых навыков можно использовать основные структуры алгоритмов, в том числе и группу рассматриваемых в этой работе.

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

В главе 1 рассмотрим основные понятия – что такое алгоритм, итерация и рекурсия, вспомним, что такое базовые структуры алгоритмов. Более детальное внимание структурам итерационных и рекурсивных алгоритмов уделяется в главах 2 и 4 соответственно, а об их использовании поговорим в главах 3 и 5 соответственно. В главе 6 уделим внимание практической необходимости использования алгоритмов сортировки и поиска, основанных на рассматриваемых базовых структурах.

Основными учебными материалами, использованными при написании данной работы, являются учебные пособия В. А. Голикова «Теория программирования»[1] и Е. А. Роганова «Основы информатики и программирования»[2], а также небезызвестные учебники Томаса Х. Кормена «Алгоритмы: вводный курс»[3] и в меньшей степени его труд вместе с соавторами «Алгоритмы: построение и анализ»[4], а также книга Джона Маккормика «Девять алгоритмов, изменивших мир»[5] (John McCormick’s “Nine Algorithms That Changed the Future”), А. Левитина «Алгоритмы: введение в разработку и анализ» [6]. Все перечисленные пособия являются проверенным инструментом в обучении программированию и имеют под собой глубокую теоретическую базу. Также использовался международный ресурс онлайн-обучения программированию codecademy.com [7], где имеются не только теоретические справки и задания, но и возможность редактировать и выполнять программный код.

Глава 1. Понятие алгоритма, итерационного, рекурсивного алгоритмов

Алгоритм – это последовательность действий (команд, инструкций), заданный исполнителю. Этим исполнителем может быть и сам задающий. Алгоритмом в том числе является и компьютерная программа – по сути, это алгоритм, заданный компьютеру на специальном языке – языке программирования. Компьютерные алгоритмы, в отличие от «человеческих» не могут толковаться неоднозначно. В результате выполнения алгоритма для компьютера должна решаться поставленная ему задача. Это означает, что главное в алгоритме – именно результат его работы, который может быть достигнут различными способами. Также требуется максимально точное описание каждой команды, так как неоднозначная трактовка компьютером инструкции недопустима. При этом совершенно очевидно, что необходимо эффективно использовать ресурсы компьютера . Помимо учета технических характеристик компьютера, который будет исполнять алгоритм, важным показателем является время работы алгоритма. Алгоритм, который дает правильное решение, но требует большого времени для его получения, не имеет практической ценности [3]. Именно для оптимизации структуры алгоритма существуют так называемые базовые структуры.

Рассмотрим такое понятие, как структурный подход к построению алгоритма: он предполагает использование только нескольких основных структур, комбинация которых дает все многообразие алгоритмов и программ [1]. Базовых структур имеется ограниченное количество, и все они в различных сочетаниях способны описать любой алгоритм.

В данной работе будут подробно разобраны итерационные и рекурсивные структуры.

Понятие итерация происходит от латинского iteratio – повторяю. Вспомним, что такое цикл – это базовая структура, в которой некоторая часть программы, выполняемая многократно, после проверки некоторого условия в какой-то момент осуществляется выход из нее [1]. Эта часть программы называется телом цикла, а единичное выполнение тела цикла – итерацией. Итерационным циклом при этом считается такой цикл, где количество повторений заранее неизвестно [1]. Если же требуемое количество повторений действия уже известно, используется счетчик цикла – переменная, связанная с номером итерации.

Важно отметить, что рекурсия (в программировании так называют такой способ организации обработки данных, при котором программа вызывает сама себя непосредственно либо с помощью других программ [2]) в случае итерационного цикла недопустима, многократное повторение действий происходит без обращений программы к части самой себя.

В следующей главе будет более подробно рассмотрена структура итерационных алгоритмов.

Глава 2. Структура итерационного алгоритма

Итерационные алгоритмы применяются в тех случаях, когда некоторое действие требуется повторить несколько раз. Очевидно, что просто последовательное выполнение команд будет неэффективно как с точки зрения удобства, так и рациональности использования ресурсов компьютера[2, 3, 4]. Тем более это необходимо, когда количество повторений действия заранее не определено. Поэтому вводится специальное условие (обычно это логическое выражение): при истинности будет происходить итерация цикла, а при ложности – выход из цикла.

На рисунке 1 базовые структуры алгоритмов приведены в виде блок-схем. Под буквой б видим так называемый цикл «До» - он же цикл с постусловием, в JavaScript используется оператор do…while[7]. Буквой в отмечен цикл «Пока» - соответственно, цикл с предусловием, или же “While” Loop [7]. Существуют и циклы без условия (они являются бесконечными, и для выхода из них требуется специальная команда прерывания или выхода [2], в рамках данной работы они рассматриваться не будут).

Рис. 1: Основные структуры алгоритмов (Источник: [1])

Цикл «До» используется тогда, когда требуется выполнить действие хотя бы 1 раз. Сначала выполняется команда, а затем проверяется условие итерации. Если условие не соблюдается, мы получаем результат первой команды, но не входим в цикл. Иначе цикл будет выполняться до ложности условия итерации.

Итак, приведем пример записи цикла с постусловием на языке JavaScript с помощью оператора «Do… While”.

Рис. 2: Использование оператора do…while для записи цикла с постусловием

Здесь в строке 1 задается переменная, содержащая значение условия выхода из цикла. Сразу присваиваем ей значение false – «ложно». Оператор do содержит тело цикла, а оператор while выполняет проверку истинности условия. Видим, что так как изначально условию присвоено ложное значение, тело цикла выполнится, и сразу произойдет выход из цикла. В ходе выполнения тела цикла условие будет изменяться, и рано или поздно мы выйдем из цикла. В противном случае получаем бесконечный цикл.

Перейдем к циклу с предусловием. Конструкция очень похожа, но проверка условия цикла будет происходить до выполнения тела цикла. Это значит в первую очередь то, что если условие выполения цикла ложно изначально, то тело цикла не выполнится ни одного раза. В JavaScript для его записи используется, как правило, оператор while.

Рис. 3: Использование оператора while для записи цикла с предусловием

На рисунке 3 заранее присвоено истинное значение, в теле цикла также должно быть изменение условия на ложное, иначе получим бесконечный цикл.

Несмотря на то, что оператор for по большей части используется для циклов по счетчику [7], с помощью него также можно написать цикл с предусловием.

Рис. 4: Использование оператора for для записи цикла с предусловием

Глава 3. Примеры использования итерационных алгоритмов

3.1 Алгоритмы линейного поиска

При работе с массивами данных зачастую требуется найти какой-либо элемент и произвести с ним действие. Для этого переменной условия выхода из цикла присваивается искомое значение, и идет просмотр элементов массива. Для относительно простых задач по поиску необходимых элементов массива будет достаточно использовать линейный поиск.

Сразу отметим очевидность использование базовых структур с итерацией либо рекурсией для математических вычислений, поэтому в рамках данной работы эти примеры рассматривать не будем.

В самом простом варианте используется линейный поиск с использованием цикла со счетчиком: просматриваются все элементы массива на предмет совпадения с искомым значением.

Рис. 5: Линейный поиск (на основе [3])

Видим, что если искомое значение не найдется, программа дает ответ «не найдено», заданный заранее. n здесь – переменная, обозначающая последний элемент массива, i – счетчик (ее значение также является номером просматриваемого элемента массива), x – искомое значение. Счетчик увеличивает значение на 1 после каждой итерации. Обратим внимание, что если искомых элементов в массиве несколько, в результате показан будет только последний из них, а не все.

Недостаток данного алгоритма в том, что даже если искомое значение найдено, все равно продолжается просмотр элементов массива. Чтобы оптимизировать этот алгоритм, можно останавливать его при первом же нахождении нужного значения – добавляется команда break и выводится результат. В противном случае просмотр элементов пройдет до конца, и в результате получим ответ not found [3].

В обоих случаях происходит две проверки каждого элемента массива: проверка условия (не вышли ли мы за пределы от 1 до n) и сверка с искомым значением. Чтобы отбросить первый этап, можно воспользоваться алгоритмом линейного поиска с ограничителем. Здесь вместо оператора for используется while, что делает алгоритм более эффективным [4].

Рис. 6: Линейный поиск с ограничителем (на основе [3]);

Мы вводим переменную last и помещаем в нее значение последнего элемента массива. Счетчику задается значение 1, а искомое значение помещаем в последний элемент (то есть у нас теперь гарантированно есть искомый результат, в конце просто нужно будет сверить исходное значение последнего элемента массива с искомым). Затем до тех пор, пока значение просматриваемого элемента не совпадает с искомым, происходит увеличение счетчика. Присваиваем последнему элементу его исходное значение. Затем у нас идет ветвление: если найденное значение не последнее, выводим его значение. Если окажется, что замененное значение A[n] и было истинным, у нас также есть ответ. В противном случае, ответ not found.

3.2 Алгоритмы сортировки

Для более сложных задач перед поиском желательно предварительно провести сортировку массива. Для этой процедуры у каждого элемента массива мы имеем в виду два атрибута: ключ сортировки (то свойство, по которому необходимо сортировать элементы) и сопутствующие данные (все остальные атрибуты элемента) [3].

Один из простых вариантов – это сортировка выбором. Она подойдет лучше всего для небольших массивов. В этом варианте мы находим самое малое значение ключа сортировки и помещаем этот элемент на первое место массива, затем находим второй по величине элемент и перемещаем на второе, и так далее до предпоследнего. Здесь работает алгоритм линейного поиска, рассмотренный выше.

Также часто используется сортировка вставкой.

Рис. 7: Наглядное представление сортировки вставкой (Источник: [4])

Смысл ее состоит в том, что текущий элемент массива (A[j]) сравнивается со всеми уже отсортированными элементами. Если его ключ меньше элемента из отсортированной части массива (A[i]), он занимает его место, и все последующие элементы сдвигаются на 1.