Содержание
- 2. Что такое рекурсия? Рекурсия — это прием программирования, при котором решение задачи сводится к некоторым действиям
- 3. Пример Нахождение факториала натурального числа n. По определению : n! = 1 * 2 * …
- 4. Для описания рекурсивного решения необходимы две четко определенные вещи : Правило, по которому решение задачи в
- 5. Терминальное условие Рекурсивный переход. С точки зрения программирования рекурсивное решение записывается в виде функции, содержащей вызов
- 6. Ханойские башни Дано три стержня. В начальный момент времени на первый нанизано N колец различного диаметра
- 7. Требуется перенести все кольца с первого стержня на третий за минимальное количество ходов, соблюдая два правила:
- 8. Для N, равного 1 или 2, решения очевидны. При N = 3 можно сделать следующее замечание
- 9. Из этих рассуждений можно вывести схему упрощения задачи и сведения ее решения к более простому случаю
- 10. Можно написать процедуру moveTo, которая будет переносить N колец со стержня с номером from на стержень
- 11. Основной идеей рекурсивного решения является «вера» в то, что внутренняя функция успешно справится с решением своей
- 12. Рекурсивный перебор Перебором мы будем называть в первую очередь перебор некоторых, скажем так, комбинаторных объектов. Основная
- 13. Конечно, перебор можно писать по-разному. Но наиболее общим и в большинстве случаев довольно простым является рекурсивный
- 14. Давайте научимся решать следующую задачу : Дан массив из N различных чисел. Мы хотим узнать количество
- 15. Как перебирать все подмножества массива? Заметим, что все подмножества делятся на два типа : Те, в
- 16. Заведем вспомогательный массив used, который для каждого элемента хранит, будет ли он находится в нашем подмножестве.
- 17. Задача о расстановке ферзей Возьмем обычную шахматную доску и попробуем расставить на ней 8 ферзей так,
- 18. Давайте попробуем перебрать все возможные расстановки восьми ферзей рекурсивным перебором. Воспользуемся следующим переходом: выберем, в какую
- 20. Попытаемся оценить время работы. Мы выбираем, куда поставим первого ферзя – 64 варианта, потом второго –
- 21. Вот так изменится процедура find:
- 22. Прием, который позволяет уменьшить количество рассматриваемых вариантов в переборе, называется отсечением. Существует огромное количество разных по
- 23. Рекурсия очень требовательная к ресурсам компьютера, и писать её нужно аккуратно. Все что можно закодить рекурсией,
- 25. Скачать презентацию