Geum.ru

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

Курсовой проект - Компьютеры, программирование

Другие курсовые по предмету Компьютеры, программирование

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

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

 

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

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

 

(p1 > l1;> ... ;pn >ln )

 

Результатом його виконання буде pі‚ якщо lі прийме істине значення. В мові є пять елементарних функцій:

  1. atom - логична функция‚ яка визначає чи є досліджуваний вираз атомом - неподільною частиною інформації;
  2. eq - логична функцияё яка встановлює рівність двох атомів;
  3. car, cdr -функції, які виділяють зі списку перший елемент‚ та елементи‚ що залишились;
  4. cons - обєднання двох списків у один.

Крім елементарних‚ в мові Lisp є ряд більш складних функцій‚ які будуються з них‚ наприклад‚ підстановка в у вираз z замість всіх входжень символу y виразу x запишеться у вигляді наступної функції

 

 

цей запис представляє собою приклад програми на мові Lisp.

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

На початку програми встановлюється значення змінної *VMode*‚ яка керує установкою відео режиму, і за замовчуванням встановлена в значення 18. Ця установка відповідає режиму 640x480 Color, і працює на більшості систем. У випадку проблеми з установкою цього режиму необхідно вибрати значення цієї змінної відповідно до документації на устаткування. Розмір області для побудови кривих встановлюється константою *SquareZize*, значення якої в даному випадку становить 256.

Далі з допомогою операцій

 

h = SquareSize/4

x0 = MaxX/2

y0 = MaxY/2

 

обчислюється довжина лінії h та координати початкової точки (x0,y0) для малювання кривої .

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

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

 

 

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

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

4. малювання рекурсивної частини кривої з допомогою процедур A(i), B(i), C(i) D(i).

Потім виконується збільшення лічильника циклу на 1 і перевірка умови закінчення циклу. При досягненні лічильником циклу значення змінної Count здійснюється вихід з циклу й побудова кривої Серпінського і-го порядку завершується. На цьому програма завершує свою роботу.

При роботі з програмою встановлюються такі вимоги до системи:

  1. x86 персональний компютер (386 мінімум; 486, Pentium, чи Pentium Pro рекомендується)
  2. Microsoft DOS 3.30 чи вище
  3. Microsoft Windows 3.1, Microsoft Windows for Workgroups, Microsoft Windows 95, Microsoft Windows NT 3.51 чи 4.0
  4. 512 Kb RAM
  5. 5 Kb вільного простору на жорсткому диску
  6. Встановлений інтерпретатор XLisp версії 2.1 чи вище

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

  1. Увімкнути компютер
  2. Завантажити інтерпретатор XLisp c параметром Sierpins.lsp: C:\XLISP\XLISP.EXE SIERPINS.LSP
  3. У відповідь на запрошення XLisp увести: (SierpinskiCurve 4)

Висновки

 

Завершивши роботу над курсовим проектом можна зробити висновок про те, що мені вдалося досягти своєї мети і розробити програму побудови кривих Серпінського. За допомогою засобів алгоритмічної мови Lisp було створено програму Serp‚ яка дозволяє будувати криві Серпінського за допомогою рекурсивних процедур. Використання чотирьох рекурсивних процедур дало змогу досить просто справитись з поставленою задачею..

Розробка даної програми дала мені змогу оволодіти основними засобами програмування на алгоритмічній мові Lisp та здобути практичні навички розробки програм з використанням інтерпретатора PC-Lisp версії 3.0.

Завдяки використанню мови програмування Lisp розроблена програма вийшла лаконічною і водночас легкою для читання й розуміння, а розроблені рекурсивні графічні процедури можуть бути використані при розвязуванні інших, можливо набагато складніших програм.

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

 

  1. “Алгоритм + структура даних = програма”, H.Вірт.
  2. “XLisp-Plus 2.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* відповідно до обраного режиму

;;

(

defun InitGraph()

(

case *VMode*

( 4 ;320x200 Color

( mode 4 )

( setq *MaxX* 320 *MaxY* 200 *SquareSize* 128 ) )