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

Введение

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

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

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

Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. [5, 67] Правильность работы рекурсивных алгоритмов зависит от технических возможностей процессора, что рассмотрено в настоящей работе.

Рекурсия существует вокруг нас практически везде: в литературных произведениях, математике, биологии, физике и соответственно, в программировании. Рекурсия является общим методом научного познания, эффективно применяется во многих научных дисциплинах и стала неотъемлемой их частью.

Актуальность темы исследования заключается в том, что любую задачу можно решить с использованием итерационного алгоритма и рекурсии. Рекурсия позволяет создавать "понятные" и "читаемые" алгоритмы, быстро сходящиеся, но необходимо грамотно использовать рекурсивные методы вместо простых итерационных алгоритмов. Правильность работы рекурсии зависит от технических характеристик компьютера. Процессор не может обеспечить бесконечный рекурсивный спуск вниз, необходимо создавать промежуточные точки выхода из рекурсии, позволяющие проводить анализ правильности работы алгоритма. Итерационные алгоритмы используются при реализации итерационных численных методов. В итерационных алгоритмах необходимо обеспечить обязательное достижение условия выхода из цикла (сходимость итерационного процесса).

Объект исследования – алгоритмы.

Предметом исследования являются– рекурсивные и итерационные алгоритмы.

Цель курсовой работы заключается в расширении систематизации теоретических знаний по теме: "Рекурсивные и итерационные алгоритмы: особенности и примеры использования".

Задачи исследования

• провести анализ научных источников по теме «Рекурсивные и итерационные алгоритмы: особенности и примеры использования»;
• описать принципы написания итерационных алгоритмов;
• описать принципы написания рекурсивных алгоритмов;
• привести примеры задач с итерационным методом решения;
• привести примеры использования рекурсии;
• сравнить работу итерационных алгоритмов и рекурсии.

При проведении исследования были изучены научные труды по основам алгоритмизации и программирования, приведенные в списке литературы.

В научных трудах описаны алгоритмические конструкци, принципы написания итерационных и рекурсивных алгоритмов.

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

1. Итерационные алгоритмы

1.1. Определение итерационного алгоритма

Алгоритм - это точное, сформулированное на определенном языке, конечное описание того или иного способа действия, основанного на применении исполнимых элементарных однозначно трактуемых шагов. [8, 42]

Любой алгоритм имеет пять особенностей.

1) Конечность алгоритма (финитность). Означает, что алгоритм всегда должен заканчиваться после конечного числа шагов.

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

3) Наличие входных данных. Алгоритм имеет некоторое число входных величин, заданных ему до начала работы.

4) Наличие выходных данных. Результатом выполнения любого алгоритма всегда будет обработанная информация, выдаваемая в том или ином виде и, следовательно, алгоритм обязательно имеет одну или несколько выходных величин, являющихся результатом обработки входных данных.

5) Эффективность алгоритма. Алгоритм, который выполняет действие за меньшее число шагов признается более эффективным.

Алгоритм является абстракцией и поэтому один и тот же алгоритм можно представить многими способами. Если с алгоритмом работает человек, то это может быть традиционный язык (русский, английский), язык картинок и пиктограмм, а также математические формулы. [7, 12]

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

Для организации алгоритмов иногда используются способы дополнительные, позволяющие решение той или иной задачи [1, 34]. Среди них выделяют:

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

2.Рекурсия – организация алгоритма, при которой процедура, состоящая из набора шагов, обращается к самой себе (рекурсивная процедура).

Рассмотрим подробнее способ итерации:

Итерационный цикл -оператор цикла, для которого число повторений тела цикла заранее неизвестно. В итерационных циклах на каждом шаге вычислений происходит последовательное приближение и проверка условия достижения искомого результата. Выход из итерационного цикла осуществляется в случае выполнения заданного условия. Различают итерационные циклы с предусловиями и с постусловиями.[11, 19]

Итерационный процесс – процесс последовательного вычисления значений по формулам; процесс последовательных приближений.

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

Примером такого рода алгоритмов, могут служить алгоритмы и методы приближенного вычисления функций и решения различного рода уравнений [3,120].

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

В итерационных алгоритмах решение задачи реализуется путем последовательного приближения к искомому результату^[1]. Процесс является циклическим, поскольку заключается в многократных вычислениях. Начальное приближение Y₀ выбирается заранее или задается по определенным правилам. Заканчивается итерационное вычисление при выполнении условия |Y_i –Y_i-1| <d

где d - допустимая ошибка вычисления.

Типовая структура алгоритма итерационных вычислений имеет вид, показанный на рисунке 1.

Рисунок 1 – Структура итерационного алгоритма

Пример итерационного алгоритма

Составить алгоритм вычисления функции y= √x c точностью d, используя рекуррентную формулу

y _i+1=0.5*(x/y_i+y_i).

Этот метод называется методом Ньютона, но начало получил из Древней Греции и приписывается Герону Александрийскому. Герон жил в I веке н.э. и описал в своих книгах механизмы извлечения квадратного корня из чисе. Данный метод настолько прост, понятен и есть возможность проводить вычисления с заданной точностью. Интересно, что и в наше время метод Герона используется в вычислительных машинах и калькуляторах.

Заслуга метода Ньютона в том, что он описал данный механизм нахождения квадратного корня с использованием формул, которые в дальнейшем стали называться как итерационными формулами. Проиллюстрируем на следующем примере метод Герона^[2].

Найдем приближенное значение квадратного корня из 720.

Ближайшее к 720 число, из которого извлекается квадратный корень, есть число 729, оно имеет корнем 27. Разделив 720 на 27, получаем 26. Найдем среднее арифметическое чисел 27 и 26.

Получаем (26 + 27) : 2 = 53 : 2 = 

Это и есть результат. Если возвести это число в квадрат, получим 720.

Где -это погрешность алгоритма.

Если начальное приближение y₁ = x , тогда на первом цикле вычисления будем иметь

y ₁=0.5*(x/y₁+y₁)

Блок - схема алгоритма решения примера 4 приведена на рисунке 2.

Рисунок 2-Блок-схема алгоритма

Приведем пример вычисления корня уравнения методом дихотомии или половинного деления.

Изложение метода, приведенное в работе Окулова С.М. [4, 451]

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

Будем считать, что корень  функции  отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция  непрерывна на отрезке ,

 и  - единственный корень уравнения .

(Мы не рассматриваем случай, когда корней на отрезке  несколько, то есть более одного. В качестве  можно взять и другое достаточно малое положительное число, например, .)