Файл: Рекурсивные и итерационные алгоритмы: особенности и примеры использования (ПОНЯТИЕ РЕКУРСИВНОГО АЛГОРИТМА).pdf

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

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

Рассмотрим пример для функции вычисления факториала: дерево рекурсии при вычислении 5! (рисунок 2).

Рисунок 2 - Дерево рекурсии при вычислении факториала числа 5

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

Рисунок 3 - Вычисление 5 – ого числа Фибоначчи (Fb(5)).

Упомянутый анализ практической сложности программ показывает, что часто асимптотически более сложные итеративные алгоритмы, на практике становятся более эффективными. Сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро. Причина, как уже было сказано, кроется в том, что в теории не учтена зависимость времени работы программы от количества вызовов вложенных подпрограмм. Неэффективность рекурсии проявляется в том, что одни и те же вычисления производятся много раз. Особенно сильно это проявляется в методе, который был самым востребованным при построении теоретически быстрых рекурсивных алгоритмов, – методе бинарного разбиения на независимые подзадачи. Когда подзадачи независимы, это часто приводит к недопустимо большим затратам времени, так как одни и те же подзадачи решаются многократно.

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

---

Технология, называемая восходящим динамическим программированием (bottom – up dynamic pгogгamming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Она применима к любому рекурсивному вычислению при условии, что мы можем позволить себе хранить все ранее вычисленные значения. Это в результате позволит уменьшить временную зависимость с экспоненциальной на линейную.

Нисходящее динамическое программирование (top – down dynamic pгogгamming). Оно позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления.

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

- часто это наиболее легкий метод написания алгоритма для задач, которые можно решить с помощью рекурсии (число фибоначчи, факториал);

- рекурсивно реализованные алгоритмы, при правильных на то основаниях, имеют лаконичную запись и менее трудоёмки при последующей отладке и модификации, они сокращают временные затраты на разработку, отладку и модификацию программных средств;

- целый ряд структур данных и многие объекты современных язы­ков программирования рекурсивны по самой своей сути (фрактальные объекты, иерархия классов в объектно – ориентированном программировании, древовидные регулярные структуры данных) и программы для работы с такими структурами выглядят намного более естественно в рекурсивной реализации;

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

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

Недостатки рекурсии заключаются в следующем:

- велика возможность войти в бесконечный цикл;

- при использовании некоторых формул слишком большие затраты памяти компьютера (к примеру, при вычислении числа Фибоначчи или факториалов, необходимо запоминать все значения чисел и вычислять одни и те же значения по многу раз);

---

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

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

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

ГЛАВА 2. ПОНЯТИЕ ИТЕРАЦИОННОГО АЛГОРИТМА

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

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

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

Метод хорд, или метод итерационных приближений, широко используется при решении различных алгебраических задач. В общих словах, сущность метода заключается в последовательном нахождении корней уравнения, с приближением найденного значения к заданному отклонению «эпсилон».

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

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

---

Рассмотрим метод коротких итераций для нахождения корней полиноминального уравнения.

Многочлен (или полином) от n переменных — это сумма одночленов или, строго, — конечная формальная сумма вида:

, (1)

где k – первый показатель степени полинома;

N – конечный показатель степени полинома;

а – коэффициенты перед неизвестными.

Более традиционная формула представления полинома n-ой степени будет выглядеть следующим образом:

(2)

Корень многочлена (не равного тождественно нулю), над полем k это элемент , (либо элемент расширения поля k), такой, что выполняются два следующих равносильных условия:

1 Данный многочлен делится на многочлен x-c;

2 Подстановка элемента c вместо x обращает уравнение:

(3)

в тождество.

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

Свойства корней многочлена:

1. Число корней многочлена степени n не превышает n даже в том случае, если кратные корни учитывать кратное количество раз.

2. Корни многочлена связаны с его коэффициентами формулами Виета.

Способ нахождения корней линейных и квадратичных многочленов, то есть способ решения линейных и квадратных уравнений, был известен ещё в древнем мире. Поиски формулы для точного решения общего уравнения третьей степени продолжались долгое время (следует упомянуть метод, предложенный Омаром Хайямом), пока не увенчались успехом в первой половине XVI века в трудах Сципиона дель Ферро, Никколо Тарталья и Джероламо Кардано. Формулы для корней квадратных и кубических уравнений позволили сравнительно легко получить формулы для корней уравнения четвертой степени.

То, что корни общего уравнения пятой степени и выше не выражаются при помощи рациональных функций и радикалов от коэффициентов, было доказано норвежским математиком Нильсом Абелем в 1826 году. Это совсем не означает, что корни такого уравнения не могут быть найдены. Во-первых, в частных случаях, при некоторых комбинациях коэффициентов, корни уравнения всё же могут быть определены. Во-вторых, существуют формулы для корней уравнений 5-й степени и выше, использующие специальные функции — эллиптические или гипергеометрические (например, корень Бринга).

В случае, если все коэффициенты многочлена рациональны, то нахождение его корней приводится к нахождению корней многочлена с целыми коэффициентами. Для рациональных корней таких многочленов существуют алгоритмы нахождения перебором кандидатов с использованием схемы Горнера, причем при нахождении целых корней перебор может быть существенно уменьшен приемом чистки корней. Также в этом случае можно использовать полиномиальный LLL-алгоритм [10].

---

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

ГЛАВА 3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ИТЕРАЦИОННОГО АЛГОРИТМА НАХОЖДЕНИЯ КОРНЕЙ УРАВНЕНИЯ

Итерация в программировании — организация обработки данных, при которой действия повторяются многократно, не приводя при этом к вызовам самих себя.

Метод секущих — итерационный численный метод приближённого нахождения корня уравнения.

Алгебраическое описание метода секущих.

Пусть задан диапазон абсцисс, находящийся между x₁ и x₂. Уравнение, содержащее хорду, имеет вид:

y = kx+b (4)

Найдем значения коэффициентов k и b и выразим через них первое приближение к корню.

(5)

Теперь возьмем координаты x₂ и x₃ и повторим все проделанные операции, найдя новое приближение к корню. Таким образом, итерационная формула метода секущих имеет вид:

(6)

Повторять операцию следует до тех пор, пока |x_i-x_i-1| не станет меньше или равно заданному значению погрешности .

Иногда методом секущих называют метод с итерационной формулой:

(7)

Этот метод можно считать разновидностью метода простой итерации, и он имеет меньшую скорость сходимости.

Итерации метода секущих сходятся к корню f(x), если начальные величины x₁ и x₂ достаточно близки к корню. Метод секущих является быстрым.

На рисунке 4 представлена блок-схема алгоритма.

Рисунок 4 - Схема алгоритма нахождения корня методом хорд

Так как для решения поставленной задачи требуется отыскание функции F(x), метод хорд и касательных достаточно трудно реализуем на программном уровне. Связано это с тем, что перед передачей функции в цикл, необходимо аналитически определить ее форму – представить коэффициенты перед соответствующими переменными. Если человек выполняет такую работу легко, то для ПК этот процесс будет трудным, нужно предусмотреть в программе алгоритм «отсеивания» незначащих коэффициентов перед соответствующими степенями и алгоритм передачи значений из одной функции в другую. Поэтому, ограничимся для данного задания полиномом 10-ой степени со всеми значащими коэффициентами.

---