Получить кривую дракона порядка n

Кривые дракона, показанные могут быть построены с помощью следующего рекуррентного метода. Каждой кривой ставится в соответствие последовательность, состоящая из нулей и единиц (будем называть ее двоичной формулой), где единица соответствует повороту кривой налево, а нуль – повороту направо. Кривая дракона первого порядка имеет двоичную формулу 1 (рис. a). Для того чтобы получить двоичную формулу кривой дракона каждого следующего порядка, следует приписать справа к формуле кривой предыдущего порядка единицу. Полученная последовательность дает половину искомой формулы. Затем в последовательности цифр, предшествующих приписанной единице, следует заменить на нуль единицу, стоящую в ее середине, после чего приписать полученную последовательность справа от уже построенной части формулы. На рис. б показана кривая дракона второго порядка, которой соответствует двоичная формула 110, а на рис. в - кривая дракона третьего порядка - ей соответствует двоичная формула 1101100. Кривые строятся от хвоста к голове дракона и повернуты так, чтобы драконы «плыли» направо, а пасть и кончик хвоста касались «поверхности воды». Прямые углы обычно скругляются дугой окружности или срезаются (показано на рисунках штриховой линией) для того, чтобы вершины углов не соприкасались, и не создавалась иллюзия самопересечения кривой. Дано натуральное n. Получить кривую дракона порядка n.

Миниатюры

 

0