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

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Разработка программы на языке LISP для построения кривых Серпинского i-го порядка

    МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РФ
    МОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ
    Курсовой проект
    Тема:
    «Разработка программы на языке
    LISP
    для построения кривых Серпинского
    го порядка
    Факультет:
    ВАВТ
    Дисциплина:
    ФПО
    Студент:
    Группа:
    Специальность:
    2202
    Преподаватель:
    Яшин Л.З.
    МОСКВА
    DATE \\@ \"MMMM yyyy\" \\* MERGEFORMAT
    октябрь 2008
    Оглавление
    TOC \\o \"1-3\"
    Задание
    ...........................................................................................................................................................................
    PAGEREF _Toc407475828 \\h
    Формализация задачи
    ......................................................................................................................................
    PAGEREF _Toc407475829 \\h
    Схема алгоритма
    ..................................................................................................................................................
    PAGEREF _Toc407475830 \\h
    Текст программы
    ..................................................................................................................................................
    PAGEREF _Toc407475831 \\h
    Руководство пользователя
    .....................................................................................................................
    PAGEREF _Toc407475832 \\h
    Тест программы
    ..................................................................................................................................................
    PAGEREF _Toc407475833 \\h
    Литература
    ...............................................................................................................................................................
    PAGEREF _Toc407475834 \\h
    Задание
    Оригинальный узор на рисунке 1 состоит из суперпозиции четырех кривых. Эти кривые соответствуют некоторому регулярному образу
    . Алгоритм для построения этих кривых на экране монитора или на графопостроителе под управлением вычислительной машины описан в
    [1].
    Задача проекта – реализовать этот алгоритм в виде программы на функциональном языке программирования
    Lisp.
    Рисунок
    SEQ Рисунок \\* ARABIC
    Формализация задачи
    Анализируя рисунок 1, можно обнаружить, что он получен путем наложения друг на друга нескольких кривых. Первые две из них показаны на рисунке 2. Кривая
    i называется кривой Серпинского
    i-го порядка. Необходимо выяснить, какова рекурсивная схема этих кривых.
    Рисунок
    SEQ Рисунок \\* ARABIC
    Главная особенность кривой Серпинского состоит в том, что она замкнута и в ней нет пересечений. Это означает, что основная рекурсивная схема
    должна давать разомкнутую кривую линию, четыре части которой соединяются линиями, не принадлежащими самому рекурсивному образу. И действительно, эти замыкающие линии
    представляют собой отрезки прямых в четырех внешних углах, на рисунке 2 они выделены жирными линиями. Можно считать, что они принадлежат к непустой начальной кривой
    S – квадрату, «стоящему» на одном углу. Теперь достаточно легко составить рекурсивную схему.
    Четыре составляющих образа, для наглядности, обозначим через
    , B, C, D, а процедуры, рисующие соединительные прямые, будем обозначать стрелками, указывающими соответствующем направлении. Надо отметить, что четыре рекурсивных образа
    по существу идентичны, но лишь повертываются на 90
    Основной образ кривых Серпинского задается схемой:
    а рекурсивные составляющие (горизонтальные и вертикальные отрезки – двойной длины):
    Предположим, что для построения части прямой в нашем распоряжении есть процедура
    Line, передвигающая перо в заданном направлении на заданное расстояние, причем направление задается целочисленным параметром
    , как
    градусов. Если единичную прямую обозначить через
    h, то с помощью рекурсивных обращений к аналогично составленным процедурам для
    B и
    D и к самой
    A довольно просто написать процедуру, соответствующую схеме А.
    ( defun A ( k )
    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. Ее задача - установить начальную точку кривой, т.е. исходные координаты пера (
    x и
    y) и единичную длину приращения
    h. Квадрат, где рисуется кривая, помещается в середине экрана, заданной ширины и высоты.
    Графическое изображение полученного алгоритма представлено в следующем разделе (Рисунок 3).
    По сравнению с таким рекурсивным построением эквивалентные программы, где избегали употребления рекурсии, выглядят крайне сложными и запутанными.
    Схема алгоритма
    Рисунок
    SEQ Рисунок \\* ARABIC
    Схема алгоритма главной процедуры
    Рисунок
    SEQ Рисунок \\* ARABIC
    Схема алгоритма процедуры
    Текст программы
    ;; SIERPINS.LSP для XLISP версии 2.1
    ;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    ;; Программа построения кривых Серпинского i-го порядка.
    ;; ЗАПУСК:
    (SierpinskiCurve 4)
    ;; Замечание: Переменная *VMode* управляет установкой видео режима,
    и по умолчанию установлена в значение 18.
    Эта установка соответствует режиму 640x480 Color,
    и работает на большинстве систем. В случае проблемы
    с установкой этого режима необходимо выбрать
    значение этой переменной в соответствии с документацией
    на оборудование.
    ( defvar *VMode* 18 )
    Видео режим по умолчанию
    ( defvar *MaxX* 640 )
    Максимальная ширина экрана по умолчанию
    ( defvar *MaxY* 480 )
    Максимальная высота экрана по умолчанию
    ( defvar *SquareSize* 256 ) ;Размер области для построения
    ;; Функция инициализирует графический режим, устанавливает переменные
    ;; *MaxX* *MaxY* *SquareSize* в соответствии с выбранным режимом
    defun InitGraph()
    case *VMode*
    320x200 Color
    ( mode 4 )
    ( setq *MaxX* 320 *MaxY* 200 *SquareSize* 128 ) )
    ( 16
    640x350 Color
    ( mode 16 )
    ( setq *MaxX* 640 *MaxY* 350 *SquareSize* 128 ) )
    ( 18
    640x480 Color
    ( mode 18 ) )
    ( 106
    800x600 Color
    ( mode 106 106 800 600 )
    ( setq *MaxX* 800 *MaxY* 600 *SquareSize* 512 ) )
    ( t ( error Unsupported graphics mode:
    *VMode* ) )
    ;; Функция реализует задержку на заданное время
    defun pause ( time )
    ( let ( ( fintime ( + ( * time internal-time-units-per-second )
    ( get-internal-run-time )
    ) ) )
    ( get-internal-run-time) fintime )
    ( return-from pause ) ) ) )
    ;; Функция целочисленного деления
    defun div ( a b ) ( round ( / a b ) )
    ;; Функция рисования прямой:
    ;; Параметры: - направление рисования (0-7)
    - длинна прямой
    defun Line( Direction Size )
    ( setq x Px y Py )
    case Direction
    ( 0 ( setq x ( + x Size) ) )
    ( 1 ( setq x ( + x Size ) y ( - y Size ) ) )
    ( 2 ( setq y ( - y Size) ) )
    ( 3 ( setq x ( - x Size ) y ( - y Size ) ) )
    ( 4 ( setq x ( - x Size) ) )
    ( 5 ( setq x ( - x Size ) y ( + y Size ) ) )
    ( 6 ( setq y ( + y Size) ) )
    ( 7 ( setq x ( + x Size ) y ( + y Size ) ) )
    ( move Px Py x y )
    ( setq Px x ...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены