ЗМІСТ
Вступ
Розділ1. Криві Серпінського.
Розділ2. Методи та засоби розв'язку задачі
Розділ3. Практична реалізація розв'язку задачі
Висновки
Списоквикористаної літератури.
Додатока. Блок-схема алгоритму.
Додатокб. Текст програми
Додатокв. Тест програми
/>/>Вступ
Мови програмування — це формальні мови зв'язку людиниз машиною‚ призначені для опису даних та алгоритмів(програм) їх обробки на ЕОМ.Алгоритмічні мови‚ існують в наш час‚ поділяються на три великих класи:машинно-орієнтовані‚ процедурно-орієнтовані та проблемно-орієнтовані. Домашинно-орієнтованих відносяться мови‚ в яких з однієї сторони явно вираженийзв'язок з конкретною ЕОМ (структура команд‚ пам'яті‚ зовнішніх пристроїв)‚ а здругої — в мову введено елементи‚ які спрощують і автоматизують процеспрограмування (символьне позначення команд і комірок пам'яті‚ широкезастосування звичних для людини позначень і т.д.). Процедурно-орієнтовані мовиє вищим рівнем мов програмування, призначені для різних сфер застосування ЕОМ івраховують специфіку їх застосування.
Особливий клас утворюють мови‚ призначені для описуспеціальних проблем і які носять назву проблемно-орієнтованих мов. Програма,реалізована на такій мові програмування містять крім опису умови задачівказівку розв'язати задачу даного класу. Прикладом такої мови є, наприклад,мова Stress‚ яка призначається для описузадач конструювання. Програма на цій мові містить ряд загальних характеристиксистеми (розмірності‚ число вершин та ін.) і дані‚ а також вказівку — розв'язати задачу і представити певні дані у вигляді деякої таблиці.
Програмна реалізація курсового проекту здійснюваласьна алгоритмічній мові Lisp. Мова Lisp є процедурно-орієнтованою мовою івідноситься до групи мов програмування‚ призначених для обробки списків (сюди жвідносяться мови. IL-V, КОМИТ). Мова IPL-V використовується для досліджень вобласті штучного інтелекту.
Особливістю мови Lisp є використання ланцюжковоїадресації — кожен член списку містить інформацію про себе у виглядібезпосереднього значення чи адреси та адресу наступного елемента списку. Мова єзручним засобом при створенні програм обробки інформації‚ зміст та об'єм якоїнаперед невідомі.
/>/>Розділ 1. Криві Серпінського
Оригінальний візерунок на малюнку 1 складається ізсуперпозиції чотирьох кривих. Ці криві відповідають деякому регулярному образу.Алгоритм для побудови цих кривих на екрані монітора чи на графобудівнику підкеруванням обчислювальної машини описаний у [1].
Задача проекту – реалізувати цей алгоритм увиді програми функціональною мовою програмування Lisp.
/>
Малюнок 1
Аналізуючи малюнок 1, можна переконатись, що вінотриманий шляхом накладення один на одного декількох кривих. Перші дві з нихпоказані на малюнку 2. Крива Si називається кривою СерпінськогоІ-го порядку. Необхідно з'ясувати, яка рекурсивна схема цих кривих.
/>
Малюнок 2
Головна особливість кривої Серпінського полягає втому, що вона замкнута й у ній немає перетинань. Це означає, що основнарекурсивна схема повинна давати розімкнуту криву лінію, чотири частини якоїз'єднуються лініями, що не належать самому рекурсивному образу. І дійсно, цізамикаючі лінії являють собою відрізки прямих у чотирьох зовнішніх кутах, намалюнку 2 вони виділені жирними лініями. Можна вважати, що вони належать до непорожньої початкової кривої S – квадрату, який «стоїть» на одному куті. Тепердосить легко скласти рекурсивну схему.
Чотири складових образи, для наочності, позначимочерез A, B, C, D, а процедури, що малюють сполучніпрямі, будемо позначати стрільцями, що указують відповідному напрямку. Требавідзначити, що чотири рекурсивних образи власне кажучи ідентичні, але лишеповертаються на 90°.
/>/>
Розділ 2. Методи та засобирозв'язку задачі
Основний образ кривих Серпінського задається схемою:
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, як /> градусів.Якщо одиничну пряму позначити через 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. Практичнареалізація розв'язку задачі
Програма рисування кривих Серпінського реалізована мовою Lisp. Текст програми наведено в додатку Б.
Програма на мові Lisp прдставляє собою рекурсивну функцію символьних виразів‚ яка будуєтьсяаналогічно до арифметичних функцій з допомогою умовного оператора та операторасуперпозиції. Умовний оператор має вигляд
(p1→ l1;→… ;pn→ln)
Результатом його виконання буде pі‚ якщо lі прийме істине значення. В мові є п'ять елементарних функцій:
- atom — логична функция‚ яка визначає чи єдосліджуваний вираз атомом — неподільною частиною інформації;
- eq — логична функцияё яка встановлює рівність двох атомів;
- car, cdr -функції, які виділяють зісписку перший елемент‚ та елементи‚ що залишились;
- cons — об'єднання двох списків у один.
Крім елементарних‚ в мові Lisp є ряд більш складних функцій‚ якібудуються з них‚ наприклад‚ підстановка в у вираз z замість всіх входженьсимволу y виразу x запишеться у вигляді наступноїфункції
/>
цей запис представляє собою приклад програми на мові Lisp.
В даному курсовому проекті на мови Lispрозроблено програму Sierpins,яка реалізує побудову рекурсивних кривих Серінського.
Напочатку програми встановлюється значення змінної *VMode*‚ яка керуєустановкою відео режиму, і за замовчуванням встановлена в значення 18. Цяустановка відповідає режиму 640x480 Color, і працює на більшості систем. Увипадку проблеми з установкою цього режиму необхідно вибрати значення цієїзмінної відповідно до документації на устаткування. Розмір області для побудовикривих встановлюється константою *SquareZize*,значення якої в даному випадку становить 256.
Даліз допомогою операцій
h= SquareSize/4
x= MaxX/2
y= MaxY/2
обчислюєтьсядовжина лінії hта координати початкової точки (x0,y0)для малювання кривої .
Рисуваннякривої здійснюється в циклі по змінній і‚котра визначає порядок кривої Серпінського (при тестовому запуску програмипропонувалось 4). В циклі виконуються такі операції:
1.обчислення координат початкової точки для малювання та визначення довжиниодиничної лінії за формулами
/>
2.установка пера в точку з координатами PxPy
3.визначення і установка кольору для малювання
4.малювання рекурсивної частини кривої з допомогою процедур A(i),B(i),C(i)D(i).
Потімвиконується збільшення лічильника циклу на 1 і перевірка умови закінченняциклу. При досягненні лічильником циклу значення змінної Countздійснюється вихід з циклу й побудова кривої Серпінського і-го порядкузавершується. На цьому програма завершує свою роботу.
При роботі з програмою встановлюються такі вимоги досистеми:
ü x86 персональний комп'ютер(386 мінімум; 486, Pentium, чи Pentium Pro рекомендується)
ü Microsoft DOS 3.30 чи вище
ü Microsoft Windows 3.1,Microsoft Windows for Workgroups, Microsoft Windows 95, Microsoft Windows NT3.51 чи 4.0
ü 512 Kb RAM
ü 5 Kb вільного простору нажорсткому диску
ü Встановлений інтерпретаторXLisp версії 2.1 чи вище
Для запуску програми необхідно:
q Увімкнути комп'ютер
q Завантажити інтерпретаторXLisp c параметром «Sierpins.lsp»: C:\XLISP\XLISP.EXESIERPINS.LSP[1]Ã
q У відповідь на запрошенняXLisp увести: (SierpinskiCurve 4)Ã
/>/>Висновки
Завершивши роботу над курсовим проектомможна зробити висновок про те, що мені вдалося досягти своєї мети і розробитипрограму побудови кривих Серпінського. За допомогоюзасобів алгоритмічної мови Lisp було створено програму Serp‚ яка дозволяєбудувати криві Серпінського за допомогою рекурсивних процедур. Використаннячотирьох рекурсивних процедур дало змогу досить просто справитись з поставленоюзадачею…
Розробка даної програми дала мені змогуоволодіти основними засобами програмування на алгоритмічній мові Lisp та здобутипрактичні навички розробки програм з використанням інтерпретатора PC-Lisp версії3.0.
Завдяки використанню мовипрограмування Lisp розроблена програма вийшла лаконічноюі водночас легкою для читання й розуміння, а розроблені рекурсивні графічніпроцедури можуть бути використані при розв'язуванні інших, можливо набагатоскладніших програм.
/>/>Список використаноїлітератури
1. “Алгоритм+ структура даних = програма”, H.Вірт.
2. “XLisp-Plus2.1 Programmers Manual”, David Michael Betz
/>/>/>Додаток А. Блок-схема алгоритму
/>
Схема алгоритму процедури A
/>
/>/>/>Додаток Б. Текст програми
;;SIERPINS.LSP для XLISP версії 2.1
;;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
;;Програма побудови кривих Серпінського i-го порядку.
;;
;;ЗАПУСК: > (SierpinskiCurve 4)
;;
;;
(defvar *VMode* 18 ) ; Відео режим за замовчуванням
(defvar *Max* 640 ) ; Максимальна ширина екрана за замовчуванням
(defvar *Max* 480 ) ; Максимальна висота екрана за замовчуванням
(defvar *SquareSize* 256 ); Розмір області для побудови
;;
;;Функція ініціалізує графічний режим, установлює перемінні
;;*Max* *Max* *SquareSize* відповідно до обраного режиму
;;
(
defunInitGraph()
(
case *VMode*
( 4 ;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* ) )
)
)
;;
;;Функція реалізує затримку на заданий час
;;
(
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 )
(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, 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 ); Установка графічного режиму
(setq h ( div *SquareSize* 4 ) ) ; Обчислення довжини лінії
(setq x0 ( div *Max* 2 ) ) ; Обчислення початкової точки
(setq y0 ( + ( div *Max* 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) ) ; Підказка