Определение уравнения одной и двух прямых на плоскости. Составление рекурсивного алгоритма построения всевозможных простых замкнутых ломаных через n произвольных точек методом треугольника и его реализация с помощью языка программирования Turbo Pascal.
Аннотация к работе
Перечень основных процедур и функций, используемых в программахп.1 Идея метода п.2 Реализация на языке ПаскальФигура, образованная конечным набором отрезков, расположенных так, что конец первого является началом второго, конец второго - началом третьего и т.д., называется ломаной линией или просто ломаной (рис. Отрезки называются сторонами ломаной, а их концы - вершинами ломаной.Из курса геометрии известно, что любая прямая на плоскости XOY имеет уравнение (1)[2], где - постоянные. Пусть даны две произвольные точки и прямой l, тогда найдем уравнение прямой l, проходящей через эти точки. Воспользуемся уравнением (1). 1) Если то, уравнение(1) примет вид , т.е. прямая будет параллельна оси Оу или совпадать с ней. Замечание: так как коэффициенты а и с заданы не однозначно, поэтому в алгоритмах, использующих уравнение прямой используется только геометрическая интерпретация этого случая, т.е. тот факт если прямая проходит через две точки у которых первые координаты равны, то эта прямая параллельна оси Оу.Функция истина если три точки лежат на одной прямой. Идея: находим уравнение прямой l, проходящей через точки В и С, и проверяем на принадлежность точки Т прямой l . If ((B.x=C.x)and(B.x=T.x)) or ((B.y=C.y)and(B.y=T.y))then S_3:=true else if B.x=C.x then S_3:=false else begin k1:=(B.y-C.y)/(B.x-C.x); Идея: Если точка Т лежит на отрезке ВС, то она лежит на прямой проходящей через точки В и С, и заключена между ними. 2) если один конец отрезка совпадает с одним из концов другого отрезка, и других общих точек нет. п.2 Function Peres, на языке Turbo PascalИдея: Чтобы перебрать все возможные способы построения простой замкнутой прямой мы воспользовались следующим алгоритмом построения: 1. Зафиксировали одну из n точек, т.к. не имеет значение, какая точка будет начальной т.к ломаная замкнутая; Соединяя зафиксированную точку с одной из незанятых точек, получаем первую сторону ломаной. Затем соединение продолжаем рекурсивно полным перебором всех незанятых точек, при условиях: O Новую точку можно соединить с последней присоединенной точкой, если отрезок, соединяющий эти точки, не пересекает ни одну из уже построенных сторон ломаной; O Продолжаем построение до тех пор, пока есть незадействованные точки, O Если свободных точек нет и отрезок, соединяющий последнюю присоединенную точку с первой, не пересекает ни одну из сторон построенной ломаной то, построенная ломаная и этот отрезок будут образовывать искомую замкнутую ломаную.Гипотеза: Пусть через n произвольных точек плоскости проходит S прямых содержащих не менее чем по 4-ре точки из данных, тогда через эти n точек возможно провести простых замкнутых ломанных не более чем где ki - количество точек из данных точек лежащих на i прямой, . 2) Количество способов построения замкнутых ломанных т.к. не имеет значение какая вершина будет начальной. 3) Очевидно, что количество ПЗЛ будет не больше количества замкнутых ломаных. Рассмотрим случаи соединения точки А с точками на i прямой. Точку А можно соединить максимум с двумя точками, лежащих на этой прямой, чтобы выполнялись условия построения.Const n=10; {Задаем количество точек} m=400;{Длина стороны квадрата на котором расположены точки} {Сдвигает точки в массиве на 1 позицию влево начиная с n1 до n2} {Ищет основание перпендикуляра опущенного из точки Т на прямую проходящую через точки В ИС} If (B.x=C.x) then begin O.x:=B.x; O.y:=T.y end else begin k:=(B.y-C.y)/(B.x-C.x); Begin for i:=n1 to n2 do begin PIESLICE(Round(A[i].x), Round(A[i].
План
Содержание
Введение
Глава 1
§1. Понятие ломаной
§2. Прямая на плоскости
Глава 2
Введение
Перечень основных процедур и функций, используемых в программах
§1. Function Peres, Блок Схема п.2 Function Peres, на языке Turbo Pascal
Список литературы
Введение
Тема бакалаврской работы является "Простая замкнутая ломаная кривая" (ПЗЛ).
Актуальность : выбранной темы заключается в том, что теория ПЗЛ имеет практическое применение например: прокладывание газопровода, железнодорожных путей и т.д., но теория ПЗЛ не дает ответа как и сколькими способами это возможно сделать. В теории ПЗЛ дано лишь определение ПЗЛ и ее компонентов без выделения, каких либо свойств. А так решение проблемы выбранной темы является, частным случаем решения задачи Коммивояжера ее еще называют транспортной задачей.
Объект исследования: Планиметрия.
Предмет исследования: Простая замкнутая ломаная на плоскости.
Цели: Изучит понятие ПЗЛ, выделить его свойства и составить алгоритм построения.
Задачи: 1) Составить рекурсивный алгоритм позволяющий построить все возможные ПЗЛ через n произвольных точек плоскости (замечание эти точки должны быть вершинами ПЗЛ, и других вершин нет). Реализовать его в среде Turbo Pascal.
2) Дать верхнюю оценку количества способов построения ПЗЛ через n произвольных точек плоскости.
3) Составить не рекурсивный алгоритм и реализовать его на языке Turbo Pascal, позволяющий строить ПЗЛ для большого количества произвольных точек
Гипотезы: 1. ПЗЛ можно построить всегда, кроме случая когда все точки лежат на одной прямой.
2. Пусть через n точек проходят S прямых имеющих не менее 4-х данных точек, тогда через эти n точек можно провести не более чем различных ПЗЛ, где k i -количество точек принадлежащих i-ой прямой, i=1,2…S1. Фаронов Turbo Pascal 7.0.
2. Погорелов А.В. Геометрия: Учебное пособие для вузов. - 2-е изд. - М.: Наука. Главная редакция физико-математической литературы, 1984. - 288с.
3. Дискретная математика для программистов / Новиков Ф. А. - Спб.: Питер, 2001. - 304 с. :ил.