|
||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Data 1, 2, 3, 4
Data 1, 2, 4, 3 Data 1, 3, 2, 4 Data 1, 2, 4, 3 Data 1, 4, 2, 3 Data 1, 4, 3, 2 tchks: 'координаты точек Data 0, 0 Data 0, 3 Data 4, 0 Data 4, 3 Результаты выполнения на ЭВМ приведенной программы: координаты точек: 0 0 4 0 4 3
маршруты: длина: 1 2 3 4 16 1 2 4 3 14 1 3 2 4 18 1 2 4 3 14 1 4 2 3 18 1 4 3 2 16 максимальный маршрут: 1 3 2 4 длина =18 минимальный маршрут: 1 2 4 3 длина = 14
Четвертую задачу можно отнести к геометрическим задачам, решение которых опирается на некоторые геометрические законы и свойства. Эта задача наиболее сложная среди рассмотренных задач из-за необходимости привлечения определенных математических знаний для организации ее решения. Задача 4. «Ломаная». Найти все точки самопересечения разноцветной замкнутой линии, заданной на плоскости координатами своих вершин в порядке обхода ломаной. Данные о ломаной представляются таблицей:
Особенность этой задачи - большое число частных случаев, связанных с возможным вырождением или наложением отрезков ломанной линии. Именно эти ситуации и составляют содержание тестов, на которых большинство программ дают неправильные результаты. Приведем проверочные тесты: Tecт1. (Основной случай)
Правильные результаты: точки пересечения 0.5 0.5
Тест 2. (Основной случай)
Правильные результаты: точки пересечения: отсутствуют
Тест3. (Наложение вершины)
Правильные результаты: точки пересечения 0.5 0
Тест4. (Наложение ребра)
Правильные результаты: отрезок пересечения: [0.2, 0] - [0.8, 0] Для систематического конструирования алгоритмов и программы необходима разработка сценария диалога и описание метода решения поставленной геометрической задачи. Сценарий точек: <n> координаты точек: <k>: <x> <у> …….. точки пересечения: отрезок: <k> - <k+l> * отрезок: <1> - <1+1> точка: <х> <у> ……… отсутствуют
Метод решения данной задачи может быть основан на вычислении точек пересечения отрезков (х1, у1) - (x2, у2) и (х3, y3) - (х4, y4) как точек пересечения линий, проходящих через заданные отрезки, с помощью системы уравнений: (y2 – y1)×(x – x1) - (x2 – x1)×(y – у1) = 0; (у4 – у3)×(x – x3) - (x4 – x3)×(у – y3) = 0.
Решение этих уравнений может быть проведено вычислением определителей D, Dx, Dy приведенной системы уравнений:
(у2 – у1)×х - (х2 – х1)×у = (у2 – y1)×х1 - (x2 – x1)×y1; (у4 – y3)×х - (х4 – х3) ×у = (у4 – у3)×х3- (x4 – x3)×y3,
для которой будет справедлив следующий набор расчетных формул:
х = Dx/D; у = Dy/D; D = (у2 - у1)×(х4 - x3) - (x2 - x1)×(y4 - y3); Dx = [(y2 - yl)×xl - (х2 – x1)×y1] - (x4 – х3) - (x2 – x1)×[(y4 – y3)×x3 - (х4 – х3)×y3]; Dy = (у2 - у1)×[(у4 – у3)×х3 - (x4 - x3)×у3] - [(у2 – y1)×x1 - (х2 – x1)×y1]×(y4 – y3).
Факт пересечения пар отрезков может быть установлен из этих же уравнений подстановкой в правые части координат точек альтернативного отрезка и сравнением значений этих выражений. А именно отрезок [(х3, у3) - (х4, у4)] пересекает линию, проходящую через отрезок [(x1, y1) - (х2, у2)], если эти выражения имеют разные знаки:
(у2 - у1)×(х3 – x1) - (х2 – х1)×(y3 – у1) ´ (у2 - у1)×(х4 – x1) - (х2 – x1)×(y4 – y1) £ 0.
Соответственно, отрезок [(х1, у1) - (х2, у2)] пересекает линию, проходящую через отрезок [(х3, у3) - (х4, у4)], если аналогичные выражения имеют разные знаки:
(у4 – у3)×(х1 – х3) - (х4 – х3)×(у1 – у3)´(у4 – у3)×(х2 – х3) - (х4 – х3)×(у2 – у3) £ 0.
И наконец, самый тонкий момент - это частные случаи, когда отрезки ломаной оказываются на одной прямой линии. В этом случае отрезки либо вообще не пересекаются, либо имеют общую часть, которую можно определить из взаимного расположения отрезков на прямой. В последнем случае общая часть отрезков находится из взаиморасположения отрезков [(х1, у1) - (х2, у2)] и [(х3, у3) - (х4, у4)] на прямой. В данной ситуации взаиморасположение вершин отрезков можно выяснить, вычислив взаиморасположение между ними на прямой относительно отрезка [(х1, у1) - (х2, у2)] по следующим формулам:
d1 = 0; d2 = (х2 – х1)×(х2 – х1) + (у2 – у1)×(у2 - 1); d3 = (х3 – х1)×(x2 – х1) + (у3 - у1)×(у2 - 1); d4 = (х4 – х1)×(х2 – х1) + (у4 – y1)×(y2 - 1).
Если d2 < min (d3, d4) или max (d3, d4) < 0, то отрезки не пересекаются. В противном случае необходимо выделить и отбросить две крайние точки, и тогда оставшиеся две точки зададут общую часть этих отрезков. Опираясь на эти математические факты можно приступить к составлению алгоритмов и программы. Приведем программу, в которой установлено максимальное число точек nt = 200. Реальное число точек устанавливается при вводе исходных данных из перечня операторов data, записанных в конце текста программы. ¢ самопересечение ломаной nt = 200 Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |