Если вы когда-нибудь сталкивались с фракталами, то наверняка слышали о салфетке Серпинского. Это поразительное математическое создание, которое выглядит сложным, но его можно довольно просто сгенерировать с помощью рекурсивных функций на языке программирования Python. В этой статье мы разберем, как это сделать, научимся задавать глубину фрактала, оценим глубину рекурсии и построим таблицу зависимости времени построения от глубины фрактала. Готовы погрузиться в мир фракталов? Давайте начнем!
Что такое Салфетка Серпинского?
Салфетка Серпинского, также известная как треугольник Серпинского, — это фрактал, который формируется путем рекурсивного удаления центральных частей треугольника. Этот процесс продолжается бесконечно, создавая потрясающе сложную структуру из простых элементов. Это идеальный пример того, как простые правила могут порождать сложные и красивые узоры.
Основы рекурсивных функций
Рекурсия — это техника программирования, когда функция вызывает саму себя. В контексте создания фракталов это очень удобно, так как мы можем определить простое правило для создания фрактала и применить его многократно. Давайте рассмотрим базовую структуру рекурсивной функции на Python:
def rekursivnaya_funkciya(parametry):
if bazovyj_sluchaj:
return rezultat
else:
rekursivnaya_funkciya(novye_parametry)Эта функция состоит из двух частей: базового случая и рекурсивного вызова. Базовый случай определяет, когда функция должна остановиться, чтобы избежать бесконечной рекурсии. В случае салфетки Серпинского, базовый случай будет достигнут, когда мы достигнем заданной глубины рекурсии.
Генерация Салфетки Серпинского
Шаг 1: Определение базовой структуры
Начнем с написания функции, которая будет рисовать треугольник. Мы будем использовать matplotlib для этого:
import matplotlib.pyplot as plt
import numpy as np
def risovat_treugolnik(ax, vershiny, cvet):
treugolnik = plt.Polygon(vershiny, edgecolor='k', facecolor=cvet)
ax.add_patch(treugolnik)Здесь ax — это оси графика, вершины — координаты вершин треугольника, а цвет — цвет заливки треугольника.
Шаг 2: Реализация рекурсивной функции
Теперь мы напишем функцию, которая будет рекурсивно создавать треугольники:
def salfetka_serpinskogo(ax, vershiny, glubina):
cvet = 'white' if glubina == 0 else 'black'
risovat_treugolnik(ax, vershiny, cvet)
if glubina > 0:
vershiny = np.array(vershiny)
mid01 = (vershiny[0] + vershiny[1]) / 2
mid12 = (vershiny[1] + vershiny[2]) / 2
mid20 = (vershiny[2] + vershiny[0]) / 2
salfetka_serpinskogo(ax, [vershiny[0], mid01, mid20], glubina - 1)
salfetka_serpinskogo(ax, [vershiny[1], mid12, mid01], glubina - 1)
salfetka_serpinskogo(ax, [vershiny[2], mid20, mid12], glubina - 1)В этой функции мы сначала рисуем треугольник, затем проверяем, достигли ли мы базового случая (глубина равна нулю). Если нет, вычисляем средние точки сторон треугольника и рекурсивно вызываем функцию для каждого из трех новых треугольников.
Шаг 3: Визуализация фрактала
Теперь осталось вызвать нашу функцию и визуализировать результат:
def osnovnaya_funkciya():
fig, ax = plt.subplots()
ax.set_aspect('equal')
ax.axis('off')
vershiny = [[0, 0], [1, 0], [0.5, np.sqrt(3)/2]]
glubina = 4
salfetka_serpinskogo(ax, vershiny, glubina)
plt.show()
osnovnaya_funkciya()Эта функция создает окно для рисования, задает начальные вершины треугольника и глубину рекурсии, а затем вызывает нашу рекурсивную функцию для создания салфетки Серпинского.
Добавление возможности задания глубины фрактала
Чтобы сделать нашу программу более гибкой, добавим возможность задания глубины фрактала пользователем:
def osnovnaya_funkciya():
fig, ax = plt.subplots()
ax.set_aspect('equal')
ax.axis('off')
vershiny = [[0, 0], [1, 0], [0.5, np.sqrt(3)/2]]
glubina = int(input("Vvedite glubinu fraktala: "))
salfetka_serpinskogo(ax, vershiny, glubina)
plt.show()
osnovnaya_funkciya()Теперь программа запросит у пользователя ввод глубины перед началом рисования фрактала.
Оценка глубины рекурсии
Глубина рекурсии — важный аспект, который нужно учитывать при работе с рекурсивными функциями, так как Python имеет ограничение на максимальную глубину рекурсии. Вы можете проверить текущий лимит с помощью:
import sys
print(sys.getrecursionlimit())По умолчанию этот лимит составляет 1000. Если вы хотите его изменить, можно использовать:
sys.setrecursionlimit(2000)Однако следует быть осторожным с увеличением лимита, так как это может привести к переполнению стека.
Таблица зависимости времени построения от глубины фрактала
Для оценки времени построения фрактала на разных уровнях глубины, мы можем использовать библиотеку time. Вот как это можно сделать:
import time
def izmerit_vremya(glubina):
fig, ax = plt.subplots()
ax.set_aspect('equal')
ax.axis('off')
vershiny = [[0, 0], [1, 0], [0.5, np.sqrt(3)/2]]
start_time = time.time()
salfetka_serpinskogo(ax, vershiny, glubina)
end_time = time.time()
return end_time - start_time
glubiny = range(1, 11)
vremena = [izmerit_vremya(glubina) for glubina in glubiny]
print("Glubina\tVremya (sek)")
for glubina, vremya in zip(glubiny, vremena):
print(f"{glubina}\t{vremya:.4f}")Этот код измеряет время, затраченное на построение фрактала для каждой глубины от 1 до 10, и выводит результаты в виде таблицы.
Мы рассмотрели процесс создания салфетки Серпинского с использованием рекурсивных функций на Python. Мы научились задавать глубину фрактала, оценивать глубину рекурсии и измерять время построения фрактала на разных уровнях глубины. Теперь вы можете экспериментировать с различными глубинами и наслаждаться красотой фракталов. Надеюсь, эта статья была полезной и вдохновила вас на дальнейшее изучение мира фракталов и рекурсивных алгоритмов.
Полный код программы
Для вашего удобства приведем полный код программы:
import matplotlib.pyplot as plt
import numpy as np
import time
def risovat_treugolnik(ax, vershiny, cvet):
treugolnik = plt.Polygon(vershiny, edgecolor='k', facecolor=cvet)
ax.add_patch(treugolnik)
def salfetka_serpinskogo(ax, vershiny, glubina):
cvet = 'white' if glubina == 0 else 'black'
risovat_treugolnik(ax, vershiny, cvet)
if glubina > 0:
vershiny = np.array(vershiny)
mid01 = (vershiny[0] + vershiny[1]) / 2
mid12 = (vershiny[1] + vershiny[2]) / 2
mid20 = (vershiny[2] + vershiny[0]) / 2
salfetka_serpinskogo(ax, [vershiny[0], mid01, mid20], glubina - 1)
salfetka_serpinskogo(ax, [vershiny[1], mid12, mid01], glubina - 1)
salfetka_serpinskogo(ax, [vershiny[2], mid20, mid12], glubina - 1)
def osnovnaya_funkciya():
fig, ax = plt.subplots()
ax.set_aspect('equal')
ax.axis('off')
vershiny = [[0, 0], [1, 0], [0.5, np.sqrt(3)/2]]
glubina = int(input("Vvedite glubinu fraktala: "))
salfetka_serpinskogo(ax, vershiny, glubina)
plt.show()
def izmerit_vremya(glubina):
fig, ax = plt.subplots()
ax.set_aspect('equal')
ax.axis('off')
vershiny = [[0, 0], [1, 0], [0.5, np.sqrt(3)/2]]
start_time = time.time()
salfetka_serpinskogo(ax, vershiny, glubina)
end_time = time.time()
return end_time - start_time
if __name__ == "__main__":
osnovnaya_funkciya()
glubiny = range(1, 11)
vremena = [izmerit_vremya(glubina) for glubina in glubiny]
print("Glubina\tVremya (sek)")
for glubina, vremya in zip(glubiny, vremena):
print(f"{glubina}\t{vremya:.4f}")Теперь вы вооружены всем необходимым для создания и анализа фракталов в Python. Удачи в ваших фрактальных приключениях!
Автор статьи:
Обновлено:
Добавить комментарий