![]() |
|
сделать стартовой | добавить в избранное |
![]() |
Разработка программы для построения кривых Серпинского i-го порядка |
Оглавление Задание Формализация задачи Схема алгоритма Текст программы Руководство пользователя Тест программы Литература Задание Оригинальный узор на рисунке 1 состоит из суперпозиции четырех кривых. Эти кривые соответствуют некоторому регулярному образу. Алгоритм для построения этих кривых на экране монитора или на графопостроителе под управлением вычислительной машины описан в . Задача проекта – реализовать этот алгоритм в виде программы на функциональном языке программирования Lisp. Рисунок 1 Анализируя рисунок 1, можно обнаружить, что он получен путем наложения друг на друга нескольких кривых. Первые две из них показаны на рисунке 2. Кривая Si называется кривой Серпинского i-го порядка. Необходимо выяснить, какова рекурсивная схема этих кривых. Рисунок 2 Главная особенность кривой Серпинского состоит в том, что она замкнута и в ней нет пересечений. Это означает, что основная рекурсивная схема должна давать разомкнутую кривую линию, четыре части которой соединяются линиями, не принадлежащими самому рекурсивному образу. И действительно, эти замыкающие линии представляют собой отрезки прямых в четырех внешних углах, на рисунке 2 они выделены жирными линиями. Можно считать, что они принадлежат к непустой начальной кривой S – квадрату, “стоящему” на одном углу. Теперь достаточно легко составить рекурсивную схему. Четыре составляющих образа, для наглядности, обозначим через A, B, C, D, а процедуры, рисующие соединительные прямые, будем обозначать стрелками, указывающими соответствующем направлении. Надо отметить, что четыре рекурсивных образа по существу идентичны, но лишь повертываются на 90° . Основной образ кривых Серпинского задается схемой: 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 Предположим, что для построения части прямой в нашем распоряжении есть процедура Li e, передвигающая перо в заданном направлении на заданное расстояние, причем направление задается целочисленным параметром i, как градусов. Если единичную прямую обозначить через h, то с помощью рекурсивных обращений к аналогично составленным процедурам для B и D и к самой A довольно просто написать процедуру, соответствующую схеме А. ( defu A ( k ) ( co d ( ( > k 0 ) ( A ( - k 1 ) ) ( Li e 1 h ) ( B ( - k 1 ) ) ( Li e 0 ( 2 h ) ) ( D ( - k 1 ) ) ( Li e 7 h ) ( A ( - k 1 ) )))) Эта процедура инициируется главной программой по одному разу для каждой кривой Серпинского, образующих приведенный рисунок. Употребление явного параметра для уровня гарантирует окончание работы, так как глубина рекурсии не может быть больше k. Главная программа строится по образцу S. Ее задача - установить начальную точку кривой, т.е. исходные координаты пера (Px и Py) и единичную длину приращения h. Квадрат, где рисуется кривая, помещается в середине экрана, заданной ширины и высоты. Графическое изображение полученного алгоритма представлено в следующем разделе (Рисунок 3).
По сравнению с таким рекурсивным построением эквивалентные программы, где избегали употребления рекурсии, выглядят крайне сложными и запутанными. Схема алгоритма Рисунок 3 Схема алгоритма главной процедуры Рисунок 4 Схема алгоритма процедуры A Текст программы ;; SIERPI S.LSP для XLISP версии 2.1 ;; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ;; Программа построения кривых Серпинского i-го порядка. ;; ;; ЗАПУСК: > (Sierpi skiCurve 4) ;; ;; Замечание: Переменная VMode управляет установкой видео режима, ;; и по умолчанию установлена в значение 18. ;; Эта установка соответствует режиму 640x480 Color, ;; и работает на большинстве систем. В случае проблемы ;; с установкой этого режима необходимо выбрать ;; значение этой переменной в соответствии с документацией ;; на оборудование. ;; ( defvar VMode 18 ) ;Видео режим по умолчанию ( defvar MaxX 640 ) ;Максимальная ширина экрана по умолчанию ( defvar MaxY 480 ) ;Максимальная высота экрана по умолчанию ( defvar SquareSize 256 ) ;Размер области для построения ;; ;; Функция инициализирует графический режим, устанавливает переменные ;; MaxX MaxY SquareSize в соответствии с выбранным режимом ;; ( defu I i Graph() ( case VMode ( 4 ;320x200 Color ( mode 4 ) ( se q MaxX 320 MaxY 200 SquareSize 128 ) ) ( 16 ;640x350 Color ( mode 16 ) ( se q MaxX 640 MaxY 350 SquareSize 128 ) ) ( 18 ;640x480 Color ( mode 18 ) ) ( 106 ;800x600 Color ( mode 106 106 800 600 ) ( se q MaxX 800 MaxY 600 SquareSize 512 ) ) ( ( error U suppor ed graphics mode: VMode ) ) ) ) ;; ;; Функция реализует задержку на заданное время ;; ( defu pause ( ime ) ( le ( ( fi ime ( ( ime i er al- ime-u i s-per-seco d ) ( ge -i er al-ru - ime ) ) ) ) ( loop ( whe ( > ( ge -i er al-ru - ime) fi ime ) ( re ur -from pause ) ) ) ) ) ;; ;; Функция целочисленного деления ;; ( defu div ( a b ) ( rou d ( / a b ) ) ) ;; ;; Функция рисования прямой: ;; Параметры: &l ;Direc io > - направление рисования (0-7) ;; &l ;Size> - длинна прямой ;; ( defu Li e( Direc io Size ) ( se q x Px y Py ) ( case Direc io ( 0 ( se q x ( x Size) ) ) ( 1 ( se q x ( x Size ) y ( - y Size ) ) ) ( 2 ( se q y ( - y Size) ) ) ( 3 ( se q x ( - x Size ) y ( - y Size ) ) ) ( 4 ( se q x ( - x Size) ) ) ( 5 ( se q x ( - x Size ) y ( y Size ) ) ) ( 6 ( se q y ( y Size) ) ) ( 7 ( se q x ( x Size ) y ( y Size ) ) ) ) ( move Px Py x y ) ( se q Px x Py y ) ) ;; ;; Функции A, B, C, D - рекурсивные функции рисования ;; ( defu A ( k ) ( co d ( ( > k 0 ) ( A ( - k 1 ) ) ( Li e 1 h ) ( B ( - k 1 ) ) ( Li e 0 ( 2 h ) ) ( D ( - k 1 ) ) ( Li e 7 h ) ( A ( - k 1 ) ) ) ) ) ( defu B ( k ) ( co d ( ( > k 0 ) ( B ( - k 1 ) ) ( Li e 3 h ) ( C ( - k 1 ) ) ( Li e 2 ( 2 h ) ) ( A ( - k 1 ) ) ( Li e 1 h ) ( B ( - k 1 ) ) ) ) ) ( defu C ( k ) ( co d ( ( > k 0 ) ( C ( - k 1 ) ) ( Li e 5 h ) ( D ( - k 1 ) ) ( Li e 4 ( 2 h ) ) ( B ( - k 1 ) ) ( Li e 3 h ) ( C ( - k 1 ) ) ) ) ) ( defu D ( k ) ( co d ( ( > k 0 ) ( D ( - k 1 ) ) ( Li e 7 h ) ( A ( - k 1 ) ) ( Li e 6 ( 2 h ) ) ( C ( - k 1 ) ) ( Li e 5 h ) ( D ( - k 1 ) ) ) ) ) ;; ;; Главная процедура ;; Параметры: &l ;Cou > - количество итераций ;; ( defu Sierpi skiCurve ( Cou ) ( I i Graph ) ;Установка графического режима ( se q h ( div SquareSize 4 ) ) ;Вычисление длины линии ( se q x0 ( div MaxX 2 ) ) ;Вычисление начальной точки ( se q y0 ( ( div MaxY 2 ) h ) ) ;для рисования ( ;Основной цикл do (( i 1 )) ;Инициализация счетчика (( eql i ( Cou 1 ) ) 'Do e ) ;Условие завершения ( se q x0 ( - x0 h ) ) ;Вычисление координат начальной ( se q h ( div h 2 ) ) ;точки для рисования и ( se q y0 ( y0 h ) ) ;единичной длины линии ( se q Px x0 Py y0 ) ;Установка пера ( color i ) ;Установка цвета для рисования ( A i ) ( Li e 1 h ) ;Рисование ( B i ) ( Li e 3 h ) ( C i ) ( Li e 5 h ) ( D i ) ( Li e 7 h ) ( pause 1.0
) ;Задержка ( se q i ( i 1 )) ;Инкримент счетчика ) ;Конец основного цикла ) ( pri ry (Sierpi skiCurve 4) ) ;Подсказка Руководство пользователя Требования к системе: x86 персональный компьютер (386 минимум; 486, Pe ium, или Pe ium Pro рекомендуется) Microsof DOS 3.30 или выше Microsof Wi dows 3.1, Microsof Wi dows for Workgroups, Microsof Wi dows 95, Microsof Wi dows 3.51 или 4.0 512 Kb RAM 5 Kb свободного пространства на жестком диске Установленный интерпретатор XLisp версии 2.1 или выше Для запуска программы необходимо: Включить компьютер Загрузить интерпретатор XLisp c параметром “Sierpi s.lsp”: C:XLISPXLISP.EXE SIERPI S.LSPÃ В ответ на приглашение XLisp ввести: (Sierpi skiCurve 4)Ã Тест программы Тест проводился на рабочей станции со следующей конфигурацией: Pe ium 166 32 Mb RAM Sy cMas er 17Glsi S3 rio64V Wi dows 95 Интерпретатор XLisp был запущен в окне MS-DOS. Программа тестировалась при значениях параметра Cou от 1 до 4. В результате тестов были получены следующие изображения на экране монитора: Рисунок 5 Рисунок 6 Рисунок 7 Рисунок 8 Литература “Алгоритм структура данных = программа”, H.Вирт “XLisp-Plus 2.1 Programmers Ma ual”, David Michael Be z
Авторы не согласны с этим утверждением. Разработка программ призвана быть инженерной дисциплиной. Однако это не исключает индивидуального мастерства. Достаточно вспомнить о больших соборах, построенных в Европе в средние века. Для каждого из них потребовались тысячи человеко-лет усилий, прилагаемых на протяжении десятилетий. Приобретенный опыт передавался следующему поколению строителей, которые своими достижениями двигали строительную технику вперед. Но плотники, каменотесы, резчики по дереву и стекольщики оставались мастерами, преобразующими требования для создания единого целого, что выходило за границы чисто механической стороны строительства. Именно вера в их личный вклад не давала замереть этим проектам: Отесывая камни, всегда думай о соборах, которые будут строиться из них. Кредо средневекового каменотеса В общей структуре проекта всегда найдется место индивидуальности и мастерству. Это утверждение особенно верно, если учитывать сегодняшнее состояние программирования. Через сотню лет современные методы программирования могут показаться такими архаичными, какими сегодня кажутся методы строительства средневековых соборов, тогда как наше мастерство по-прежнему будет в почете
1. Исследование кривых и поверхностей второго порядка
3. Кривые второго порядка. Квадратичные формы
4. Поверхности второго порядка
5. Поверхности второго порядка
9. Стандарты сотовой связи 1-го и 2-го поколений. Организация хэндовера
10. Разработка программы на языке LISP для построения кривых Серпинского i-го порядка
14. Решение дифференциальных уравнений 1 порядка методом Эйлера
18. Нормы ГК, которые определяют особенности порядка заключения договоров по недвижимости
20. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка
25. Крива LM. Сутнiсть, графiчна побудова. Фактори, що впливають на кут нахилу кривоi LM
26. США: от экспансии в прошлом к новому «мировому порядку» в будущем
27. Создание термоядерного оружия в СССР: второй этап ядерной гонки
28. Анализ дискретного фильтра II порядка
29. Алгоритм компактного хранения и решения СЛАУ высокого порядка
31. Хроногеометрия несвязных гранично однородных порядков в аффинном пространстве
34. Кривые линии и поверхности
35. О порядке определения и способе установления ставок платы за землю поселений
37. Роль и место органов местного самоуправления в осуществлении охраны общественного порядка
41. Маркетинг и кривые равновесия
42. Кривые Энгеля и их новая интерпретация
43. Критика неолиберального порядка
44. Кривые спроса, предложения и доход
46. Конституционные основы правосудия при защите прав в порядке гражданского судопроизводства
47. ФСС: О некоторых вопросах порядка проведения камеральных проверок
48. Производство в порядке надзора
52. Кривизна плоской кривой. Эволюта и эвольвента
60. Исследование процессуального порядка привлечения лица в качестве обвиняемого
62. Охрана общественного порядка и обеспечение общественной безопасности на объектах транспорта
63. Пересмотр в порядке надзора судебных постановлений, вступивших в законную силу
64. Пересмотр судебных актов в порядке надзора и по вновь открывшимся обстоятельствам
66. Предупреждение и пресечение административных правонарушений против порядка управления
68. Процессуально-правовые последствия несоблюдения порядка предъявления иска
69. Разрешение жалоб в административном порядке
73. Основные принципы построения сети 1-WIRE
74. Розв’язання задачі Коші для звичайного диференціального рівняння першого порядку методом Ейлера
75. Чисельне інтегрування та наближення функцій поліномами вищого порядку
76. Кривий Ріг у роки Великої Вітчизняної війни
77. Дефокусировка. Сферическая аберрация 3 порядка. Кома и неизопланатизм
78. Аналитические свойства решений системы двух дифференциальных уравнений третьего порядка
80. Пересечение кривых поверхностей
84. Особенности хозяйственного порядка Украины
85. Когрентність другого порядку як об’єкт експериментального дослідження
90. О порядке регулирования, формирования и утверждения тарифов на платные медицинские услуги
91. Перераспределение бюджета. Кривая производственных возможностей
92. Авиация Второй мировой войны
93. Отчёт по лабараторным работам по биологии за 1 семестр
95. ГО Правила поведения и действия населения в очагах поражения
96. Оповещение о чрезвычайных ситуациях. Сигналы оповещения ГО и действия населения по ним
97. Применение ЭВМ для повышения эффективности работы штаба ГО РАТАП
98. Промышленное производство в Республике Беларусь в 90-х годах ХХ-го века
99. Геодезия и картография. Создание топографических карт и планов масштаба 1:5000