Оглавление
Задание
Формализация задачи
Схема алгоритма
Текст программы
Возможно вы искали - Реферат: Исследование посещаемости WEB сайта
Руководство пользователя
Тест программы
Литература
Задание
Оригинальный узор на рисунке 1 состоит из суперпозиции четырех кривых. Эти кривые соответствуют некоторому регулярному образу. Алгоритм для построения этих кривых на экране монитора или на графопостроителе под управлением вычислительной машины описан в [1].
Похожий материал - Реферат: Классификация средств вычислительной техники
Задача проекта – реализовать этот алгоритм в виде программы на функциональном языке программирования Lisp.
Рисунок 1
Анализируя рисунок 1, можно обнаружить, что он получен путем наложения друг на друга нескольких кривых. Первые две из них показаны на рисунке 2. Кривая Si называется кривой Серпинского i -го порядка. Необходимо выяснить, какова рекурсивная схема этих кривых.
Рисунок 2
Главная особенность кривой Серпинского состоит в том, что она замкнута и в ней нет пересечений. Это означает, что основная рекурсивная схема должна давать разомкнутую кривую линию, четыре части которой соединяются линиями, не принадлежащими самому рекурсивному образу. И действительно, эти замыкающие линии представляют собой отрезки прямых в четырех внешних углах, на рисунке 2 они выделены жирными линиями. Можно считать, что они принадлежат к непустой начальной кривой S – квадрату, “стоящему” на одном углу. Теперь достаточно легко составить рекурсивную схему.
Четыре составляющих образа, для наглядности, обозначим через A , B , C , D , а процедуры, рисующие соединительные прямые, будем обозначать стрелками, указывающими соответствующем направлении. Надо отметить, что четыре рекурсивных образа по существу идентичны, но лишь повертываются на 90°.
Основной образ кривых Серпинского задается схемой:
S: A -B -C -D -
Очень интересно - Реферат: Информационные технологии как инструмент повышения конкурентоспособности торгового предприятия
а рекурсивные составляющие (горизонтальные и вертикальные отрезки – двойной длины):
A: A - B - D - A
B: B - C - A - B
C: C - D - B - C
D: D - A - C - D
Предположим, что для построения части прямой в нашем распоряжении есть процедура Line , передвигающая перо в заданном направлении на заданное расстояние, причем направление задается целочисленным параметром i , как 
градусов. Если единичную прямую обозначить через h , то с помощью рекурсивных обращений к аналогично составленным процедурам для B и D и к самой A довольно просто написать процедуру, соответствующую схеме А .
( defun A ( k )
( cond ( ( > k 0 )
( A ( - k 1 ) ) ( Line 1 h )
Вам будет интересно - Реферат: Информационные технологии как инструмент повышения конкурентоспособности торгового предприятия
( B ( - k 1 ) ) ( Line 0 ( * 2 h ) )
( D ( - k 1 ) ) ( Line 7 h )
( A ( - k 1 ) ))))
Эта процедура инициируется главной программой по одному разу для каждой кривой Серпинского, образующих приведенный рисунок. Употребление явного параметра для уровня гарантирует окончание работы, так как глубина рекурсии не может быть больше k . Главная программа строится по образцу S . Ее задача - установить начальную точку кривой, т.е. исходные координаты пера (Px и Py ) и единичную длину приращения h . Квадрат, где рисуется кривая, помещается в середине экрана, заданной ширины и высоты.
Графическое изображение полученного алгоритма представлено в следующем разделе (Рисунок 3).
Похожий материал - Реферат: Использование электронной почты
По сравнению с таким рекурсивным построением эквивалентные программы, где избегали употребления рекурсии, выглядят крайне сложными и запутанными.
Схема алгоритма
Рисунок 3 Схема алгоритма главной процедуры
Рисунок 4 Схема алгоритма процедуры A[1]
Текст программы
;; SIERPINS.LSP для XLISP версии 2.1