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

Сентябрь 6, 2022

Главная
Алгебра
Рекурсия. Перебор. Методы сокращения перебора

Содержание

2. Рекурсия. Определение В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия)
3. Рекурсия. Основные положения Рекурсию надо использовать там, где она реально необходима. Числа Фибоначчи и факториалы –
4. Примеры использования рекурсии Поиск в глубину в графе Сортировка слиянием «Быстрая» сортировка (Хоара) Обход различного рода
5. Стек вызовов Рекурсия использует системный стек для запоминания вызываемых подпрограмм и их параметров Следите за стеком.
6. Рекурсия. Иллюстрация
7. Перебор с помощью рекурсии Даны N упорядоченных множеств U1, U2, …, UN (N – неизвестно) Требуется
8. Перебор с помощью рекурсии. Общая схема
9. Перебор с помощью рекурсии. Схема реализации Procedure Backtrack ( ); Begin If Then Else Begin ;
10. Задача о Ханойских башнях. История Древняя индийская легенда 1883 г. Франсуа Люка «Профессор Клаус» Современное название
11. Ханойские башни. Решение Допустим на штыре n дисков Необходимо каким-то образом(пока непонятно каким) перенести n-1 дисков
12. Ханойские башни. Графическая иллюстрация решения
13. Ханойские башни. Алгоритм решения. Функция Перенести_диск(номер_1, номер_2, количество) begin если (количество > 0) то begin номер_промежуточный
14. Меморизация. Предпосылки При реализации рекурсивных подпрограмм часто вызываются подпрограммы с одними и теми же параметрами, т.е.
15. Меморизация. Что это? От английского слова memo – памятка. Идея заключается в том, чтобы запомнить параметры
16. Меморизация. Особенности Эффективна, когда рекурсивная процедура или функция имеет целые параметры с небольшим диапазоном значений Тогда
17. Спасибо за внимание!
19. Скачать презентацию

Слайд 2

Рекурсия. Определение
В программировании рекурсия — вызов функции (процедуры) из неё же

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

Слайд 3

Рекурсия. Основные положения
Рекурсию надо использовать там, где она реально необходима.
Числа Фибоначчи

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

Слайд 4

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

рода деревьев (в повседневной жизни – дерево каталогов)
Практически незаменима в переборных задачах

Слайд 5

Стек вызовов
Рекурсия использует системный стек для запоминания вызываемых подпрограмм и их

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

Слайд 6

Рекурсия. Иллюстрация

Слайд 7

Перебор с помощью рекурсии
Даны N упорядоченных множеств U1, U2, …, UN

(N – неизвестно)
Требуется построить вектор A = (a1, a2, …, aN)
A1є U1, A2є U2, …, ANє UN
В алгоритме перебора вектор строится покомпонентно слева направо

Слайд 8

Перебор с помощью рекурсии. Общая схема

Слайд 9

Перебор с помощью рекурсии. Схема реализации
Procedure Backtrack (<вектор,i>);
Begin
If <вектор является решением>

Then <записать его>
Else Begin
<вычислить Si>;
For Do
Backtrack (<вектор + а>,i+1) ;
End;
End;

Слайд 10

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

Содержание

Рекурсия. ОпределениеВ программировании рекурсия — вызов функции (процедуры) из неё же

Рекурсия. Основные положенияРекурсию надо использовать там, где она реально необходима.Числа Фибоначчи

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

Стек вызововРекурсия использует системный стек для запоминания вызываемых подпрограмм и их