Эксперт

Сергей

Задать вопрос

Мы готовы помочь Вам.

Цель работы: Ознакомиться с рекурсивными алгоритмами.
Краткие теоретические сведения
В ходе рекурсии метод вызывает сам себя. Если он делает это непосредственно, то рекурсия называется прямой, если через другой метод — косвенной. Она также может быть единичной (однократный вызов) либо множественной (вызов осуществляется несколько раз). На первый взгляд понятие кажется несколько сложным, поскольку человек не мыслит рекурсивно. Тем не менее есть задачи, которые рекурсивны по своей природе, а их структура
и решение легко отслеживаются с помощью алгоритма. Таковы, например, программы, выстраивающие деревья и проводящие по ним поиск. Однако не всегда это наилучший способ решения задач, в некоторых случаях он снижает производительность программы, в связи с чем необходимо рассмотреть еще и способы удаления рекурсии.
В следующих подразделах приводятся три рекурсивных алгоритма для расчета факториала, чисел Фибоначчи, а также решения задачи о ханойской башне. Они относительно просты, но раскрывают важные понятия. Некоторые алгоритмы используют рекурсию, чтобы создавать сложные графические изображения. И хотя код у них очень компактный, на самом деле они ничуть не проще базовых алгоритмов.
Кривая Коха — хороший пример самоподобного фрактала, где часть кривой напоминает ее общую форму. Построение таких фракталов начинается с инициатора — участка, определяющего основные очертания будущей фигуры. В ходе рекурсии все инициаторы или некоторые из них преобразуются (правильно масштабируются, поворачиваются и т. д.), превращаясь в своего рода генераторы, которые затем замещаются новыми версиями генераторов. Простейшая кривая Коха в качестве инициатора использует линию, которая на каждом уровне рекурсии разбивается на четыре части. Из них формируются три сегмента длиной в 1/3 от исходного отрезка. Первая и четвертая части находятся в направлении базовой линии, вторая поворачивается на –60°, третья — на 120° (рис. 9.4). На следующем уровне рекурсии программа заменяет каждый сегмент в генераторе новой копией генератора. Взглянув на рисунок 9.5, вы поймете, почему кривая называется самоподобной: ее часть выглядит как уменьшенная копия целой фигуры. Пусть pt1, pt2, pt3, pt4 и pt5 — точки, связанные с сегментами в генераторе. Начертим кривую Коха с помощью приведенного ниже псевдокода.
// Чертим кривую Коха заданной сложности, начиная с точки p1
// и прокладывая расстояние length в направлении angle.
DrawKoch(Integer: depth, Point: pt1, Float: angle, Float: length)
If (depth == 0) Then
<Чертим сегмент.>
Else
<Находим точки pt2, pt3, and pt4.>
// Рекурсивно чертим части кривой.
DrawKoch(depth — 1, pt1, angle, length / 3);
DrawKoch(depth — 1, pt2, angle — 60, length / 3);
DrawKoch(depth — 1, pt3, angle + 60, length / 3);
DrawKoch(depth — 1, pt4, angle, length / 3);
End If
End DrawKoch
Если depth = 0, то алгоритм чертит сегмент от точки p1 длиной length, следуя в направлении angle. (То как осуществляется рисование, зависит от используемой вами среды программирования.) При depth > 0 алгоритм определяет точки pt2, pt3 и pt4, а затем
выстраивает четыре сегмента длиною 1/3 от исходного отрезка: вначале он следует из точки pt1 в направлении angle до точки pt2, потом разворачивается на 60° влево и идет до точки pt3, совершает еще один поворот на 120° вправо (на угол, превышающий исходный на 60°) и двигается до точки pt4, и наконец, из нее, придерживаясь начального угла, преодолевает последнюю часть пути. Если глубина больше 0, то алгоритм рекурсивно вызывает себя четыре раза. Предположим, что T(N) — количество шагов, которые он совершает для глубины n, тогда T(N) = 4 _ T(N – 1) + C, где C — константа. Если проигнорировать последнюю, то T(N) = 4 _ T(N – 1), отсюда время работы — O(4N). Максимальная глубина рекурсии, необходимая для построения кривой Коха сложностью N, определяется только N и не должна вызывать проблем, ведь, как и в предыдущих алгоритмах (для нахождения чисел Фибоначчи и решения головоломки «Ханойская башня»), время работы возрастает невероятно быстро.
Если соединить края трех кривых Коха таким образом, чтобы их инициаторы образовывали треугольник, то получится так называемая снежинка Коха.
Порядок выполнения работы
1. Ознакомиться с теоретическими сведениями.
2. Получить вариант задания у преподавателя.
3. Выполнить задание: написать программу на языке С++.
4. Продемонстрировать выполнение работы преподавателю.
5. Оформить отчет.
6. Защитить лабораторную работу.
Требования к оформлению отчета
Отчет по лабораторной работе должен содержать следующие разделы:
титульный лист;
цель работы;
задание на лабораторную работу;
ход работы;
ответы на контрольные вопросы;
выводы по проделанной работе.

Варианты заданий
1. Напишите программу для решения головоломки «Ханойская башня» и покажите ходы, изобразив передвижения дисков между колышками.
2. Создайте программу для рисования снежинок Коха.
3. В стандартной снежинке Коха генератор создает углы, равные 60. Р но можно использовать и другие значения для получения интересных результатов. Напишите программу, которая разрешит пользователю задавать угол в качестве входного параметра.
4. Реализуйте программу для черчения кривых Гильберта.
5. Создайте программу, которая чертит кривые Серпинского.
6. Создайте программу, которая рисует ковер Серпинского.
7. Реализуйте программу для решения задачи о восьми ферзях.
8. Усовершенствуйте задачу о восьми ферзях: отследите, сколько ферзей может атаковать определенную позицию на доске.
9. Напишите программу, которая решает задачу о ходе коня методом возврата и в которой пользователю разрешается задавать размеры шахматной доски. Каковы будут наименьшие размеры доски, чтобы ход конем оказался возможен?
10. Используйте любимый язык программирования, чтобы решить задачу о ходе коня с использованием эвристического алгоритма Варнсдорфа.

Контрольные вопросы
1. Что такое рекурсия?
2. Какие есть способы удаления рекурсии, зачем это применяется?
3. Что такое алгоритмы с возвратом, приведите примеры?