Презентация Рекурсия. Перебор онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Рекурсия. Перебор абсолютно бесплатно. Урок-презентация на эту тему содержит всего 24 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Рекурсия. Перебор
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:24 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:219.66 kB
- Просмотров:62
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Что такое рекурсия? Рекурсия](/documents_6/6cd48c8d499856719c5a22ba356076fd/img1.jpg)
Содержание слайда: Что такое рекурсия?
Рекурсия — это прием программирования, при котором решение задачи сводится к некоторым действиям плюс решение такой же задачи, но в более простом случае. Под более простым подразумевается либо случай с меньшими входными данными, либо с меньшим их количеством.
№3 слайд
![Пример Нахождение факториала](/documents_6/6cd48c8d499856719c5a22ba356076fd/img2.jpg)
Содержание слайда: Пример
Нахождение факториала натурального числа n.
По определению : n! = 1 * 2 * … * n
Видоизменим равенство : n! = (1 * 2 * … * n – 1) * n
Таким образом, n! = (n – 1) ! * n
В словесной формулировке результаты преобразований будут звучать так : чтобы найти факториал числа n, надо найти факториал числа n – 1, а затем домножить его на число n.
№4 слайд
![Для описания рекурсивного](/documents_6/6cd48c8d499856719c5a22ba356076fd/img3.jpg)
Содержание слайда: Для описания рекурсивного решения необходимы две четко определенные вещи :
Для описания рекурсивного решения необходимы две четко определенные вещи :
Правило, по которому решение задачи в сложном случае сводится к решению такой же задачи, но в более простом случае (рекурсивный переход).
Условие, при котором дальнейшее упрощение нужно прекратить (терминальное условие). При отсутствии этого условия процесс упрощения будет продолжаться до бесконечности.
№7 слайд
![Требуется перенести все](/documents_6/6cd48c8d499856719c5a22ba356076fd/img6.jpg)
Содержание слайда: Требуется перенести все кольца с первого стержня на третий за минимальное количество ходов, соблюдая два правила:
Требуется перенести все кольца с первого стержня на третий за минимальное количество ходов, соблюдая два правила:
Можно брать только свободное кольцо (то, на котором ничего не лежит).
Взятое кольцо можно нанизывать на любой стержень, но нельзя класть большее кольцо на меньшее.
№8 слайд
![Для N, равного или , решения](/documents_6/6cd48c8d499856719c5a22ba356076fd/img7.jpg)
Содержание слайда: Для N, равного 1 или 2, решения очевидны.
Для N, равного 1 или 2, решения очевидны.
При N = 3 можно сделать следующее замечание : Пока верхние два кольца не будут перемещены на другой стержень, с нижним кольцом по правилам ничего сделать нельзя.
Поэтому можно временно про нижнее кольцо «позабыть» и решать только задачу переноса двух верхних колец на второй стержень. После этого «освободившееся» нижнее кольцо можно перенести на третий стержень, а затем опять вернуться к задаче о перемещении первых двух колец. Таким образом задача для N=3 сводится к двум задачам для N=2.
№9 слайд
![Из этих рассуждений можно](/documents_6/6cd48c8d499856719c5a22ba356076fd/img8.jpg)
Содержание слайда: Из этих рассуждений можно вывести схему упрощения задачи и сведения ее решения к более простому случаю :
Из этих рассуждений можно вывести схему упрощения задачи и сведения ее решения к более простому случаю :
Чтобы перенести n колец с одного стержня на другой, необходимо для начала n - 1 кольцо поместить на третий стержень, потом перенести самое большое кольцо на нужный стержень и снова переместить n - 1 кольцо.
№11 слайд
![Основной идеей рекурсивного](/documents_6/6cd48c8d499856719c5a22ba356076fd/img10.jpg)
Содержание слайда: Основной идеей рекурсивного решения является «вера» в то, что внутренняя функция успешно справится с решением своей более простой задачи. А это вполне возможно, так как внутренняя функция может быть либо последней в цепочке рекурсии (тогда она выдает простой ответ), либо от нее цепочка будет тянуться дальше, тогда все зависит от правильности рекурсивного соотношения.
Основной идеей рекурсивного решения является «вера» в то, что внутренняя функция успешно справится с решением своей более простой задачи. А это вполне возможно, так как внутренняя функция может быть либо последней в цепочке рекурсии (тогда она выдает простой ответ), либо от нее цепочка будет тянуться дальше, тогда все зависит от правильности рекурсивного соотношения.
№12 слайд
![Рекурсивный перебор Перебором](/documents_6/6cd48c8d499856719c5a22ba356076fd/img11.jpg)
Содержание слайда: Рекурсивный перебор
Перебором мы будем называть в первую очередь перебор некоторых, скажем так, комбинаторных объектов.
Основная цель перебора—перебрать все объекты из некоторого множества, дабы что-то сделать с каждым.
Наиболее часто, встречаются три варианта :
либо надо найти объект (любой), удовлетворяющий некоторому условию.
либо посчитать количество таких объектов,.
либо найти в некотором смысле оптимальный объект (дающий минимальную стоимость и т.п.)
№13 слайд
![Конечно, перебор можно писать](/documents_6/6cd48c8d499856719c5a22ba356076fd/img12.jpg)
Содержание слайда: Конечно, перебор можно писать по-разному. Но наиболее общим и в большинстве случаев довольно простым является рекурсивный перебор, также называемый перебором с возвратом. Помимо более простой реализации, он обладает рядом других достоинств: например, в нем возможно очень легко реализовывать различные отсечения и эвристики.
Конечно, перебор можно писать по-разному. Но наиболее общим и в большинстве случаев довольно простым является рекурсивный перебор, также называемый перебором с возвратом. Помимо более простой реализации, он обладает рядом других достоинств: например, в нем возможно очень легко реализовывать различные отсечения и эвристики.
№14 слайд
![Давайте научимся решать](/documents_6/6cd48c8d499856719c5a22ba356076fd/img13.jpg)
Содержание слайда: Давайте научимся решать следующую задачу :
Давайте научимся решать следующую задачу :
Дан массив из N различных чисел. Мы хотим узнать количество различных способов выбрать некоторые числа из этого массива так, чтобы их сумма равнялась заданному числу K.
Задача имеет множество решений, но давайте попробуем применить технику перебора – то есть просто попробуем перебрать все возможные подмножества чисел, затем найдем их сумму и сравним с K.
№18 слайд
![Давайте попробуем перебрать](/documents_6/6cd48c8d499856719c5a22ba356076fd/img17.jpg)
Содержание слайда: Давайте попробуем перебрать все возможные расстановки восьми ферзей рекурсивным перебором.
Давайте попробуем перебрать все возможные расстановки восьми ферзей рекурсивным перебором.
Воспользуемся следующим переходом: выберем, в какую клеточку поставить первого ферзя, а потом переберем все возможные расстановки семи ферзей в оставшиеся клетки. Напишем следующую процедуру.
№20 слайд
![Попытаемся оценить время](/documents_6/6cd48c8d499856719c5a22ba356076fd/img19.jpg)
Содержание слайда: Попытаемся оценить время работы. Мы выбираем, куда поставим первого ферзя – 64 варианта, потом второго – 63 варианта, и так далее.
Попытаемся оценить время работы. Мы выбираем, куда поставим первого ферзя – 64 варианта, потом второго – 63 варианта, и так далее.
Получаем 64 * 63 * .. * 58 вариантов, что, конечно, слишком большое число. Решение необходимо оптимизировать.
Давайте, например, при переборе не пытаться ставить ферзя в клеточку, которая уже находится под боем.
Оказывается, этого небольшого отсечения ненужных вариантов более чем хватает для быстрого решения задачи.
№22 слайд
![Прием, который позволяет](/documents_6/6cd48c8d499856719c5a22ba356076fd/img21.jpg)
Содержание слайда: Прием, который позволяет уменьшить количество рассматриваемых вариантов в переборе, называется отсечением. Существует огромное количество разных по сложности и эффективности отсечений и эвристик.
Прием, который позволяет уменьшить количество рассматриваемых вариантов в переборе, называется отсечением. Существует огромное количество разных по сложности и эффективности отсечений и эвристик.
Вот самые популярные из них:
Отсечение по ответу (откидывание заведомо ненужных вариантов)
Отсечение по времени.
Оптимальный порядок перебора.
Жадных поиск каких-то решений еще до запуска перебора.
№23 слайд
![Рекурсия очень требовательная](/documents_6/6cd48c8d499856719c5a22ba356076fd/img22.jpg)
Содержание слайда: Рекурсия очень требовательная к ресурсам компьютера, и писать её нужно аккуратно.
Рекурсия очень требовательная к ресурсам компьютера, и писать её нужно аккуратно.
Все что можно закодить рекурсией, можно в тероии закодить итеративно (и наоборот).
Если вы можете без особых проблем написать итеративное решение задачи, то, скорее всего, оно будет работать лучше рекурсивного.
Скачать все slide презентации Рекурсия. Перебор одним архивом:
Похожие презентации
-
Рекурсия. Перебор. Методы сокращения перебора
-
Процедуры и функции в Паскале. Рекурсия
-
Рекурсия. Определение факториала. (Тема 10)
-
Рекурсивные функции
-
Рекурсия. Описание подпрограмм
-
Рекурсивные алгоритмы. ЕГЭ-2017 по информатике. Задание 11
-
Рекурсия. Рекурсивная функция
-
Рекурсия и деревья
-
Программирование. Рекурсия
-
Перебор подмножеств и перестановок