Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

10:33p

Системы Линденмаера Для тех, кто не знает, что это такое: К примеру, кривая дракона с их помощью описывается вот так:
L=L+R
R=L-R
L0=F
R0=F
Есть набор стандартных символов - +(поворот по часовой стрелке),-(против),F(шаг вперед) и возможно некоторые другие (например, [ и ] - занести координаты в стек и обратно), с их помощью и с помощью друг друга рекурсивно определяются другие символы, и заданы символы нулевого порядка.
Например, кривая 3 порядка построится так:
L3=L2+R2=L1+R1+L1-R1=F+F+F-F+F+F-F-F.
Раздумываю над тем, как это можно реализовать с минимальными издержками на С/С++. Мне кажется (и кажется, что это было бы оптимальным вариантом), что подобную систему можно преобразовать в конечный автомат с количеством состояний порядка N*K*M, где N - желаемый порядок кривой, K - количество правил, M - среднее количество рекурсивных вызовов в правиле. Если не строить кривые диких порядков (для красивой картинки обычно хватает 10 :) ), то это вполне резонная цифра, соответствующая максимально занимаемому объему памяти в стеке при тупой реализации. Но кажется-то мне кажется, а вот как именно это сделать - за полтора часа не придумал :)
Пока что лучшее, что я придумал - хранить каждое правило в виде вектора пар (несколько вызовов, несколько примитивов), где вызовы - номера правил в таблице, примитивы - номера стандартных функций (+,-,F..). Тогда к примеру a=b+F-cde+b-F превратится в (b,+F-)(cde,+)(b,-F).
Это кажется уже довольно неплохо по издержкам, но без рекурсии, а следовательно и больших издержек из-за локальных переменных в стеке и т.п. все равно не обойтись. Хотя наверное проще вместо рекурсии сделать свой стек, но мне кажется, с конечным автоматом все равно получится лучше.
Идеи?