Розробка програми Sierpins, яка реалізує побудову рекурсивних кривих Серпінського
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ЗМІСТ
Вступ
Розділ 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. Квадрат, де малюється крива, міститься в середині екрана заданої ширини і висоти.
Графічне зображення отриманого алгоритму представлено в додатку А.