Презентация Рекурсия. Перебор. Методы сокращения перебора онлайн

Содержание слайда: Рекурсия. Перебор. Методы сокращения перебора Автор: Заливако Сергей Сергеевич выпускник БГУИР

Содержание слайда: Рекурсия. Определение В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Содержание слайда: Рекурсия. Основные положения Рекурсию надо использовать там, где она реально необходима. Числа Фибоначчи и факториалы – плохой пример использования рекурсии Рекурсия – это всего лишь вызов подпрограммы в самой себе Рекурсия используется для разбиения задачи на подзадачи и решения задачи с объемом меньше, чем исходная.

Содержание слайда: Примеры использования рекурсии Поиск в глубину в графе Сортировка слиянием «Быстрая» сортировка (Хоара) Обход различного рода деревьев (в повседневной жизни – дерево каталогов) Практически незаменима в переборных задачах

Содержание слайда: Стек вызовов Рекурсия использует системный стек для запоминания вызываемых подпрограмм и их параметров Следите за стеком. Изменение размера стека: Pascal: {$M <размер стека в байтах>, <максимальный размер стека>} С++: #pragma comment(linker, "/STACK:<размер стека в байтах>")

Содержание слайда: Рекурсия. Иллюстрация

Содержание слайда: Перебор с помощью рекурсии Даны N упорядоченных множеств U1, U2, …, UN (N – неизвестно) Требуется построить вектор A = (a1, a2, …, aN) A1є U1, A2є U2, …, ANє UN В алгоритме перебора вектор строится покомпонентно слева направо

Содержание слайда: Перебор с помощью рекурсии. Общая схема

Содержание слайда: Перебор с помощью рекурсии. Схема реализации Procedure Backtrack (<вектор,i>); Begin If <вектор является решением> Then <записать его> Else Begin <вычислить Si>; For <a є Si>Do Backtrack (<вектор + а>,i+1) ; End; End;

Содержание слайда: Задача о Ханойских башнях. История Древняя индийская легенда 1883 г. Франсуа Люка «Профессор Клаус» Современное название головоломки

Содержание слайда: Ханойские башни. Решение Допустим на штыре n дисков Необходимо каким-то образом(пока непонятно каким) перенести n-1 дисков на промежуточный штырь Перенесем n-й диск на последний штырь Таким же образом как и во втором шаге перенести n-1 дисков на последний штырь

Содержание слайда: Ханойские башни. Графическая иллюстрация решения

Содержание слайда: Ханойские башни. Алгоритм решения. Функция Перенести_диск(номер_1, номер_2, количество) begin если (количество > 0) то begin номер_промежуточный = 6 - номер_1 - номер_2; Перенести_диск(номер_1, номер_промежуточный, количество – 1); Вывести_действие(номер_1, номер_2); Перенести_диск(номер_промежуточный, номер_1, количество – 1); end; end;

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

Содержание слайда: Меморизация. Что это? От английского слова memo – памятка. Идея заключается в том, чтобы запомнить параметры уже вызывавшихся подпрограмм В случае если такие параметры повторяться, то не вызывать подпрограмму

Содержание слайда: Меморизация. Особенности Эффективна, когда рекурсивная процедура или функция имеет целые параметры с небольшим диапазоном значений Тогда для их хранения достаточно n-мерного (n – число параметров функции) булевского массива Если параметры имеют сложный вид, то необходимы сложные структуры данных, что вряд ли оправданно

Содержание слайда: Спасибо за внимание!

Содержание слайда: Вопросы?