Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
18 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
206.65 kB
Просмотров:
65
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Рекурсия. Перебор. Методы](/documents_6/5916496f72a617400702c520feb4b1d7/img0.jpg)
Содержание слайда: Рекурсия. Перебор. Методы сокращения перебора
Автор: Заливако Сергей Сергеевич
выпускник БГУИР
№2 слайд![Рекурсия. Определение В](/documents_6/5916496f72a617400702c520feb4b1d7/img1.jpg)
Содержание слайда: Рекурсия. Определение
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию B, а функция B — функцию A.
Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
№3 слайд![Рекурсия. Основные положения](/documents_6/5916496f72a617400702c520feb4b1d7/img2.jpg)
Содержание слайда: Рекурсия. Основные положения
Рекурсию надо использовать там, где она реально необходима.
Числа Фибоначчи и факториалы – плохой пример использования рекурсии
Рекурсия – это всего лишь вызов подпрограммы в самой себе
Рекурсия используется для разбиения задачи на подзадачи и решения задачи с объемом меньше, чем исходная.
№4 слайд![Примеры использования](/documents_6/5916496f72a617400702c520feb4b1d7/img3.jpg)
Содержание слайда: Примеры использования рекурсии
Поиск в глубину в графе
Сортировка слиянием
«Быстрая» сортировка (Хоара)
Обход различного рода деревьев (в повседневной жизни – дерево каталогов)
Практически незаменима в переборных задачах
№5 слайд![Стек вызовов Рекурсия](/documents_6/5916496f72a617400702c520feb4b1d7/img4.jpg)
Содержание слайда: Стек вызовов
Рекурсия использует системный стек для запоминания вызываемых подпрограмм и их параметров
Следите за стеком.
Изменение размера стека:
Pascal: {$M <размер стека в байтах>, <максимальный размер стека>}
С++: #pragma comment(linker, "/STACK:<размер стека в байтах>")
№6 слайд![Рекурсия. Иллюстрация](/documents_6/5916496f72a617400702c520feb4b1d7/img5.jpg)
Содержание слайда: Рекурсия. Иллюстрация
№7 слайд![Перебор с помощью рекурсии](/documents_6/5916496f72a617400702c520feb4b1d7/img6.jpg)
Содержание слайда: Перебор с помощью рекурсии
Даны N упорядоченных множеств U1, U2, …, UN (N – неизвестно)
Требуется построить вектор A = (a1, a2, …, aN)
A1є U1, A2є U2, …, ANє UN
В алгоритме перебора вектор строится покомпонентно слева направо
№8 слайд![Перебор с помощью рекурсии.](/documents_6/5916496f72a617400702c520feb4b1d7/img7.jpg)
Содержание слайда: Перебор с помощью рекурсии. Общая схема
№9 слайд![Перебор с помощью рекурсии.](/documents_6/5916496f72a617400702c520feb4b1d7/img8.jpg)
Содержание слайда: Перебор с помощью рекурсии. Схема реализации
Procedure Backtrack (<вектор,i>);
Begin
If <вектор является решением>
Then <записать его>
Else Begin
<вычислить Si>;
For <a є Si>Do
Backtrack (<вектор + а>,i+1) ;
End;
End;
№10 слайд![Задача о Ханойских башнях.](/documents_6/5916496f72a617400702c520feb4b1d7/img9.jpg)
Содержание слайда: Задача о Ханойских башнях. История
Древняя индийская легенда
1883 г. Франсуа Люка «Профессор Клаус»
Современное название головоломки
№11 слайд![Ханойские башни. Решение](/documents_6/5916496f72a617400702c520feb4b1d7/img10.jpg)
Содержание слайда: Ханойские башни. Решение
Допустим на штыре n дисков
Необходимо каким-то образом(пока непонятно каким) перенести n-1 дисков на промежуточный штырь
Перенесем n-й диск на последний штырь
Таким же образом как и во втором шаге перенести n-1 дисков на последний штырь
№12 слайд![Ханойские башни. Графическая](/documents_6/5916496f72a617400702c520feb4b1d7/img11.jpg)
Содержание слайда: Ханойские башни. Графическая иллюстрация решения
№13 слайд![Ханойские башни. Алгоритм](/documents_6/5916496f72a617400702c520feb4b1d7/img12.jpg)
Содержание слайда: Ханойские башни. Алгоритм решения.
Функция Перенести_диск(номер_1, номер_2, количество)
begin
если (количество > 0) то begin
номер_промежуточный = 6 - номер_1 - номер_2;
Перенести_диск(номер_1, номер_промежуточный, количество – 1);
Вывести_действие(номер_1, номер_2);
Перенести_диск(номер_промежуточный, номер_1, количество – 1);
end;
end;
№14 слайд![Меморизация. Предпосылки При](/documents_6/5916496f72a617400702c520feb4b1d7/img13.jpg)
Содержание слайда: Меморизация. Предпосылки
При реализации рекурсивных подпрограмм часто вызываются подпрограммы с одними и теми же параметрами, т.е. выполняется «лишняя» работа
Такая особенность рекурсии уменьшает эффективность
№15 слайд![Меморизация. Что это? От](/documents_6/5916496f72a617400702c520feb4b1d7/img14.jpg)
Содержание слайда: Меморизация. Что это?
От английского слова memo – памятка.
Идея заключается в том, чтобы запомнить параметры уже вызывавшихся подпрограмм
В случае если такие параметры повторяться, то не вызывать подпрограмму
№16 слайд![Меморизация. Особенности](/documents_6/5916496f72a617400702c520feb4b1d7/img15.jpg)
Содержание слайда: Меморизация. Особенности
Эффективна, когда рекурсивная процедура или функция имеет целые параметры с небольшим диапазоном значений
Тогда для их хранения достаточно n-мерного (n – число параметров функции) булевского массива
Если параметры имеют сложный вид, то необходимы сложные структуры данных, что вряд ли оправданно
№17 слайд![Спасибо за внимание!](/documents_6/5916496f72a617400702c520feb4b1d7/img16.jpg)
Содержание слайда: Спасибо за внимание!
№18 слайд![Вопросы?](/documents_6/5916496f72a617400702c520feb4b1d7/img17.jpg)
Содержание слайда: Вопросы?