АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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.5 0

 

Тест4. (Наложение ребра)

 

   
   
0.2  
0.8  
   
   

 

Правильные результаты:

отрезок пересечения:

[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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.)