Канторово множество

Мы рассматриваем реализацию алгоритма генерации множества Кантора — фрактальной структуры, которая строится рекурсивным удалением центральных частей отрезков.

Введение

Множество Кантора — это фрактал, получаемый из единичного отрезка путём бесконечного удаления средней трети каждого оставшегося отрезка. На практике алгоритм можно ограничить определённым уровнем глубины рекурсии.

Зачем используется?

Алгоритм имеет образовательное значение и применяется в компьютерной графике для демонстрации рекурсии и фрактальных структур. Он также используется как простой пример фрактала и необычного множества в математике.

Основная часть

# Определение размеров поля: ширина 81 и высота 5
const width = 81;
const height = 5;

Здесь задаются константы — ширина и высота поля, на котором будет строиться изображение множества Кантора. Ширина выбрана как степень тройки (), чтобы процесс деления был целочисленным.

# Рекурсивная функция построения множества Кантора
# Принимает:
# - lines — массив символов (поле для рисования)
# - start — начальная позиция (индекс) в строке
# - len — длина текущего сегмента
# - idx — номер строки (уровень рекурсии)
function cantor!(lines, start, len, idx)
    # Делим отрезок на три части
    seg = div(len, 3)

    # Если длина сегмента больше нуля, продолжаем рекурсию
    if seg > 0
        # Очищаем среднюю треть отрезка во всех строках ниже текущей
        for i in idx+1:height, j in start + seg + 1 : start + seg * 2
            lines[i, j] = ' '  # заменяем символ решётки на пробел
        end

        # Рекурсивный вызов для левой и правой трети
        cantor!(lines, start, seg, idx + 1)
        cantor!(lines, start + 2 * seg, seg, idx + 1)
    end
end

cantor! (generic function with 1 method)

Это ключевая рекурсивная функция cantor!, которая строит множество Кантора. На каждом шаге она делит текущий отрезок на три части и очищает (заменяет на пробел) среднюю треть в строках ниже текущего уровня рекурсии. Процесс повторяется для левой и правой трети, пока сегмент не станет меньше 3 пикселей.

# Инициализируем весь массив символом '#'
lines = fill(UInt8('#'), height, width)

# Вызываем рекурсивную функцию, начинаем с самого верхнего уровня
cantor!(lines, 0, width, 1)

Создаём двумерный массив lines, заполненный символом # — это символ, которым обозначается оставшаяся часть множества. Вызов cantor!(lines, 0, width, 1) начинает процесс построения множества Кантора от начала строки (start=0), полной ширины (len=width) и первой строки (idx=1).

# Печать результата построчно
for i in 1:height, j in 1:width
    print(Char(lines[i, j]), j == width ? "\n" : "")
end

#################################################################################
###########################                           ###########################
#########         #########                           #########         #########
###   ###         ###   ###                           ###   ###         ###   ###
# #   # #         # #   # #                           # #   # #         # #   # #

Здесь происходит вывод результата. Мы проходим по каждому элементу массива lines, преобразуем числовые значения обратно в символы и печатаем их. По достижении конца строки (j == width) добавляется переход на новую строку.

Заключение

Мы рассмотрели реализацию классического фрактала — множества Кантора — с использованием языка программирования Julia. Нам удалось:

Построить фрактальную структуру рекурсивно.
Визуализировать результат в виде текстовой графики.
Ознакомиться с простым примером применения рекурсии и работы с двумерными массивами в Julia.

Это полезный пример для понимания рекурсии, фракталов и базовой компьютерной графики. Также он может быть расширен до более сложных визуализаций или интерактивных приложений.

Пример разработан с использованием материалов Rosetta Code

Канторово множество