Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №23/2008


В мир информатики
Школа программирования

Фрактал из окружностей

В статье о фракталах в этом выпуске газеты на рис. 8б показано красивое изображение. Если не закрашивать окружности, то это изображение будет выглядеть так, как на рис. 1.

 

Рис. 1

В данной статье мы опишем методику получения такого изображения. Но начнем мы с более простой картинки, представленной на рис. 2. Почему более простой — станет ясно ниже, а в чем отличие двух изображений, предлагаем читателям определить самостоятельно.

 

Рис. 2

Анализ рис. 2 показывает, что на нем изображена большая окружность, к которой с четырех сторон примыкают 4 меньшие окружности, каждой из которых также касаются еще 4 окружности меньшего размера и т.д. Если какую-то окружность условно назвать “планетой”, а примыкающие к ней — “спутниками”, то очевидно, что каждый спутник, в свою очередь, может рассматриваться как планета с соответствующими спутниками. Это наводит на мысль о возможности использования такого приема программирования, как рекурсия [1–2]. Поэтому если составить процедуру, с помощью которой можно изобразить на экране некоторую окружность-планету с рядом окружностей-спутников, а для рисования спутников использовать эту же процедуру, но с другими параметрами — координатами, радиусами и т.п. (то есть применить рекурсию), то можно получить требуемое изображение.

В приведенной ниже процедуре Окружности использованы следующие основные величины:

1) параметры процедуры:

х и у — координаты окружности-планеты;

радиус — ее радиус;

k — коэффициент уменьшения размера окружностей-спутников по отношению к размеру окружности-планеты;

n — величина, указывающая на “уровень” расположения спутников и одновременно — определяющая необходимость дальнейшего рекурсивного использования процедуры Окружности (напомним, что необходимо так оформлять процедуры (функции), чтобы рекурсивные вызовы осуществлялись по условию, которое когда-то станет ложным). В нашей процедуре величина n будет уменьшаться на 1, а в тело процедуры включено условие, что ее команды должны выполняться только при n > 0;

2) локальные переменные процедуры:

х1 и у1 — координаты окружности-спутника;

рад — радиус последней.

Итак, процедура Окружности на школьном алгоритмическом языке:

алг Окружности(арг цел x, y, радиус, n, вещ k)

нач цел i, x1, y1, рад

если n > 0 |Только в этом случае

то

|Рисуем окружность-"планету"

поз(x, y)

окружность(радиус)

|Рисуем окружности-"спутники"

|и для каждой из них

|рекурсивно вызываем

|процедуру Окружности

|Радиус спутников

рад := радиус * k

|Правая окружность-"спутник"

|Рассчитываем координаты ее центра

x1 := x + радиус + цел(рад)

y1 := y

|Рекурсивный вызов

Окружности(x1, y1, рад, n - 1, k)

|Нижняя

x1 := x

y1 := y + радиус + цел(рад)

Окружности(x1, y1, рад, n - 1, k)

|Левая

x1 := x - радиус - цел(рад)

y1 := y

Окружности(x1, y1, рад, n - 1, k)

|Верхняя

x1 := x

y1 := y – радиус - цел(рад)

Окружности(x1, y1, рад, n - 1, k)

все

 

кон

Напоминаем, что на экране координатная ось У направлена вниз.

Если вспомнить значения синуса и косинуса углов 90, 180, 270 и 360 градусов, то вместо четырех фрагментов, изображающих окружности-“спутники” (с последующим рекурсивным вызовом процедуры Окружности), можно применить оператор цикла с параметром, в котором для расчета координат использованы значения синуса и косинуса.

нц для i от 1 до 4

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

Окружности(x1, y1, рад, n - 1, k)

 

кц

Обратим внимание на то, что при i = 1 рисуется нижний “спутник”, при i = 2 — левый, при i = 3 — верхний, при i = 4 — правый (убедитесь в этом!). Это обстоятельство пригодится нам в будущем.

Основная часть программы в любом случае может быть оформлена так:

алг Фрактал_из_окружностей

 

нач цел радиус, n, вещ k

|Устанавливаем графический режим

|работы экрана

видео(17)

|Задаем начальное значение

|величины радиус

радиус := 50

|значение величины k

k := 0.5

n

n := 5

|Вызываем процедуру Окружности

|для рисования самой большой планеты

|и ее спутников

Окружности(цел(максX/2), цел(максY/2),

радиус, n, k)

 

кон

Примечания

1. Функции максХ и максУ в школьном алгоритмическом языке возвращают соответственно максимальное значение координат х и у в выбранном режиме работы экрана.

2. Функция цел возвращает целую часть ее вещественного аргумента.

А как же получить изображение, показанное на рис. 1? Можно увидеть, что оно отличается от рис. 2 тем, что “спутники”, расположенные внутри других окружностей-“планет”, не нарисованы. Чтобы добиться этого, сначала изменим нашу программу следующим образом.

Центральную (самую большую) окружность и ее четыре “спутника” будем получать отдельно, а только после этого для каждой из четырех окружностей будем рисовать ее “спутники”:

алг Фрактал_из_окружностей

 

нач цел радиус, n, вещ k

видео(17)

|Задаем начальное значение

|величины радиус

радиус := 50

|значение величины k

k := 0.5

n

n := 46

|Рисуем центральную окружность

поз(цел(максX/2), цел(максY/2))

окружность(радиус)

|и ее спутники

рад := радиус * k

нц для i от 1 до 4

x1 := цел(максX/2) +

цел((радиус + рад) *

cos(6.28/4 * i))

y1 := цел(максX/2) +

цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

|Для изображения новых "спутников"

|вызываем процедуру Спутники

Спутники(x1, y1, рад, n, k)

кц

 

кон

Видно, что появилась новая процедура — с именем Спутники. Она изображает четыре “спутника”, и для каждого из них происходит рекурсивное использование этой же процедуры:

алг Спутники(арг цел x, y, радиус, n, вещ k)

 

нач цел i, x1, y1, рад

если n > 0

то

|Определяем радиус "спутников"

рад := радиус * k

|Для каждого "спутника"

нц для i от 1 до 4

|Определяем его координаты

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

|Рисуем "спутник"

поз(x1, y1)

окружность(рад)

|Для изображения новых "спутников"

|рекурсивно вызываем эту же процедуру

Спутники(x1, y1, рад, n - 1)

кц

все

 

кон

Теперь мы уже можем получить изображение, показанное на рис. 1. Как уже отмечалось, на нем “спутники”, расположенные внутри других окружностей-“планет”, не нарисованы. Поскольку какие именно окружности-“спутники” не нужно рисовать, зависит от того, какой является окружность-“планета” (правой, левой, верхней или нижней), то введем в процедуру Спутники еще один параметр, определяющий эту особенность “планеты”. Дадим ему имя — номер (при номер = 1 “планета” — нижняя, при номер = 2 — левая, при номер = 3 — верхняя, при номер = 4 — правая; см. выше). В процедуре Спутники в зависимости от значения параметра номер некоторые окружности-“спутники” изображаться не должны:

алг Спутники(арг цел x, y, радиус, номер, n)

 

нач цел i, x1, y1, рад

если n > 0

то

рад := радиус * k

выбор |В зависимости от значения номер

при номер = 1:

|Не рисуется верхняя

|окружность-"спутник"

нц для i от 1 до 2

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

кц

i := 4

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

при номер = 2:

|Не рисуется правая окружность-"спутник"

нц для i от 1 до 3

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

кц

при номер = 3:

|Не рисуется нижняя

|окружность-"спутник"

нц для i от 2 до 4

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

кц

при номер = 4:

|Не рисуется левая

|окружность-"спутник"

нц для i от 3 до 4

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

кц

i := 1

x1 := x + цел((радиус + рад) *

cos(6.28/4 * i))

y1 := y + цел((радиус + рад) *

sin(6.28/4 * i))

поз(x1, y1)

окружность(рад)

Спутники(x1, y1, рад, i, n - 1)

все

все

кон

В основной части программы вызов процедуры Спутники должен быть оформлен с учетом изменения ее (процедуры) описания:

Спутники(x1, y1, рад, i, n)

Задание для самостоятельной работы

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

Литература

1. Рекурсия. / “В мир информатики” № 4–5 (“Информатика” № 36–37/2003).

2. Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. М.: БИНОМ. Лаборатория знаний, 2007.


6 Значение параметра n задается на 1 меньше, чем ранее, так как центральная окружность и ее “спутники” уже нарисованы.

TopList