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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Рекурсия. Перебор. Методы сокращения перебора, слайд №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. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Описание слайда:
Рекурсия. Определение В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция А вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


Рекурсия. Иллюстрация
Описание слайда:
Рекурсия. Иллюстрация

Слайд 7


Перебор с помощью рекурсии Даны N упорядоченных множеств U1, U2, …, UN (N – неизвестно) Требуется построить вектор A = (a1, a2, …, aN) A1є U1, A2є U2, …, ANє UN В алгоритме перебора вектор строится покомпонентно слева направо
Описание слайда:
Перебор с помощью рекурсии Даны 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 <a є Si>Do Backtrack (<вектор + а>,i+1) ; End; End;
Описание слайда:
Перебор с помощью рекурсии. Схема реализации Procedure Backtrack (<вектор,i>); Begin If <вектор является решением> Then <записать его> Else Begin <вычислить Si>; For <a є Si>Do Backtrack (<вектор + а>,i+1) ; End; End;

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию