# Содержание

Содержание;
LL-система или система Линденмайера;
Итерпретатор черепашьего языка;
A: Интерпретатор черепашьего языка;
Генерация управляющих команд;
B: Однозначное выведение;
C: Красивые картинки;
D: Снежинка Коха;
E: Кривая Минковского;
F: Интерпретатор черепашьего языка — 2;
G: Кривая дракона;
H: Салфетка Серпинского;
I: Кривая Госпера;
J: Кривая Гильберта;
K: Случайное выведение;
L: Растенье-подобная структура — 1;
M: Растенье-подобная структура — 2;

# LL-система или система Линденмайера

LL-система или система Линденмайера — это система последовательного переписывания команд. LL-система состоит

LL-системы предложил и развивал в 1968 Аристид Линденмайер, венгерский биолог и ботаник из Утрехтского университета. Линденмайер использовал LL-системы для описания поведения клеток растений и моделирования процесса развития растения. LL-системы использовались также для моделирования морфологии различных организмов и могут быть использованы для генерации самоподобных фракталов. Ниже примеры растений, полученные при помощи LL-систем.

# Итерпретатор черепашьего языка

Эта часть отвечает за механизм перевода строки в геометрические структуры.

В предыдущий раз мы писали рекурсивные функции, порождающие те или иные фрактальные (самоподобные) структуры. Можно пойти дальше и описать язык, порождающий последовательности команд управления черепашкой. Теперь надо написать только одну функцию-интерпретатор, переводящую предложения нашего языка на язык команд черепашки. А разные фракталы — это просто разные предложения на описанном нами языке.

Состояние черепашки описывается тройкой (x,y,α)(x, y, \alpha), где xx, yy — декартовы координаты черепашки, а α\alpha — угол (в градусах, отсчитываемый от положительного направления оси OxOx), в направлении которого черепашка движется (см. t.pos(), t.heading() и их set-варианты).

Теперь опишем команды в нашем новом фрактально-черепашьем языке. Зафиксируем два числа: dd — величина шага и δ\delta — величина изменения угла черепашки. Тогда в нашем языке пока будут только следующие 4 команды:
F — сделать шаг длины dd в направлении угла α\alpha и нарисовать соответствующий отрезок (forward). При этом состояние из (x,y,α)(x, y, \alpha) переходит в (x′,y′,α)(x', y', \alpha), где x′=x+d⋅cos⁡α x' = x + d\cdot\cos\alpha, y′=y+d⋅sin⁡αy' = y + d\cdot\sin\alpha;
f — всё то же самое, но отрезок не рисуется;
+ — повернуть налево на угол δ\delta. Состояние черепашки меняется на (x,y,α+δ)(x, y, \alpha+\delta). Поворот на положительный угол происходит против часовой стрелки;
- — повернуть направо на угол δ\delta. Состояние черепашки меняется на (x,y,α−δ)(x, y, \alpha-\delta).

A: Интерпретатор черепашьего языка

Напишите функцию interpret, принимающую на вход фиксированную величину dd, угол δ\delta, а также строку, состоящую из команд Ff+- без пробелов. Функция должна проинтерпретировать программу черепашки в соответствии с языком, описанным выше.

100 90 F+F+F+F
100 45 F+F--F+F
50 30 FF+++f---FF+++f---FF

# Генерация управляющих команд

Для порождения строк, управляющих черепашкой можно воспользоваться следующей универсальной конструкцией. Пусть VV — некоторый алфавит, то есть просто формальное множество букв. Например, алфавитом может быть наш набор команд: V={F,f,+,−}V = \{F, f, +, -\}. Возьмём непустое слово ω\omega в этом алфавите (то есть просто последовательность букв), которое мы будем называть аксиомой, axiom. И наконец возьмём набор пар PP вида (буква, соответстующее_ему_слово), которые называются продукциями, productions. Будем записывать продукции в виде a→μa \to \mu. При этом требуется, чтобы для каждой буквы aa была хотя бы одна продукция a→μa \to \mu. Обычно PP записывают в виде небольшого списка продукций, подразумевая, что для всех остальных букв задана продукция a→aa \to a. Тройка G=(V,ω,P)G=(V,\omega,P) называется LL-системой (или системой Линденмайера).

Идём дальше, у нас задана LL-система G=(V,ω,P)G=(V,\omega,P). Говорят, что слово ν\nu напрямую выводится (derive) из слова μ=a1a2…an\mu=a_1a_2\ldots a_n (и записывается μ⇒ν\mu \Rightarrow \nu), если слово ν\nu получается из слова μ\mu заменой каждой буквы aia_i на какую-нибудь из продукций ai→…a_i \to \ldots. И наконец, слово ν\nu порождается LL-системой GG, если его можно вывести из начальной аксиомы ω\omega за несколько шагов.

Заметим, что если не существует двух различных продукций вида a→μ1a\to\mu_1 и a→μ2a\to\mu_2, то LL-система порождает просто последовательность слов, которые последовательно получаются из аксиомы. В питоне такие продукции удобно задавать с помощью словаря P, из которого выводимое слово «добывается» при помощи команды вида P.get(a, a).

Так, сложные определения в сторону, рассмотрим примеры. В качестве алфавита будут выступать команды черепашьего языка: V={F,f,+,−}V = \{F, f, +, -\}. Возьмём ω=\omega=F, и единственную нетривиальную продукцию F→\toFF. Такая LL-система порождает только скучный набор слов F, FF, FFFF и так далее. Возьмём другую продукцию F→\toF+F. Эта LL-система порождает последовательность слов F, F+F, F+F+F+F и так далее.

Самое время добавить магии :) Возьмём продукцию F→\toF+F-, d=50d=50 и δ=90\delta=90 и проинтерпретируем последовательность, порождаемую LL-системой нашей черепашкой. Вот что получится (где-то вы эту кривую уже видели, да?):
F

F+F-

F+F-+F+F--

F+F-+F+F--+F+F-+F+F---

F+F-+F+F--+F+F-+F+F---+F+F-+F+F--+F+F-+F+F----

F+F-+F+F--+F+F-+F+F---+F+F-+F+F--+F+F-+F+F----+F+F-+F+F--+F+F-+F+F---+F+F-+F+F--+F+F-+F+F-----

Больше магии! Возьмём ω=\omega=F-F-F-F, и единственную нетривиальную продукцию F→\toF-F+F+FF-F-F+F. Возьмём d=50d=50 и δ=90\delta=90 и проинтерпретируем нашей черепашкой последовательность слов, порождаемых LL-системой.
pict

B: Однозначное выведение

Напишите функцию derive, принимающую на вход словарь продукций, а также слово, и возвращающую слово, которое из него выводится. При этом для каждой буквы aa, не встречающейся в словаре продукций, мы считаем, что a→aa\to a.

Формат ввода. В первой строке даётся целое число N — количество продукций. В следующих N строках даются продукции в формате a word, где a — буква, а word — выводимое слово (которое может не быть словом в обычном понимании). Гарантируется, что буквы в продукциях не повторяются. Затем идёт число M — число тестов. В следующих M строках идут слова, для каждого из которых нужно вывести следующее.

1 F F+F- 3 F Hello, world! FF+abc+FF--
F+F- Hello, world! F+F-F+F-+abc+F+F-F+F---
3 A hello B world o (o was here) 4 A B hello world BA IS REALLY COOL! BATTERY INCLUDED
hello world hell(o was here) w(o was here)rld worldhello IS REhelloLLY COOL! worldhelloTTERY INCLUDED
3 a bc b ca c ab 2 abbcccbba bccacaabababcacabc
bccacaabababcacabc caababbcabbcbccabccabccaabbcabbccaab

C: Красивые картинки

Для каждого из следующих наборов (число nn, величины dd и δ\delta, а также LL-система) нарисуйте черепашкой картинку, которая получается после nn выведений из аксиомы.

n=3n=3, d=5d=5, δ=90\delta=90; ω=\omega=F-F-F-F; P={P=\{F→\toF-F+F+FF-F-F+F }\}

n=4n=4, d=5d=5, δ=90\delta=90; ω=\omega=-F; P={P=\{F→\toF+F-F-F+F }\}

n=4n=4, d=3d=3, δ=90\delta=90; ω=\omega=F-F-F-F; P={P=\{F→\toFF-F--F-F }\}

n=4n=4, d=3d=3, δ=90\delta=90; ω=\omega=F-F-F-F; P={P=\{F→\toFF-F-F-F-F-F+F }\}

n=2n=2, d=5d=5, δ=90\delta=90; ω=\omega=F+F+F+F; P={P=\{F→\toF+f-FF+F+FF+Ff+FF-f+FF-F-FF-Ff-FFF, f→\toffffff }\}

Картинки нужно построить последовательно, выполняя turtle.resetscreen() между рисунками.

D: Снежинка Коха

Реализуйте при помощи LL-системы снежинку Коха.

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.

Картинки с примерами
0
1
5

E: Кривая Минковского

Реализуйте при помощи LL-системы снежинку кривую Минковского.

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.

Картинки с примерами
0
1
2
3

F: Интерпретатор черепашьего языка — 2

Для того, чтобы расширить возможности по генерации самоподобных картинок при помощи LL-систем добавим в интерпретатор черепашки дополнительные синонимы. Команды L и R должны работать так же, как и команда F, а команды l и r — аналогично команде f.

Добавим ещё две команды в черепаший язык — квадратные скобки [ и ]. Они должны интерпретироваться следующим образом:
[ — сохранить текущее состояние черепашки (x,y,α)(x, y, \alpha) в стек;
] — вынуть с верхушки стека запомненное ранее состояние и сделать его текущим.

Добавьте эти новые возможности в функцию interpret.

100 90 F+L+R+F
50 30 RF+++l---FF+++r---LF
50 90 FF[+FF-F][-FF+F]FF

G: Кривая дракона

Оказывается, кривую дракона очень легко построить, используя подобную технику. Нужно взять δ=90\delta=90; ω=\omega=L; P={P=\{L→\to..., R→\to...}\} Восстановите многоточия и постройте кривую Дракона.

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.
Ориентация кривой важна, первый поворот — налево.

Картинки с примерами
0
1
2
3
4
5
10
18

H: Салфетка Серпинского

Используя два вида продукций (для L и R), придумайте правила вывода “салфетки Серпинского”. Угол поворота равен 60 градусов. Первые 5 итераций на рисунке ниже:

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.

I: Кривая Госпера

Используя два вида продукций (для L и R), придумайте правила вывода кривой Госпера. Угол поворота равен 60 градусов. Первые 4 итерации на рисунке ниже:

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.
Ориентация кривой важна, первый поворот — направо.

J: Кривая Гильберта

Кривая Гильберта — это непрерывная кривая, заполняющая целиком квадрат. На первой картинке кривые Гильберта, с первого по четвёртый шаги. В пределе получается кривая, которая заполняет квадрат целиком! Впрочем первую такую кривую придумал в 1890 году (годом ранее) итальянский математик Джузеппе Пеано.

Для рисования кривой Гильберта пригодятся буквы, которые никак не интерпретируются черепашкой. Например, A и B. Придумайте правила вывода кривой Гильберта, используя два вида продукций — для A и B.

На вход даётся неотрицательное число nn. Постройте кривую «степени» nn.

K: Случайное выведение

Можно отказаться от детерминированности правил вывода и добавить в этот процесс случайность. Рассмотрим LL-систему, в которой для одной и той же буквы есть несколько продукций a→μ1,a→μ2,…a\to\mu_1, a\to\mu_2, \ldots. Тогда при выведении букву aa мы будем заменять на случайно выбранное слово из μ1,μ2,…\mu_1, \mu_2, \ldots. Для этого можно использовать random.choice.

Формат ввода. В первой строке даётся целое число N — количество продукций. В следующих N строках даются продукции в формате a word, где a — буква, а word — выводимое слово (которое может не быть словом в обычном понимании). Затем идёт число M — число тестов. В следующих M строках идут слова, для каждого из которых нужно вывести следующее.

Обратите внимание, что ответ носит случайный характер и может не совпадать с примером.

3 F FF F -1- F =2= 4 F,F F,F F,F F,F
FF,-1- =2=,-1- =2=,FF -1-,-1-

L: Растенье-подобная структура — 1

Для данного nn нарисуйте черепашкой картинку, которая получается после nn выведений из аксиомы. Перед началом рисования поверните черепашку «головой» вверх.

δ=20\delta=20; ω=\omega=F; P={P=\{F→\toF[+F]F[-F][F] }\}

M: Растенье-подобная структура — 2

Для данного nn нарисуйте черепашкой картинку, которая получается после nn выведений из аксиомы. Ниже приведён пример запуска одной и той же программы с указанными правилами.

δ=25.7\delta=25.7; ω=\omega=F; P={P=\{F→\toF[+F]F[-F][F], F→\toF[+F]F, F→\toF[-F]F }\}