Анализ структур данных, выбранных для реализации алгоритма
Использование структур на примере решения задач аналитической геометрии
Цель работы:
1. Получить навыки выбора и обоснования выбора структур данных при написании программ на примере решения задач аналитической геометрии.
2. Получить навыки работы со структурами.
Задание:
1. Согласно заданному варианту описать методы решения задачи.
2. На основе описанных методов разработать математическую модель.
3. Привести обоснование выбора структур данных, использованных при разработке программы.
4. Разработать алгоритм решения задачи и закодировать его на языке программирования.
Содержание отчета:
1. Математическая постановка задачи.
2. Описание и анализ методов решения (если приведено более одного метода).
3. Анализ структур данных, выбранных для реализации алгоритма.
4. Постановка задачи (описание входных, выходных, дополнительных данных, ограничения на входные данные).
5. Алгоритм.
6. Листинг программы
7. Тестовые примеры (несколько вариантов исходных данных и результаты работы программы для указанных данных).
Пример выполнения лабораторной работы
Формулировка задачи:
На плоскости задано множество точек. Подсчитать количество остроугольных треугольников, которые можно построить на этом множестве.
Математическая постановка задачи.
Точка на плоскости задается парой координат (х,у).
Треугольником является плоская фигура, состоящая из отрезков, соединяющих три точки на плоскости, при условии, что эти точки не лежат на одной прямой.
Остроугольным называется треугольник, у которого каждый из углов при вершине треугольника не превышает 90°.
Обозначим через a, b, c стороны треугольника, построенного по произвольным трем точкам множества; А, В, С – углы треугольника при соответствующих сторонах (см. рис.1); р – полупериметр треугольника.
 |
Описание методов решения.
Решить данную задачу можно несколькими способами
а) используя теорему косинусов:
; 
; 
;
находим значения углов через функцию arccos;
б) используя формулы половинных углов:
пример для угла А:
, либо 
, либо 
,
находим значение половинного угла через соответствующую обратную функцию и умножаем полученное значение на 2.
Углы рассчитаем по формулам:
; 
;
,
где р – полупериметр текущего треугольника со сторонами, длины которых равны а, b и c.
.
Длины сторон вычисляются по формулам:
; 
; 
,
где 
- координаты текущей тройки точек, по которым строится треугольник, причем точки не лежат на одной прямой.
Уравнение прямой, проходящей через две точки с координатами 
:
,
или, по свойству пропорции:
.
Чтобы определить, лежит ли третья точка 
на прямой, необходимо подставить ее координаты в уравнение:
.
При переборе точек множества необходимо избегать дублирования комбинаций трех точек, поэтому индексы должны изменяться следующим образом:
Геометрическое решение.
Вариант задачи для множества из четырех точек представлен на рис. 2.
Возможные комбинации точек и решения:
{(х1, у1), (х2, у2), (х3, у3)} – точки лежат на одной прямой и не образуют треугольник.
{(х1, у1), (х2, у2), (х4, у4)} – точки образуют остроугольный треугольник.
{(х1, у1), (х3, у3), (х4, у4)} – точки образуют тупоугольный треугольник.
{(х2, у2), (х3, у3), (х4, у4)} – точки образуют тупоугольный треугольник.
Итого: количество остроугольных треугольников, которые можно построить на данном множестве – 1.
 |
Анализ структур данных, выбранных для реализации алгоритма.
Входные данные.
Количество точек nÎN, поэтому в алгоритме представляется целым типом:
n:цел.
Прежде чем рассматривать представление множества точек, рассмотрим представление одной точки. Поскольку координаты точки принадлежат множеству R, то им соответствует вещественный тип данных. Координаты одной точки можно представить:
а) как две отдельные переменные:
х,у: вещ.;
б) как запись:
точка = запись (х,у:вещ.)
Множество точек можно представить следующим образом.
1. Для хранения используется набор отдельных переменных:
а) 2*n переменных вещественного типа:
х1,х2,х3...хn,у1,у2,у3...уn:вещ.
б) n переменных типа «точка»:
t1,t2,t3...tn:точка.
Недостаток этого способа – невозможность автоматизации обработки при большом количестве точек.
2. Для хранения используется один или несколько массивов, что позволяет автоматизировать обработку при большом количестве точек:
а) х,у: массив [n] вещ.
б) t: массив [n] типа «точка».
Достоинство способов а) и б)– мнемоничность переменных.
в) t: массив[n][2]вещ.
t[i][1] соответствует текущей координате х, t[i][2] – текущей координате у.
Недостаток этого способа– название элемента не отражает его смысл.
Недостаток представления множества в виде массива элементов – большой объем памяти, используемый для хранения элементов.
3. На каждом шаге обработки можно хранить только текущие три точки множества (либо в виде переменных вещественного типа, либо в виде записей типа «точка»). Достоинство – малый объем занимаемой памяти. Однако, поскольку обработка точек предполагает нелинейный перебор (каждая точка с каждой без учета повторений), то при обработке очередной тройки точек пришлось бы заново вводить ранее введенные значения, что ухудшает работу алгоритма, снижает быстродействие и повышает вероятность возникновения ошибок при вводе данных.
Выходные данные.
Количество треугольников ÎN, поэтому в алгоритме представляется целым типом:
K: цел.
Промежуточные данные.
Согласно выбранному методу решения, для определения параметров текущего треугольника необходимо вычислить следующие величины:
- длины сторон треугольника;
- полупериметр треугольника;
- углы треугольника.
Все эти величины принадлежат множеству действительных чисел, поэтому представляются вещественным типом.
1. Эти данные можно хранить в виде соответствующих массивов из n элементов:
а,b,c: массив [n] вещ. { длины сторон треугольников };
p: массив [n] вещ. { полупериметры треугольников};
angle_A, angle_B, angle_C: массив [n] вещ. { углы треугольников }.
Недостаток – необходим большой объем памяти для хранения данных.
2. Поскольку при обработке текущего треугольника данные о параметрах предыдущих треугольников нам не нужны, то логично хранить только данные одного треугольника:
а,b,c: вещ. { длины сторон текущего треугольника };
p: вещ. { полупериметртекущего треугольника };
angle_A, angle_B, angle_C: вещ. { углы текущего треугольника }.
Достоинство – небольшой объем памяти, необходимый для хранения данных.