🗊Презентация Рекурсия. Перебор

Рекурсия. Перебор Лектор: Михно Марк

Что такое рекурсия? Рекурсия — это прием программирования, при котором решение задачи сводится к некоторым действиям плюс решение такой же задачи, но в более простом случае. Под более простым подразумевается либо случай с меньшими входными данными, либо с меньшим их количеством.

Пример Нахождение факториала натурального числа n. По определению : n! = 1 * 2 * … * n Видоизменим равенство : n! = (1 * 2 * … * n – 1) * n Таким образом, n! = (n – 1) ! * n В словесной формулировке результаты преобразований будут звучать так : чтобы найти факториал числа n, надо найти факториал числа n – 1, а затем домножить его на число n.

Для описания рекурсивного решения необходимы две четко определенные вещи : Для описания рекурсивного решения необходимы две четко определенные вещи : Правило, по которому решение задачи в сложном случае сводится к решению такой же задачи, но в более простом случае (рекурсивный переход). Условие, при котором дальнейшее упрощение нужно прекратить (терминальное условие). При отсутствии этого условия процесс упрощения будет продолжаться до бесконечности.

Ханойские башни Дано три стержня. В начальный момент времени на первый нанизано N колец различного диаметра так, что они образуют пирамидку :

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

Для N, равного 1 или 2, решения очевидны. Для N, равного 1 или 2, решения очевидны. При N = 3 можно сделать следующее замечание : Пока верхние два кольца не будут перемещены на другой стержень, с нижним кольцом по правилам ничего сделать нельзя. Поэтому можно временно про нижнее кольцо «позабыть» и решать только задачу переноса двух верхних колец на второй стержень. После этого «освободившееся» нижнее кольцо можно перенести на третий стержень, а затем опять вернуться к задаче о перемещении первых двух колец. Таким образом задача для N=3 сводится к двум задачам для N=2.

Из этих рассуждений можно вывести схему упрощения задачи и сведения ее решения к более простому случаю : Из этих рассуждений можно вывести схему упрощения задачи и сведения ее решения к более простому случаю : Чтобы перенести n колец с одного стержня на другой, необходимо для начала n - 1 кольцо поместить на третий стержень, потом перенести самое большое кольцо на нужный стержень и снова переместить n - 1 кольцо.

Основной идеей рекурсивного решения является «вера» в то, что внутренняя функция успешно справится с решением своей более простой задачи. А это вполне возможно, так как внутренняя функция может быть либо последней в цепочке рекурсии (тогда она выдает простой ответ), либо от нее цепочка будет тянуться дальше, тогда все зависит от правильности рекурсивного соотношения. Основной идеей рекурсивного решения является «вера» в то, что внутренняя функция успешно справится с решением своей более простой задачи. А это вполне возможно, так как внутренняя функция может быть либо последней в цепочке рекурсии (тогда она выдает простой ответ), либо от нее цепочка будет тянуться дальше, тогда все зависит от правильности рекурсивного соотношения.

Рекурсивный перебор Перебором мы будем называть в первую очередь перебор некоторых, скажем так, комбинаторных объектов. Основная цель перебора—перебрать все объекты из некоторого множества, дабы что-то сделать с каждым. Наиболее часто, встречаются три варианта : либо надо найти объект (любой), удовлетворяющий некоторому условию. либо посчитать количество таких объектов,. либо найти в некотором смысле оптимальный объект (дающий минимальную стоимость и т.п.)

Конечно, перебор можно писать по-разному. Но наиболее общим и в большинстве случаев довольно простым является рекурсивный перебор, также называемый перебором с возвратом. Помимо более простой реализации, он обладает рядом других достоинств: например, в нем возможно очень легко реализовывать различные отсечения и эвристики. Конечно, перебор можно писать по-разному. Но наиболее общим и в большинстве случаев довольно простым является рекурсивный перебор, также называемый перебором с возвратом. Помимо более простой реализации, он обладает рядом других достоинств: например, в нем возможно очень легко реализовывать различные отсечения и эвристики.

Давайте научимся решать следующую задачу : Давайте научимся решать следующую задачу : Дан массив из N различных чисел. Мы хотим узнать количество различных способов выбрать некоторые числа из этого массива так, чтобы их сумма равнялась заданному числу K. Задача имеет множество решений, но давайте попробуем применить технику перебора – то есть просто попробуем перебрать все возможные подмножества чисел, затем найдем их сумму и сравним с K.

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

Давайте попробуем перебрать все возможные расстановки восьми ферзей рекурсивным перебором. Давайте попробуем перебрать все возможные расстановки восьми ферзей рекурсивным перебором. Воспользуемся следующим переходом: выберем, в какую клеточку поставить первого ферзя, а потом переберем все возможные расстановки семи ферзей в оставшиеся клетки. Напишем следующую процедуру.

Попытаемся оценить время работы. Мы выбираем, куда поставим первого ферзя – 64 варианта, потом второго – 63 варианта, и так далее. Попытаемся оценить время работы. Мы выбираем, куда поставим первого ферзя – 64 варианта, потом второго – 63 варианта, и так далее. Получаем 64 * 63 * .. * 58 вариантов, что, конечно, слишком большое число. Решение необходимо оптимизировать. Давайте, например, при переборе не пытаться ставить ферзя в клеточку, которая уже находится под боем. Оказывается, этого небольшого отсечения ненужных вариантов более чем хватает для быстрого решения задачи.

Вот так изменится процедура find: Вот так изменится процедура find:

Прием, который позволяет уменьшить количество рассматриваемых вариантов в переборе, называется отсечением. Существует огромное количество разных по сложности и эффективности отсечений и эвристик. Прием, который позволяет уменьшить количество рассматриваемых вариантов в переборе, называется отсечением. Существует огромное количество разных по сложности и эффективности отсечений и эвристик. Вот самые популярные из них: Отсечение по ответу (откидывание заведомо ненужных вариантов) Отсечение по времени. Оптимальный порядок перебора. Жадных поиск каких-то решений еще до запуска перебора.

Рекурсия очень требовательная к ресурсам компьютера, и писать её нужно аккуратно. Рекурсия очень требовательная к ресурсам компьютера, и писать её нужно аккуратно. Все что можно закодить рекурсией, можно в тероии закодить итеративно (и наоборот). Если вы можете без особых проблем написать итеративное решение задачи, то, скорее всего, оно будет работать лучше рекурсивного.

Конец спасибо