Розробка програми мовою LISP для побудови кривих Серпінського i-го порядку

МІНІСТЕРСТВО ВИЩОЇ І СЕРЕДНЬОГО СПЕЦІАЛЬНОГО ОСВІТИ РФ.

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

Курсової проект.

Тема:

«Розробка програми мовою LISP для побудови кривих Серпинского i-го порядка».

|Факультет: |ВАВТ | |Дисципліна: |ФПО | |Студент: | | |Група: | | |Спеціальність: |2202 | |Викладач: |Яшин Л.З. |.

МОСКВА.

Травень 1998.

Оглавление Задание 3.

Формалізація завдання 4.

Схема алгоритму 6.

Текст програми 8.

Керівництво користувача 11.

Тест програми 12.

Література 14.

Задание.

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

Завдання проекту — реалізувати цей алгоритм як програми на функціональному мові програмування Lisp.

[pic].

Малюнок 1.

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

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

[pic].

Малюнок 2.

Головна особливість кривою Серпинского у тому, що вона замкнута у ній немає перетинань. Це означає, основна рекурсивна схема має давати разомкнутую криву лінію, чотири частини якої з'єднуються лініями, не які належать самому рекурсивному образу. І це дійсно, ці замикаючі лінії є відтинки прямих чотири зовнішніх кутках, малюнку 2 їх виділено жирними лініями. Можна вважати, що вони належать до непорожній початковій кривою P. S — квадрату, «що стоїть» однією розі. Тепер досить легко скласти рекурсивную схему.

Чотири складових образу, для наочності, позначимо через A, B, З, D, але процедуру, які малюють з'єднувальні прямі, будемо позначати стрілками, указывающими відповідному напрямі. Слід зазначити, що чотири рекурсивних образу сутнісно ідентичні, але тільки повертываются на 90(.

Основний образ кривих Серпинского задається схемой:

P.S: A (B (З (D (.

а рекурсивні складові (горизонтальні і вертикальні відтинки — подвійний длины):

A: A (B (D (A.

B: B (З (A (B.

З: З (D (B (C.

D: D (A (З (D.

Припустимо, що з побудови частини прямий у нашій розпорядженні є процедура Line, передвигающая перо в заданому напрямку заданий відстань, причому напрям задається целочисленным параметром і, як [pic] градусів. Якщо одиничну пряму позначити через 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. Головна програма будується на зразок P. S. Її завдання — встановити початкову точку кривою, тобто. вихідні координати пера (Px і Py) і одиничну довжину збільшення h. Квадрат, де малюється крива, міститься у середині екрана, заданої ширини і высоты.

Графічне зображення отриманого алгоритму представлено наступного розділі (Малюнок 3).

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

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

[pic].

Малюнок 3 Схема алгоритму головною процедуры.

[pic].

Малюнок 4 Схема алгоритму процедури A[1].

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

;; SIERPINS. LSP для XLISP версії 2.1 ;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ;; Програма побудови кривих Серпинского i-го порядку. ;; ;; ЗАПУСК: > (SierpinskiCurve 4) ;; ;; Зауваження: Змінна *VMode* управляє установкою відео режиму, ;; і з вмовчанням встановлена у значення 18. ;; Ця установка відповідає режиму 640×480 Color, ;; й працює більшості систем. Що стосується проблеми ;; із установкою цього режиму необхідно вибрати ;; значення цієї перемінної відповідно до документацією ;; обладнання. ;;

(defvar *VMode* 18) ;Відео режим за умовчанням (defvar *MaxX* 640) ;Максимальна ширина екрана за умовчанням (defvar *MaxY* 480) ;Максимальна висота екрана за умовчанням (defvar *SquareSize* 256) ;Розмір області для построения.

;; ;; Функція инициализирует графічний режим, встановлює перемінні ;; *MaxX* *MaxY* *SquareSize* відповідно до обраним режимом ;; (defun InitGraph ().

(case *VMode*.

(4 ;320×200 Color.

(mode 4).

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

(16 ;640×350 Color.

(mode 16).

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

(18 ;640×480 Color.

(mode 18)).

(106 ;800×600 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)))).

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

(return-from pause))))).

;; ;; Функція целочисленного розподілу ;; (defun divx (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 Py y)).

;; ;; Функції A, B, З, D — рекурсивні функції малювання ;; (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)).

))).

(defun B (k).

(cond ((> k 0).

(B (- k 1)) (Line 3 h).

(З (- k 1)) (Line 2 (* 2 h)).

(A (- k 1)) (Line 1 h).

(B (- k 1)).

))).

(defun З (k).

(cond ((> k 0).

(З (- k 1)) (Line 5 h).

(D (- k 1)) (Line 4 (* 2 h)).

(B (- k 1)) (Line 3 h).

(З (- k 1)).

))).

(defun D (k).

(cond ((> k 0).

(D (- k 1)) (Line 7 h).

(A (- k 1)) (Line 6 (* 2 h)).

(З (- k 1)) (Line 5 h).

(D (- k 1)).

))).

;; ;; Головна процедура ;; Параметри: — кількість ітерацій ;; (defun SierpinskiCurve (Count).

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

(setq h (divx *SquareSize* 4)) ;Обчислення довжини линии.

(setq x0 (divx *MaxX* 2)) ;Обчислення початковій точки.

(setq y0 (+ (divx *MaxY* 2) h)) ;для рисования.

(;Основний цикл do ((і 1)) ;Ініціалізація счетчика.

((eql і (+ Count 1)) «Done) ;Умова завершения.

(setq x0 (- x0 h)) ;Обчислення координат начальной.

(setq h (divx h 2)) ;точки для малювання и.

(setq y0 (+ y0 h)) ;одиничної довжини линии.

(setq Px x0 Py y0) ;Установка пера.

(color і) ;Установка кольору для рисования.

(A і) (Line 1 h) ;Рисование.

(B і) (Line 3 h).

(З і) (Line 5 h).

(D і) (Line 7 h).

(pause 1.0) ;Задержка.

(setq і (+ і 1)) ;Инкримент счетчика.

) ;Кінець основного циклу).

(print Try (SierpinskiCurve 4)) ;Подсказка.

Керівництво пользователя.

Вимоги до системе:

V x86 персонального комп’ютера (386 мінімум; 486, Pentium, или.

Pentium Pro рекомендуется).

V Microsoft DOS 3.30 чи выше.

V Microsoft Windows 3.1, Microsoft Windows for Workgroups,.

Microsoft Windows 95, Microsoft Windows NT 3.51 чи 4.0.

V 512 Kb RAM.

V 5 Kb вільного простору на жорсткому диске.

V Встановлений інтерпретатор XLisp версії 2.1 чи выше.

Для запуску програми необхідно: o Включити комп’ютер o Завантажити інтерпретатор XLisp з параметром «Sierpins.lsp»:

C:XLISPXLISP.EXE SIERPINS. LSP[2](o У у відповідь запрошення XLisp запровадити: (SierpinskiCurve 4)(.

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

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

o Pentium 166 o 32 Mb RAM o SyncMaster 17Glsi o S3 Trio64V+ o Windows 95.

Інтерпретатор XLisp запущено з вікна MS-DOS.

Програма тестувалися при значеннях параметра Count від 1 до запланованих 4. У результаті тестів було отримано такі зображення на екрані монитора[3]:

[pic].

Малюнок 5.

[pic].

Малюнок 6.

[pic].

Малюнок 7.

[pic].

Малюнок 8.

o «Алгоритм + структура даних = програма», H. Вирт o «XLisp-Plus 2.1 Programmers Manual», David Michael Betz ———————————- [1] Схеми алгоритмів процедур B, З і D аналогічні A, і тому, у тому зображенні не потрібно. [2] Цей приклад передбачає, що XLisp встановлено у каталозі C: XLISP і його запуск виробляється у режимі MS-DOS. [3] У конкурсній програмі було встановлено графічний відео режим з дозволом 640×480 256 Color.