Формализация задачи

Формализация задачи. Анализируя рисунок 1, можнообнаружить, что он получен путем наложения друг на друга нескольких кривых. Первые две из них показаны на рисунке 2. Кривая Si называется кривойСерпинского i-гопорядка. Необходимо выяснить, какова рекурсивная схема этих кривых. Рисунок 2Главная особенность кривойСерпинского состоит в том, что она замкнута и в ней нет пересечений. Этоозначает, что основная рекурсивная схема должна давать разомкнутую кривую линию, четыре части которой соединяютсялиниями, не принадлежащими самому рекурсивному образу.

И действительно, этизамыкающие линии представляют собой отрезки прямых в четырех внешних углах, нарисунке 2 они выделены жирными линиями.

Можно считать, что они принадлежат кнепустой начальной кривой S квадрату, стоящему на одном углу. Теперь достаточно легко составитьрекурсивную схему. Четыре составляющих образа, длянаглядности, обозначим через A,B, C, D, а процедуры, рисующиесоединительные прямые, будем обозначать стрелками, указывающими соответствующемнаправлении. Надо отметить, что четыре рекурсивных образа по существуидентичны, но лишь повертываются на 90 .Основной образ кривых Серпинскогозадается схемой S A B C D а рекурсивные составляющие горизонтальные ивертикальные отрезки двойной длины A A B D AB B C A BC C D B CD D A C DПредположим, что для построениячасти прямой в нашем распоряжении есть процедура Line, передвигающая перо взаданном направлении на заданное расстояние, причем направление задаетсяцелочисленным параметром i, как градусов.

Еслиединичную прямую обозначить через h, то с помощью рекурсивных обращений к аналогичносоставленным процедурам для Bи D и к самой A довольно простонаписать процедуру, соответствующую схеме А. defun A k cond gt 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 IERPINS.LSP дляXLISP версии 2.1 Программа построениякривых Серпинского i-го порядка. ЗАПУСК gt SierpinskiCurve 4 Замечание Переменная VMode управляет установкой видео режима, и по умолчанию установлена взначение 18. Эта установка соответствует режиму640x480 Color, и работает на большинстве систем.

Вслучае проблемы с установкой этого режиманеобходимо выбрать значение этой переменной всоответствии с документацией на оборудование. defvar VMode 18 Видео режим по умолчанию defvar MaxX 640 Максимальная ширина экрана по умолчанию defvar MaxY 480 Максимальная высота экрана поумолчанию defvar SquareSize 256 Размер области для построения Функция инициализируетграфический режим, устанавливает переменные MaxX InitGraph case VMode 4 320x200 Color mode 4 setq Max320 MaxY 200 SquareSize 128 16 640x350 Color mode 16 setq Max640 MaxY 350 SquareSize 128 18 640x480 Color mode 18 106 800x600 Color mode106 106 800 600 setq Max800 MaxY 600 SquareSize 512 t errorUnsupported graphics mode VMode Функция реализуетзадержку на заданное время defun pause time let fintime time internal-time-units-per-second get-internal-run-time loop when gt get-internal-run-time fintime return-from pause Функция целочисленного деления defun div a b round ab Функция рисованияпрямой Параметры lt Direction gt - направление рисования 0-7 lt Size gt - длинна прямой defun Line Direction Size setq x Px yPy caseDirection 0 setqx x Size 1 setqx x Size y - y Size 2 setqy - y Size 3 setqx - x Size y - y Size 4 setqx - x Size 5 setqx - x Size y y Size 6 setqy y Size 7 setqx x Size y y Size move Px Py xy setq Px x Pyy Функции A, B, C, D -рекурсивные функции рисования defun A k cond gt k 0 A - k 1 Line 1 h B - k 1 Line 0 2 h D - k 1 Line 7 h A - k 1 defun B k cond gt k 0 B - k 1 Line 3 h C - k 1 Line 2 2 h A - k 1 Line 1 h B - k 1 defun C k cond gt k 0 C - k 1 Line 5 h D - k 1 Line 4 2 h B - k 1 Line 3 h C - k 1 defun D k cond gt k 0 D - k 1 Line 7 h A - k 1 Line 6 2 h C - k 1 Line 5 h D - k 1 InitGraph Установка графического режима setq h div SquareSize 4 Вычисление длины линии setq x0 div Max2 Вычисление начальной точки setq y0 div MaxY 2 h для рисования Основнойцикл do i 1 Инициализациясчетчика eql i Count 1 Done Условие завершения setq x0 - x0 h Вычисление координат начальной setq h div h 2 точки для рисования и setq y0 y0 h единичной длины линии setq Px x0 Py y0 Установка пера color i Установка цвета длярисования A i Line 1 h Рисование B i Line 3 h C i Line 5 h D i Line 7 h pause 1.0 Задержка setq i i 1 Инкримент счетчика Конецосновного цикла print Try SierpinskiCurve 4 Подсказка