Разработка программы на языке LISP для построения кривых Серпинского i-го порядка

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГОСПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РФМОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ,ЭЛЕКТРОНИКИ И АВТОМАТИКИКурсовой проектТема Разработка программы на языке LIСпециальность 2202 Преподаватель

Яшин Л.З. МОСКВАоктябрь 2005ОглавлениеЗадание 3Формализация задачи 4Схема алгоритма 6Текст программы 8Руководство пользователя 11Тест программы 12Литература 14ЗаданиеОригинальный узор на рисунке 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 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 ПодсказкаРуководство пользователяТребования к системе x86 персональный компьютер 386 минимум 486,Pentium, или Pentium Pro рекомендуется MicrosoftDOS 3.30 или выше Microsoft Windows 3.1, Microsoft Windows forWorkgroups,

Microsoft Windows 95,Microsoft Windows NT 3.51 или 4.0 512 KbRAM 5 Kb свободного пространства на жестком диске Установленныйинтерпретатор XLisp версии 2.1 или вышеДля запуска программынеобходимо q Включитькомпьютерq Загрузитьинтерпретатор XLisp c параметром Sierpins.lsp C XLISP XLISP.EXESIERPINS.LSP 2 q Вответ на приглашение

XLisp ввести SierpinskiCurve4 Тест программыТестпроводился на рабочей станции со следующей конфигурацией q Pentium166q 32Mb RAMq SyncMaster17Glsiq S3Trio64V q Windows95Интерпретатор XLisp был запущен в окне MS-DOS.Программатестировалась при значениях параметра Count от1 до 4. В результате тестов были получены следующие изображения на экранемонитора 3

Рисунок 5Рисунок 6Рисунок 7Рисунок 8Литератураq Алгоритм структура данных программа , H.Виртq XLisp-Plus2.1 Programmers Manual , David Michael Betz 1 Схемыалгоритмов процедур B, C иD аналогичны A, и поэтому, в ихизображении нет необходимости. 2 Данный пример предполагает, что XLispустановлен в каталоге

C XLISPи его запуск производится в режиме MS-DOS. 3 Впрограмме был установлен графический видео режим с разрешением 640x480 256 Color