Фрактальное дерево
Я хочу показать вам еще один пример использования рекурсии для генерации фрактальных изображений.
Существует множество фракталов, называемых фрактальными деревьями.
Проиллюстрируем идею фрактального дерева с помощью следующей диаграммы.
Изображение начинается со ствола дерева, к нему могут быть добавлены ветви.
Ветви добавляются симметрично на определенный угол, равностоящий от текущей ветви.
Новые ветви добавляются сокращенной длины.
Ветви дерева могут иметь такой же цвет или различные цвета.
Таким образом, любая часть дерева, начинающаяся от ветви, похожа на другие ветви.
Такое самоподобие дает фрактальное дерево.
Давайте посмотрим программу, реализующую фрактальное дерево.
Класс называется FractalTree который расширяет JFrame.
Конструктор здесь настраивает JFrame.
Основная задача программы делается этим методом drawFractalTree.
Первый параметр является объектом класса Graphics.
Graphics является абстрактным классом для всех графических объектов, отображаемых графическими компонентами, x1 и y1 дают начальное положение ветви, которая рисуется, angle это угол отклонения от текущей ветви, level это текущий уровень рекурсии.
Здесь есть не рекурсивный шаг, который ничего не делает, когда уровень меньше или равен 0.
Два выражения здесь определяют конечную точку для новой ветви, которая составляет угол от текущей ветви.
Метод setLineColor задает цвет на разных уровнях.
Метод drawLine будет рисовать линию в JFrame.
Ниже главная часть программы, которая делает рекурсивные вызовы drawFractalTree.
Два вызова будут сделаны с углами, равностоящими от текущей ветви.
Уровень уменьшается на единицу, так что не рекурсивный шаг будет выполнен, когда уровень в конце концов уменьшится до нуля.
Метод drawFractalTree вызывается здесь с начальной позицией, угол -90 создаст ствол, который растет прямо вверх, максимальный уровень установлен на 9.
Давайте посмотрим на выполнение программы по созданию экземпляра фрактального дерева.
Вы можете видеть, что это дерево, как структура с ветвями, симметричными от текущей ветви.
Вы на самом деле можете создать больше ветвей, сделав дополнительные рекурсивные вызовы метода drawFractalTree.
Например, здесь добавлена дополнительная ветвь, которая растет прямо из текущей ветви.
Программа запускается, путем создания нового экземпляра FractalTree.
Далее в задаче, вы должны изменить программу, так что четыре ветви будут генерироваться из каждой ветви.
Вопросы
Задача
Учитывая метод f1() ниже, что возвращает метод f1(4)?
public static int f1(int n) {
if (n == 1)
return 1;
return n + f1(n – 1);
}
Варианты ответа:
1. 13
2. 1
3. 10
4. 7
Ответ: 3.
Объяснение.
Рекурсивный метод f1() вычисляет сумму от 1 до входного параметра n, для любого натурального n. Таким образом, f1(4) дает результат 1 + 2 + 3 + 4 = 10.
Задача
Учитывая метод f2() ниже, что возвращает метод f2(3, 2)?
public static int f2(int a, int b) {
if (b >= 1)
return f2(a + 1, b – 1);
else
return a;
}
Варианты ответа:
1. 3
2. 5
3. Ошибка – бесконечный цикл
4. 2
Ответ: 2.
Объяснение.
Рекурсивный метод f2() принимает два целочисленных параметра а и b. В каждом рекурсивном вызове, если b больше 0, а увеличивается на 1, пока b уменьшается на 1. Рекурсивный вызов продолжается до тех пор пока b не равен 0. Таким образом, величина b добавляется к а этим рекурсивным методом. Величина а возвращается методом в конце. Таким образом, f2(3, 2) возвращает значение 3 + 2 = 5.
Задача
Учитывая метод f3() ниже, что возвращает метод f3(10200)?
public static int f3(int n) {
if (n == 0)
return 1;
else if (n < 10 && n > -10)
return 0;
else
return f3(n / 10) + f3(n % 10);
}
Варианты ответа:
1. 10200
2. 3
3. 12
4. 0
Ответ: 2.
Объяснение.
Рекурсивный метод f3() определяет количество нулей в заданном целом. Если входной параметр равен 0, то возвращается 1. Если входной параметр превышает -10 и меньше 10, то метод возвращает 0. В противном случае, он возвращает сумму результатов рекурсивного вызова для числа n с последней удаленной цифрой и рекурсивным вызовом для последней цифры. Таким образом, f3(10200) возвращает значение 3.
Задача
Теперь, когда вы узнали о рекурсии, каким будет вывод для каждого из рекурсивного метода ниже с данным входом?
Рекурсивный метод 1
int f1(int n) {
if (n > 1)
return f1(n – 1) + f1(n – 2);
else
return 1;
}
f1(3) = ?
Рекурсивный метод 2
int f2(int a, int b) {
if (b == 0)
return 1;
else
return a * f2(a, b – 1);
}
f2(2, 3) = ?
Рекурсивный метод 3
String f3(String s, int length) {
if (length == 0)
return "";
return s.charAt(length – 1) + f3(s, length – 1);
}
f3("tsukh", 5) = ?
Рекурсивный метод 4
String f4(int n) {
if (n == 0) return "0";
if (n == 1) return "1";
return f4(n / 2) + (n % 2);
}
f4(13) = ?
Рекурсивный метод 5
String f5(int n) {
if (n == 0) return "0";
return n + f5(n – 1) + n;
}
f5(3) = ?
Ответ:
Задача
В этом упражнении вы должны изменить рекурсивный метод drawFractalTree() в классе TreePanel, так что фрактальное дерево с четырьмя ветвями в каждом узле будет изображено.
Инструкции:
1. Запустить программу, создать новый экземпляр FractalTree.
2. Текущая реализация метода drawFractalTree() рисует дерево с тремя ветвями в каждом узле, ориентированными на 20 градусов, 0 градусов и -20 градусов по отношению к узлу, используя три рекурсивных вызова.
3. Изменить реализацию метода таким образом, что он рисует дерево с четырьмя ветвями в каждом узле, ориентированными под углом 30 градусов, 15 градусов, -15 градусов и -30 градусов по отношению к узлу, используя четыре рекурсивных вызова.
4. Вам нужно будет изменить четвертый параметр для каждого из четырех рекурсивных вызовов метода drawFractalTree(), чтобы выполнить эту задачу.
Пример вывода:
Ответ:
drawFractalTree(g, x2, y2, angle – 15, level – 1);
drawFractalTree(g, x2, y2, angle + 15, level – 1);
drawFractalTree(g, x2, y2, angle – 30, level – 1);
drawFractalTree(g, x2, y2, angle + 30, level – 1);
