Розробка програми Sierpins, яка реалізує побудову рекурсивних кривих Серпінського

ЗМІСТ

Вступ

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

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

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

Висновки

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

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

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

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

Вступ

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

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

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

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

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

Програма рисування кривих Серпінського реалізована мовою Lisp. Текст програми наведено в додатку Б.

Програма на мові Lisp прдставляє собою рекурсивну функцію символьних виразів‚ яка будується аналогічно до арифметичних функцій з допомогою умовного оператора та оператора суперпозиції. Умовний оператор має вигляд

( p ₁ → l ₁ ;→ ... ; p_n → l_n )

Результатом його виконання буде 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 та координати початкової точки (x₀ ,y₀ ) для малювання кривої .

Рисування кривої здійснюється в циклі по змінній і ‚ котра визначає порядок кривої Серпінського (при тестовому запуску програми пропонувалось 4). В циклі виконуються такі операції:

1. обчислення координат початкової точки для малювання та визначення довжини одиничної лінії за формулами

2. установка пера в точку з координатами P_x P_y

3. визначення і установка кольору для малювання