Вступ

Розділ 1. Криві Серпінського.

Розділ 2. Методи та засоби розв'язку задачі

Розділ 3. Практична реалізація розв'язку задачі

Висновки

Список використаної літератури.

Додаток а. Блок-схема алгоритму.

Додаток б. Текст програми

Додаток в. Тест програми

Вступ

Мови програмування - це формальні мови зв'язку людини з машиною‚ призначені для опису даних та алгоритмів(програм) їх обробки на ЕОМ. Алгоритмічні мови‚ існують в наш час‚ поділяються на три великих класи: машинно-орієнтовані‚ процедурно-орієнтовані та проблемно-орієнтовані. До машинно-орієнтованих відносяться мови‚ в яких з однієї сторони явно виражений зв'язок з конкретною ЕОМ (структура команд‚ пам'яті‚ зовнішніх пристроїв)‚ а з другої - в мову введено елементи‚ які спрощують і автоматизують процес програмування (символьне позначення команд і комірок пам'яті‚ широке застосування звичних для людини позначень і т.д.). Процедурно-орієнтовані мови є вищим рівнем мов програмування, призначені для різних сфер застосування ЕОМ і враховують специфіку їх застосування.

Особливий клас утворюють мови‚ призначені для опису спеціальних проблем і які носять назву проблемно-орієнтованих мов. Програма, реалізована на такій мові програмування містять крім опису умови задачі вказівку розв'язати задачу даного класу. Прикладом такої мови є, наприклад, мова Stress‚ яка призначається для опису задач конструювання. Програма на цій мові містить ряд загальних характеристик системи (розмірності‚ число вершин та ін.) і дані‚ а також вказівку - розв'язати задачу і представити певні дані у вигляді деякої таблиці.

Програмна реалізація курсового проекту здійснювалась на алгоритмічній мові Lisp. Мова Lisp є процедурно-орієнтованою мовою і відноситься до групи мов програмування‚ призначених для обробки списків (сюди ж відносяться мови. IL-V, КОМИТ). Мова IPL-V використовується для досліджень в області штучного інтелекту.

Особливістю мови Lisp є використання ланцюжкової адресації - кожен член списку містить інформацію про себе у вигляді безпосереднього значення чи адреси та адресу наступного елемента списку. Мова є зручним засобом при створенні програм обробки інформації‚ зміст та об'єм якої наперед невідомі.

Розділ 1. Криві Серпінського

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

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

Малюнок 1

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

Малюнок 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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--