Методы разработки алгоритмов 1 Итерация или рекурсивность 2 Метод полного перебора 3 Метод Greedy– «жадный» алгоритм 4 Метод перебора с возвратом 5 Метод. - презентация

1 Методы разработки алгоритмов 1 Итерация или рекурсивность 2 Метод полного перебора 3 Метод Greedy– «жадный» алгоритм 4 Метод перебора с возвратом 5 Метод «разделяй и властвуй»

2 Итерация или рекурсивность Элементарные случаи, которые вычисляются непосредственно Случаи, которые хотя и не могут быть решены явно, однако процесс вычислений обязательно сводится к элементарному случаю Рекурсия определяется как ситуация, когда подпрограмма обращается к самой себе либо непосредственно, либо посредством другой подпрограммы. Правильное определение любого рекурсивного алгоритма предполагает, что в процессе осуществления вычислений должны существовать: Например, в рекурсивном определении функции факториала fact:NN - Элементарный случай n=0. В этом случае значения fact (0) вычисляется неполсредственно, а именно fact (0)=1 -Неэлементарный случай n>0. В таких случаях значения fact (n) не могут быть вычислены непосредственно, но процесс вычислений сводится к элементарному случаю fact (0). Напрмер, для n=3 получаем: Fact(3)=3 fact(2)=32fact(1)=321 fact (0) = 3 211=6

3 Рекурсивное определение функции fact(n) является сходящимся определением Управление стеком в случае вызова функции fact(3): AR – адрес возврата n – текущее значение фактического параметра *** - место для запоминания значений f, возвращаемых функцией fact. Занесение данных в стек Извлечение данных function Fact (n:integer):longint; begin if n=0 then Fact:=1 else Fact:=n*Fact(n-1) end;

4 Рассмотрим рекурсивное определение функции incons:NN Следовательно, приведённое рекурсивное определение функции incons(n) является расходящимся определением. Теоретически процесс вычислений будет вычисляться бесконечно, на практике же вычисления будут остановлены ОС в момент переполнения памяти, выделенной для стека, или превышения разрядности арифметического устройства. Для функции incons:NN можно выделить элементарный случай n=0 и неэлементарные случаи n>0. Но, в отличие от функции fact (n), для n>0 значения incons(n) не могут быть вычислены, поскольку процесс вычисления ведёт к incons( ). Например, для n=3 получаем: Incons(3)=3incons(4)=34incons(5) =345incons(6)= …

5 Любой рекурсивный алгоритм может быть преобразован в итеративный и обратно. При выборе метода программирования должны учитываться преимущества и недостатки каждого метода. Характеристики Итерация Рекурсия 1. Расход памяти Малый Большой 2. Время выполнения Одинаковое 3. Структура программы Сложная Простая 4. Трудоёмкость написания программы Большая Малая 5. Тестирование и отладка программы Простые Сложные Сравнение итерации и рекурсии (компьютерная обработка текстов)

6 Вопросы и упражнения: 1. Объясните термин рекурсия. 2. Какие условия должны быть соблюдены, чтобы определение рекурсивного алгоритма было правильным? 3. В чём разница между сходящейся и расходящейся рекурсиями? 4. Укажите достоинства и недостатки итеративных и рекурсивных алгоритмов. Какие из следующих рекурсивных определений являются сходящимися? Обоснуйте Ваш ответ.