Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» icon

Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование»






Скачать 98.12 Kb.
НазваниеПояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование»
Фоминых М. А
Дата конвертации21.07.2013
Размер98.12 Kb.
ТипТехническое задание
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«Поволжский государственный технологический университет»

(ФГБОУ ВПО «ПГТУ» )


Кафедра ИиСП


Пояснительная записка к Курсовой работе

по дисциплине

«Функциональное и логическое программирование»


РАЗРАБОТАЛ:

Ст. ПС-31

Фоминых М. А.

ПРОВЕРИЛ:

ассистент кафедры ИиСП

Хованский В. П.


Йошкар-Ола

2012

Содержание



Содержание 2

5

5

Исходное изображение считается некорректным если найдено количество квадратов неравное пяти, или же вообще не найдено квадратов. 5





  1. Техническое задание

Дана рабочая плоскость (представленная в виде стандартного файла Windows DIB), содержащая некоторые непересекающиеся геометрические фигуры (круг, квадрат, треугольник и т.п). Необходимо идентифицировать указанные в индивидуальном задании фигуры, определить их положение, размер, проанализировать, отсортировать и преобразовать в фигуры другого вида. Считаем, что толщина линий контура геометрических фигур равна единице. Для выполнения работы использовать следующие средства:

  • Microsoft Visual Studio 2008.

  • FSharp.

  • clisp.exe или любое другое инструментальное средство языка Lisp.

  • txt2bmp.exe – осуществляет преобразование файлов форматов bmp, png в текстовый файл и наоборот. Можно использовать другие исполняемые программы.



Требуется написать программу на языке ЛИСП и батник:

Программа, написанная на языке LISP:

  1. Считывает текстовый файл в память.

  2. Идентифицирует фигуры.

  3. Преобразует фигуры.

  4. Выводит на консоль текстовую информацию (какие фигуры распознаны, преобразованы с указанием координат и размеров).

Батник выполняет следующие действия:

    1. Запускает txt2bmp.exe – осуществляет преобразование графического файла в текстовый файл.

    2. Запускает программу, написанную на языке LISP.

    3. Запускает txt2bmp.exe – осуществляет преобразование текстового файла в графический файл.

Кроме этого необходимо выполнить следующие пункты:

  1. Программа должна корректно обрабатывать нештатные ситуации

  2. Программа должна отображать информацию об авторе программы, текст общего задания, вариант задания, текст задания согласно варианту.

Вариант 23

На указанной плоскости идентифицировать 5 квадратов и преобразовать в окружности (окружность должна быть вписанной в квадрат), причем, второй по величине квадрат оставить без изменения.

Пример корректных исходных данных:

d:\мои документы\учеба\филп\курсач\3\test\1.png

Вывод:

d:\мои документы\учеба\филп\курсач\3\test\1a.png

Пример некорректных исходных данных:

d:\мои документы\учеба\филп\курсач\3\4.png


Вывод:

d:\мои документы\учеба\филп\курсач\3\4.png

Исходное изображение считается некорректным если найдено количество квадратов неравное пяти, или же вообще не найдено квадратов.




  1. Руководство программиста

Общее описание алгоритма

  • Чтение данных из файла и занесение их в список. Список представляет собой упорядоченное множество списков, содержащих строки, считанные из файла.

  • Рекурсивно вызывается процедура нахождения фигур, пока все фигуры не будут найдены и идентифицированы.

  • Найденная фигура проверяется на замкнутость. В зависимости от результата выводится сообщение о том, замкнутая ли фигура найдена. Параллельно находятся крайние точки фигуры, они тоже выводятся в консоль.

  • Если фигура замкнута, то программа проверяет, является ли фигура квадратом, параллельно находим для квадрата центр и радиус вписанной окружности. Результат проверки выводится в консоль.

  • Если фигура – квадрат, то счетчик квадратов увеличивается на единицу, а центр и радиус вписанной окружности квадрата заносим в список. Далее ищем новые фигуры.

  • Если мы нашли строго пять квадратов, то пробегаемся по списку с данными о квадратах и находим второй по величине.

  • Во все кроме второго по величине квадрата вписываем окружности. Вывод сообщения о том, что окружности отрисованы.

  • Записываем измененный список строк в выходной файл.



Алгоритм поиска фигур

После чтения из файла данные хранятся в списке списков (image). Запускается функция Search, которая находит и идентифицирует фигуры, вызывая себя рекурсивно. Поочередно проходя по каждому элементу каждого списка, функция FindPoint ищет первое вхождение единицы. Как только единица найдена, считается, что обнаружена фигура, далее происходит ее идентификация. Первая найденная точка считается самой верхней, т.к. поиск идет слева направо снизу вверх.

Проверка фигуры на замкнутость

Как только найдена единица, рекурсивно запускается проверка на замкнутость (функция CheckForClosure). Значение ячейки, координаты которой были переданы в процедуру проверки, заменяется на двойку, с помощью функции SetValue. Поочередно по часовой стрелке, начиная с левой, проверяются значения соседних ячеек, как только находится единица, запускается проверка соседей уже для этой точки и т. д., пока мы не вернемся в первоначальную точку или же среди соседей не будет ни одной единицы. Если мы смогли вернуться в первоначальную точку, то фигура считается замкнутой.

Для экономии времени в этом же проходе по ячейкам определяются крайние точки фигуры, как то: самая верхняя, самая правая, самая нижняя и самая левая, A, B, C и D соответственно.

Проверка на «квадратность»

Если фигура замкнута, то запускается проверка на то, является ли найденная фигура квадратом. Запускается функция CheckSquare, в которую передаются крайние точки фигуры. Сперва проверяются на кривизну линии, находящиеся между крайними точками фигуры (верхней и правой, правой и нижней, нижней и левой, левой и верхней, это отрезки AB, BC, CD, DA соответственно). Для этого программа находит угловые коэффициенты для уравнений прямых, по координатам точек, через которые должны проходить эти прямые. Угловой коэффициент прямой, проходящей через две данные точки, определяется по формуле . Добавочная константа находится подставлением в уравнение прямой
y = kx+b координат одной из точек, при соответствующем угловом коэффиценте, и решением этого уравнения.

Константа и угловой коэффициент, а так же две точки (point и finish), через которые должна проходить прямая передаются в функцию PointOnLine, которая работает аналогично функции CheckForClosure, пробегаясь по всем точкам фигуры, но при этом подставляет координату x, найденных точек, в уравнение прямой, и сравнивает получившееся значение функции с координатой y, данной точки. Если значение функции попадает в интервал (y-2; y+2), то считается, что найденная точка принадлежит прямой.

Однако, в случае если прямая параллельна оси oy, возникает деление на ноль, т. к. координата x является константой. В этом случае флаг divisionByZero приравнивается к единице, а функция PointOnLine сравнивает координату x, найденной точки (point), с координатой x, конечной точки отрезка (finish). Аналогично, если точка в окрестности, то она принадлежит прямой.

Функция PointOnLine заканчивает свою работу, когда мы пришли в конец отрезка или же когда одна из точек не принадлежит отрезку. Если отрезок является прямым, то в консоль выводится соответствующее сообщение. Как только найден кривой отрезок, идентификация прекращается, выводится сообщение о том, что фигура не является квадратом.

Если все отрезки прямые, то вычисляются длины диагоналей AC и BD. для этого вычисляются вектора (из координат конца вычитаются координаты начала), а затем находятся длины векторов по формуле . Длины сравниваются, с аналогичной погрешностью ±2. Если длины отличаются, то выводится соответствующее сообщение и идентификация прекращается.

Если длины диагоналей равны, то проверяется их перпендикулярность. Векторы перпендикуляры, если их скалярное произведение равно 0. В программе скалярное произведение должно находиться в промежутке
(-0,1; 0,1), это примерно 85°-95°. Скалярное произведение вычисляется по формуле . Если диагонали перпендикулярны, то фигура считается квадратом и в консоль выводится соответствующее сообщение, иначе фигура квадратом не считается и в консоль выводится сообщение об этом.

В случае, если фигура – квадрат, программа находит центр и радиус вписанной окружности, а затем заносит их в список с информацией о найденных квадратах (quades), а так же увеличивает счетчик квадратов на единицу. Центр окружности находится путем прибавления к координатам точки A (верхняя точка) половины вектора AС. Радиус же будет равен половине длины любой из сторон квадрата.

Нахождение второго по величине квадрата

Если число найденных квадратов равно 5, то программа находит второй по величине квадрат и рисует окружности для каждого квадрата кроме него, иначе окружности рисоваться не будут. Эти действия выполняет функция FindSecondQuadeAndDrawCircles.

Для того, чтобы найти второй по величине квадрат программа пробегается по списку с данными о квадратах и, сравнивая их радиусы вписанной окружности, сперва находит квадрат с максимальным радиусом (maxRadius), а затем, еще раз пробегаясь по списку, находит наибольший, но не равный максимальному радиус (secondRadius). Затем, в третий раз пробегаясь по списку, программа рисует окружности для каждого квадрата, чей радиус не равен второму по величине.

Отрисовка вписанной окружности

Рисование окружности выполняет функция DrawCircle, в нее передаются центр и радиус окружности. Функция в цикле меняет координату x, от x-R до x+R, (где R – это радиус вписанной окружности) с шагом 0,01. Для каждого x вычисляется y по уравнению окружности . Как x, так и y округляются до ближайшего целого и ячейке с координатами (x; y) присваивается значение 4.

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

Поведение в некорректных ситуациях

Как уже говорилось выше, программа продолжает дальнейшую работу только в корректных ситуациях. Приложение находит только квадраты, и, согласно условию, если квадратов будет не 5, то ситуация будет считаться некорректной, а значит, окружности не будут вписаны в имеющиеся квадраты.


Блок-схема алгоритма всей рпограммы





  1. Руководство пользователя

Примеры входных и выходных данных

Файл run.bat поочередно запускает программу для четырех входных изображений. Исходное изображение считается некорректным если найдено количество квадратов неравное пяти, или же вообще не найдено квадратов. Далее приведены первые два примера (корректный и некорректный), ввода и вывода программы.

Корректная ситуация. Изображение 1.png

d:\мои документы\учеба\филп\курсач\3\test\1.png

Вывод. Изображение 1a.png

d:\мои документы\учеба\филп\курсач\3\test\1a.png

Вывод информации в консоли:

d:\мои документы\учеба\филп\курсач\3\111.png


Некорректная ситуация. Изображение 2.png

d:\мои документы\учеба\филп\курсач\3\test\2.png

Вывод. Изображение 2a.png

d:\мои документы\учеба\филп\курсач\3\test\2.png


Вывод информации в консоли:

d:\мои документы\учеба\филп\курсач\3\222.png

Заключение

Была написана программа, которая идентифицирует 5 квадратов и преобразовывает их в окружности (окружность вписана в квадрат), причем, второй по величине квадрат оставлен без изменения.

Программа соответствует всем требованиям, описанным в постановке задачи, а так же правильно ведет себя в некорректных ситуациях.

Алгоритм был реализован на языке программирования Lisp. Данная курсовая работа позволила применить на практике знания, которые были получены на курсе “Функциональное и логическое программирование” и изучить алгоритмы распознавания и преобразования фигур.


Список использованной литературы

  1. http://ru.wikipedia.org/wiki/Окружность

  2. http://ru.wikipedia.org/wiki/Прямая

  3. http://ru.wikipedia.org/wiki/Скалярное_произведение

  4. Материалы лекции по дисциплине «Функциональное и логическое программирование» (http://wiki.margtu.ru/index.php?wakka=HomePage/20112012/3kurs/FILP/Lections&v=urx)

Ваша оценка этого документа будет первой.
Ваша оценка:

Похожие:

Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПроектирование базы данных «Тренажёрный зал»
245.1kb.   Задание на курсовую работу по дисциплине «Функциональное и логическое программирование»
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе по дисциплине «Объектно-ориентированное программирование»
236.6kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе по дисциплине “Программирование” на тему “Расчет макроэкономических индексов цен”
168.5kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе по дисциплине «Программирование» на тему: «Создание программы для работы с последовательностями»
376.1kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconШаблон иерархической структуры данных в памяти Пояснительная записка к Курсовой работе по дисциплине «Объектно-ориентированное программирование»
175.2kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconАлгоритм Форда-Фалкерсона по дисциплине Программирование
162.4kb.   Пояснительная записка к курсовой работе: 18с., 5 рис., 0 табл., 3 разделов, 2 приложения
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе по курсу «Системное программирование»
400.6kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе по курсу «Системное программирование»
424.6kb.  
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка (релиз).docx
510.8kb.   Пояснительная записка к курсовой работе по дисциплине «теория электрической связи»
Пояснительная записка к Курсовой работе по дисциплине «Функциональное и логическое программирование» iconПояснительная записка к курсовой работе По дисциплине «Методы оптимизации»
146.5kb.  
Разместите кнопку на своём сайте:
Рефераты


База данных защищена авторским правом ©CoolReferat 2000-2018
обратиться к администрации | правообладателям | пользователям
Основная база рефератов
Рефераты