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

МИНИСТЕРСТВО ВЫСШЕГО ИСРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РФ

МОСКОВСКИЙ ИНСТИТУТРАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

Курсовой проект

Тема:

«Разработка программы наязыке LISP

для построения кривых Серпинскогоi-го порядка»

Факультет:

ВАВТ

Дисциплина:

ФПО

Студент:

Группа:

Специальность:

2202

Преподаватель:

Яшин Л.З.

МОСКВА

DATE @ «MMMM yyyy» * MERGEFORMAT октябрь 2008

Оглавление

TOC o «1-3» Задание… PAGEREF_Toc407475828 h 3

Формализация задачи… PAGEREF_Toc407475829 h 4

Схема алгоритма… PAGEREF_Toc407475830 h 6

Текст программы… PAGEREF_Toc407475831 h 8

Руководство пользователя… PAGEREF_Toc407475832 h 11

Тест программы… PAGEREF_Toc407475833 h 12

Литература… PAGEREF_Toc407475834 h 14

Задание

Оригинальный узор на рисунке 1состоит из суперпозиции четырех кривых. Эти кривые соответствуют некоторомурегулярному образу.Алгоритм для построения этих кривых на экране монитора или на графопостроителе подуправлением вычислительной машины описан в [1].

Задача проекта –реализовать этот алгоритм в виде программы на функциональном языкепрограммирования Lisp.

Рисунок SEQ Рисунок * ARABIC 1

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

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

Рисунок SEQ Рисунок * ARABIC 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, как<img src="/cache/referats/946/image006.gif" v:shapes="_x0000_i1027"> градусов. Если единичную прямуюобозначить через 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).

По сравнению с таким рекурсивнымпостроением эквивалентные программы, где избегали употребления рекурсии,выглядят крайне сложными и запутанными.

Схема алгоритма

Рисунок SEQ Рисунок * ARABIC 3 Схема алгоритма главной процедуры

Рисунок SEQ Рисунок * ARABIC 4 Схема алгоритма процедуры A[1]

Текст программы

;; 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* в соответствии с выбранным режимом

;;

(

defunInitGraph()

(

case*VMode*

( 4 ;320x200 Color

( mode4 )

( setq*MaxX* 320 *MaxY* 200 *SquareSize* 128 ) )

( 16 ;640x350 Color

( mode16 )

( setq*MaxX* 640 *MaxY* 350 *SquareSize* 128 ) )

( 18 ;640x480 Color

( mode18 ) )

( 106 ;800x600 Color

( mode106 106 800 600 )

( setq*MaxX* 800 *MaxY* 600 *SquareSize* 512 ) )

( t ( error Unsupported graphics mode: *VMode* ) )

)

;;

;; Функция реализуетзадержку на заданное время

;;

(

defunpause ( time )

( let( ( fintime ( + ( * time internal-time-units-per-second )

(get-internal-run-time ) ) ) )

( loop( when ( > (get-internal-run-time) fintime )

( return-from pause ) ) ) )

)

;;

;; Функция целочисленного деления

;;

(

defun div ( a b ) ( round( / a b ) )

)

;;

;; Функция рисованияпрямой:

;; Параметры: — направление рисования (0-7)

;; — длинна прямой

;;

(

defunLine( Direction Size )

( setqx Px y Py )

(

caseDirection

( 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 ) ) )

)

( movePx Py x y )

( setqPx x Py y )

)

;;

;; Функции A, B, C, D — рекурсивные функции рисования

;;

(

defunA ( 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 ) )

) )

)

(

defunB ( k )

( cond( ( > k 0 )

( B ( — k 1 ) ) ( Line 3 h )

( C ( — k 1 ) ) ( Line 2 ( * 2 h ) )

( A ( — k 1 ) ) ( Line 1 h )

( B ( — k 1 ) )

) )

)

(

defunC ( k )

( cond( ( > k 0 )

( C ( — k 1 ) ) ( Line 5 h )

( D ( — k 1 ) ) ( Line 4 ( * 2 h ) )

( B ( — k 1 ) ) ( Line 3 h )

( C ( — k 1 ) )

) )

)

(

defunD ( k )

( cond( ( > k 0 )

( D ( — k 1 ) ) ( Line 7 h )

( A ( — k 1 ) ) ( Line 6 ( * 2 h ) )

( C ( — k 1 ) ) ( Line 5 h )

( D ( — k 1 ) )

) )

)

;;

;; Главная процедура

;; Параметры: — количество итераций

;;

(

defunSierpinskiCurve ( Count )

( InitGraph ); Установка графического режима

( setqh ( div *SquareSize* 4 ) ) ; Вычисление длины линии

( setqx0 ( div *MaxX* 2 ) ) ; Вычисление начальной точки

( setqy0 ( + ( div *MaxY* 2 ) h ) ) ; длярисования

( ; Основнойцикл

do(( i 1 )) ; Инициализация счетчика

(( eqli ( + 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) ) ; Подсказка

Руководство пользователя

Требования к системе:

ü

MicrosoftDOS 3.30 или выше

ü

Microsoft Windows 95,Microsoft Windows NT 3.51 или 4.0

ü

512KbRAM

ü

Kb свободного пространства на жестком диске

ü

Для запуска программы необходимо:

q

XLisp c параметром«Sierpins.lsp»: C:XLISPXLISP.EXESIERPINS.LSP[2]Ã

q

XLisp ввести:(SierpinskiCurve 4)Ã
Тест программы

Тестпроводился на рабочей станции со следующей конфигурацией:

q

Pentium166

q

32Mb RAM

q

SyncMaster17Glsi

q

S3Trio64V+

q

Windows95

Интерпретатор XLisp был запущен в окне MS-DOS.

Программатестировалась при значениях параметра Countот1 до 4. В результате тестов были получены следующие изображения на экранемонитора[3]

Рисунок SEQ Рисунок * ARABIC 5

Рисунок SEQ Рисунок * ARABIC 6

Рисунок SEQ Рисунок * ARABIC 7

Рисунок SEQ Рисунок * ARABIC 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

еще рефераты

Еще работы по программированию, базе данных

Реферат по программированию, базе данных

Программирование на С

29 Августа 2013

Реферат по программированию, базе данных

Форматы баз данных в автоматизированных библиографических системах

29 Августа 2013

Реферат по программированию, базе данных

Препроцессор языка СИ

29 Августа 2013

Реферат по программированию, базе данных

Разработка фрагмента информационной системы "АБОНЕНТЫ ГТС"

29 Августа 2013