Лабораторный практикум по информатике
жүктеу/скачать 1,1 Mb.
|
- Бұл бет үшін навигация:
- Векторным произведением
- Задача 1. «Штраф за левые повороты»
| Скалярное произведение двух векторов – это число, равное про- изведению модулей этих векторов на косинус угла между ними, (a,b) = |a| · |b| · cos φ. Если вектор a имеет координаты (x1, y1), а вектор b координаты – (x2, y2), то скалярное произведение вычисляется по фор- муле (a,b) = x1 · x2 + y1 · y2.
Рис. 16.1. Иллюстрация к скалярному произведению векторов Заметим, что если угол φ острый, то скалярное произведение (a, b) > 0, если угол φ тупой, то (a, b) < 0. Если два вектора перпендику- лярны, то их скалярное произведение равно нулю. Векторным произведением двух векторов a и b называется вектор [a × b], такой, что длина его равна |[a × b]| = |a| · |b| · sin φ; вектор [a × b] перпендикулярен векторам a и b; вектор [a × b] направлен так, что из его конца кратчайший поворот от a к b виден происходящим против часовой стрелки. Длина векторного произведения равна площади параллелограмма, построенного на векторах a и b. Через координаты векторов a и b векторное произведение выража- ется следующим образом: i [a × b] = x1 x2 j k y1 z1 y2 z2 = (y1 · z2 – z1 · y2) i + (x1 · z2 – z1 · x2) j + (x1 · y2 – y1 · x2) k, где i, j, k – единичные вектора осей Ox, Oy, Oz соответственно. При решении задач на плоскости координаты z1 и z2 равны нулю. В этом случае [a × b] = (x1 · y2 – x2 · y1)· k. Если вектор a образует с осью Ох угол α, а вектор b – угол β, то для ска- лярного произведения справедлива формула [a × b] = (|a| · |b| · sin(β – α))· k. Это означает, что для ненулевых векторов векторное произведение равно нулю тогда и только тогда, когда векторы параллельны. Если поворот от вектора а к вектору b по наименьшему углу выполняется против часовой стрелки, то [a × b] > 0, если по часовой стрелке, то [a × b] < 0. Рис. 16.2. Иллюстрация к векторному произведению Рассмотрим задачи, при решении которых используются скалярное и векторное произведения. Задача 1. «Штраф за левые повороты» [1]. В городе Х водителям запрещено выполнять левые повороты. За каждый такой поворот во- дитель должен уплатить штраф в размере М рублей. Для слежки за водителями в городе установлена компьютерная система, фикси- рующая координаты автомобиля в начале движения, в конце движения и во время поворота. Исходные данные: N – количество зафиксированных координат авто- мобиля, (xi, yi) – координаты автомобиля в процессе движения, i = 1, 2, …, N, где (x1, y1) – точка начала движения, (xN, yN) – последняя точка маршрута автомобиля. Требуется по заданной последовательности координат движения вычислить сумму штрафа водителя. (xi+1, yi+1) (xi, yi) (xi-1, yi-1) Рис. 16.3. Иллюстрация к задаче «Штраф за левые повороты» Траекторию движения автомобиля можно представить в виде ло- маной, состоящей из направленных отрезков из точек (xi, yi) в точки (xi+1, yi+1), i = 1, 2,…, N–1. Поворот считается левым, если направление текущего отрезка пути ai+1 меняется относительно предыдущего отрезка ai в левую сторону, т. е. против часовой стрелки. Таким образом, решение задачи сводится к вычислению количества пар участков пути ai и ai+1, для которых выполняется условие [ai × ai+1] > 0. Координаты векторов ai и ai+1 вычисляются через координаты точек (xi, yi): ai = (xi – xi–1, yi – yi–1), ai+1 = (xi+1 – xi, yi+1 – yi), следовательно, [ai × ai+1] = (xi – xi–1) (yi+1 – yi) – (yi – yi–1)(xi+1 – xi), i = 2, …, N – 1. жүктеу/скачать 1,1 Mb. Достарыңызбен бөлісу:
|