Берем равносторонний треугольник со стороной r. На первом шаге вырезаем в центре него перевернутый вершиной вниз равносторонний треугольник с длиной стороны r1 = r0/2. В результате этого шага у нас получаются три равносторонних треугольника с длинами сторон r1 = r0/2, располагающиеся в вершинах исходного треугольника.
На втором шаге в каждом из трех образовавшихся треугольников вырезаем перевернутые вписанные треугольники с длиной стороны r2 = r1/2 = r0/4. Результат — 9 треугольников с длиной стороны r2 = г/4.
Продолжаем повторять эту операцию, на любом n-м шаге в каждом из имеющихся треугольников вырезая перевернутый треугольник со стороной гn = г0/2n = r02-n.
В результате форма «салфетки Серпинского» постепенно становится все более и более определенной.
Алгебраический алгоритм
Поместим равносторонний треугольник с длиной стороны, равной 1, на комплексную плоскость = х + iу (левый треугольник на рисунке). Пусть у нас имеются три оператора t1, t2, t3, каждый из которых переводит исходный равносторонний треугольник в подобный ему, но в два раза меньшего размера.
Применение операторов t1, t2, t3 приводит к тому, что мы получаем треугольник, подобный исходному, но меньшего размера и строго определенного положения по отношению к исходному треугольнику, как показано на рисунке.
Многократное повторение этих операторов позволяет построить «салфетку Серпинского».
Привлекательность этого метода в том, что операторы t1, t2, t3 можно выразить алгебраическими формулами, приведенными в таблице, и запрограммировать.
Здесь реализуется кумулятивная фиксация образа, то есть накопительное пошаговое формирование его так, что фрагмент n-го шага накладывается на образ n-1 шага.
Метод FASS-линии
Данный метод позволяет построить фрактал Серпинского при помощи алгоритма построения так называемых FASS-кривых. Название происходит от английского описания подобных кривых: «space-Filling, self-Avoiding, Simple and self-Similar», что означает «кривые, заполняющие собой всю плоскость, без самопересечений, состоящие из простых и самоподобных фрагментов». Пошаговое построение FASS-линии при многократном повторении может произвести фрактал Серпинского.
Конечно, при фиксации образа последующего шага все предыдущие построения «стираются».
Метод L-систем
Метод L-систем был изобретен в 1968 году не математиком, а венгерским биологом Аристидом Линденмайером, разработавшим метод описания сложных природных систем и процессов с помощью простых составляющих и правил их преобразования.
Линденмайер использовал формальную грамматику, опирающуюся на правила генерации преобразования символов. L-система позволяет получить сложную форму при помощи аксиомы и правил преобразования. Результат этого процесса детерминирован, то есть строго и однозначно определен алгоритмом построения. Однако проблемой метода в общем смысле является то, что предсказать конечный результат невозможно до тех пор, пока алгоритм не будет завершен полностью. При этом каждый шаг вызывает удлинение командной строки, а значит, на ее обработку требуется все больше и больше времени, так что даже для современных компьютеров этот процесс достаточно долог, а в далеком 1968 году на решение задачи потребовалась бы почти вечность.
Рассмотрим алгоритм построения «салфетки Серпинско- го» методом L-систем немного подробнее.
Аксиомой этого процесса служит выражение: FXF — — FF — — FF. Имеются также три правила:
Нулевой шаг процесса имеет вид: FXF — — FF — — FF. Уже первый шаг имеет довольно длинную запись:
О длине записи на десятом или двадцатом шаге даже говорить не приходится. Впрочем, для вычислительной машины это не проблема. Заметим, что, в отличие от предыдущего алгоритма, при фиксации следующего шага все предыдущие построения не стираются. Поскольку фрактальные алгоритмы сводятся к повтору установленных правил, общей идеей для их вычислений будет организация цикла, в котором по завершении последней операции программа будет возвращаться к исходной операции. Эта операциональная петля не возвращает нас к начальной точке, но каждый раз переопределяет начальные условия. Начальные условия обновляются на каждом такте цикла построения фрактала, и это всякий раз приводит к новому результату в конце цикла. Промежуточные результаты могут «стираться», но могут и накапливаться. Команда «стирать» или «сохранить» — последняя команда в цикле построения фрактала.