Бінарна алгебраїчна операція
Химия

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


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

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

Зміст реферату

Завдання
1. Формалізація задачі
2. Схема алгоритму
3. Текст програми
4. Посібник користувача
5. Тест програми
Література

Завдання

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

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

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

Малюнок 1

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

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

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

Малюнок 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, як
Розробка програми мовою LISP для побудови кривих Серпінського i-го порядку градусів. Якщо одиничну пряму позначити через 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).

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

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

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

Схема алгоритму головної процедури.

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

Схема алгоритму процедури A[1]

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

;;; SIERPINS.LSP для XLISP версії 2.1

;;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

;;; Програма побудови кривих Серпінського І-го порядку.

;;;

;;; ЗАПУСК: > (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 div ( ab ) ( round ( / ab ) )

)

;;;

;;; Функція малювання прямої:

;;; Параметри: — напрям малювання (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 xy )

(setq Px x Py y)

)

;;;

;;; Функції A, B, C, 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 )

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

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

( B ( — k 1 ) )

)

)

(

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

)

)

(

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

)

)

;;;

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

;;; Параметри: — кількість ітерацій

;;;

(

defun SierpinskiCurve (Count)

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

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

(setq x0 (div * MaxX * 2)); Обчислення початкової точки

( 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); Малювання

(Bi) (Line 3h)

(C i) (Line 5 h)

(Di) (Line 7 h)

(Pause 1.0); Затримка

(setq i (+ i 1)); Інкримент лічильника

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

)

(print Try (SierpinskiCurve 4)); Підказка

4. Посібник користувача

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

x86 персональний комп’ютер (386 мінімум; 486, Pentium, або Pentium Pro рекомендується)

Microsoft DOS 3.30 або вище

Microsoft Windows 3.1, Microsoft Windows for Workgroups, Microsoft Windows 95, Microsoft Windows NT 3.51 або 4.0

512 Kb RAM

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

Встановлений інтерпретатор XLisp версії 2.1 або вище

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

Увімкнути комп’ютер

Завантажити інтерпретатор XLisp з параметром «Sierpins.lsp»: C:XLISPXLISP.EXE SIERPINS.LSP[2]Ã

У відповідь на запрошення XLisp ввести: (SierpinskiCurve 4)

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

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

Pentium 166

32 Mb RAM

SyncMaster 17Glsi

S3 Trio64V+

Windows 95

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

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

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

Малюнок 5

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

Малюнок 6

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

Малюнок 7

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

Малюнок 8

Література

«Алгоритм + структура даних = програма», H.Вірт

«XLisp-Plus 2.1 Programmers Manual», David Michael Betz

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *