Розробка програми для побудови кривих Серпінського i-го порядку Зміст

Завдання

Формалізація завдання

Схема алгоритму

Текст програми

Керівництво користувача

Тест програми

Література Завдання

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

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

Малюнок 1

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

Малюнок 2

Головна особливість кривої Серпінського полягає в тому, що вона замкнена і в ній немає перетинів. Це означає, що основна рекурсивна схема повинна давати розімкнений криву лінію, чотири частини якої з'єднуються лініями, що не належать самому рекурсивного образу. І дійсно, ці замикають лінії являють собою відрізки прямих у чотирьох зовнішніх кутах, на малюнку 2 вони виділені жирними лініями. Можна вважати, що вони належать до непорожній початкової кривої S - квадрату, "стоїть" на одному кутку. Тепер досить легко скласти рекурсивну схему.

Чотири складових образу, для наочності, позначимо через A , B , C , D , а процедури , що змальовують з'єднувальні прямі, будемо позначати стрілками, що вказують відповідному напрямі. Треба зазначити, що чотири рекурсивних образу по суті ідентичні, але лише повертиваются на 90 ° .

Основний образ кривих Серпінського задається схемою: S: A