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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Рекурсия. Перебор. Методы сокращения перебора. Доклад-сообщение содержит 18 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 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 (); Begin If Then Else Begin ; For Do Backtrack (,i+1) ; End; End;

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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