Файл: Практикум по информатике рекомендовано в качестве учебного пособия.docx

Общая часть задания: сформировать массив из 100 случайных чи- сел. Выполнить простой поиск элемента, подсчитать количество итера- ций. Отсортировать массив всеми рассмотренными методами и посчи- тать количество итерация для каждого метода. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сде- лать выводы.

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ ПОВЫШЕННОЙ СЛОЖНОСТИ

Для решения геометрических задач повышенной сложности необ- ходимо:

знать, как представляются на плоскости такие геометрические объ- екты, как точка, прямая, отрезок и окружность;
уметь находить уравнение прямой, соединяющей две заданные точки;
уметь определять координаты точки пересечения двух прямых;
знать, как провести перпендикуляр к прямой или определить, яв- ляются ли прямые параллельными;
уметь находить скалярное и векторное произведения;
находить площадь многоугольника;
уметь работать с фигурами на плоскости.

Напомним основные моменты, связанные с этими понятиями. Каждую точку плоскости можно считать вектором с началом в точ-

ке (0, 0). Обозначим через a= (x, y) вектор с координатами (x, y). Длина

вектора (его модуль) вычисляется по формуле a .

Скалярное произведение

двух векторов – это число, равное про- изведению модулей этих векторов на косинус угла между ними, (a,b) = |a| · |b| · cos φ. Если вектор a имеет координаты (x₁, y₁), а вектор bкоординаты – (x₂, y₂), то скалярное произведение вычисляется по фор- муле (a,b) = x₁ · x₂ + y₁ · y₂.

Рис.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] = ^x₁

x₂

j k

y₁z₁

y₂z₂
= (y₁ · z₂ – z₁ · y₂) i+ (x₁ · z₂ – z₁ · x₂) j+ (x₁ · y₂ – y₁ · x₂) k,

где i, j, k– единичные вектора осей Ox, Oy, Ozсоответственно.

При решении задач на плоскости координаты z₁ и z₂ равны нулю.

В этом случае [a× b] = (x₁ · y₂ – x₂ · y₁)· k.

Если вектор aобразует с осью Охугол α, а вектор b– угол β, то для ска- лярного произведения справедлива формула [a × b] = (|a| · |b| · sin(β – α))· k. Это означает, что для ненулевых векторов векторное произведение равно нулю тогда и только тогда, когда векторы параллельны. Если поворот от вектора ак вектору bпо наименьшему углу выполняется против часовой стрелки, то [a× b] > 0, если по часовой стрелке, то [a× b] < 0.

Рис.16.2.Иллюстрацияквекторномупроизведению

Рассмотрим задачи, при решении которых используются скалярное и векторное произведения.

Задача 1. «Штраф за левые повороты» [1]. В городе Х водителямзапрещено выполнять левые повороты. За каждый такой поворот во-дительдолженуплатитьштрафвразмереМрублей.Дляслежкиза водителями в городе установлена компьютерная система, фикси-рующая координаты автомобиля в начале движения, в конце движения

иво времяповорота.

Исходныеданные: N– количество зафиксированных координат авто- мобиля, (x_i, y_i) – координаты автомобиля в процессе движения, i= 1, 2, …, N, где (x₁, y₁) – точка начала движения, (x_N, y_N) – последняя точка маршрута автомобиля.

Требуется по заданной последовательности координат движения вычислить сумму штрафа водителя.

⁽^xi+1, ^yi+1⁾

(x_i_, y_i)
⁽^xi-1, ^yi-1⁾
Рис.16.3.Иллюстрациякзадаче«Штрафзалевыеповороты»

Траекторию движения автомобиля можно представить в виде ло- маной, состоящей из направленных отрезков из точек (x_i, y_i) в точки (x_i+1, y_i+1), i = 1, 2,…, N–1. Поворот считается левым, если направление текущего отрезка пути a_i₊₁ меняется относительно предыдущего отрезка a_iв левую сторону, т. е. против часовой стрелки.

Таким образом, решение задачи сводится к вычислению количества пар участков пути a_iи a_i₊₁, для которых выполняется условие [a_i× a_i₊₁] > 0. Координаты векторов a_iи a_i₊₁

вычисляются через координаты точек (x_i, y_i): a_i= (x_i_–x_i_–1, y_i_–y_i_–1), a_i₊₁ = (x_i₊₁ _– x_i, y_i₊₁ _– y_i), следовательно,

[a_i× a_i₊₁] = (x_i–x_i_–1) (y_i₊₁ –y_i) – (y_i_–y_i_–1)(x_i₊₁ – x_i), i= 2, …, N– 1.
Задача 2. «Здесь будет город-сад». Жители одного дома города Хрешиливысадитьусебяводворенесколькодеревьев.Таккакжильцыне смогли договориться, как должны быть расположены посадки, токаждый посадил дерево в том месте двора, где ему захотелось. Послепроведения посадок полученный сад решили обнести забором. Но покадоскинепривезли,деревьяобвязалиоднойдлиннойверевкой.

Исходная информация: N – количество деревьев в саду, (x_i, y_i) – ко- ординаты деревьев, i = 1, 2, …, N. Так как были высажены молодые са- женцы, то их толщиной можно пренебречь.

Требуется определить, к каким из посаженных деревьев надо при- вязать веревку так, чтобы все деревья оказались внутри обнесенной зо- ны, а длина веревки была минимальная.

Эта и подобные ей задачи сводятся к определению для заданного множества точек на плоскости выпуклой оболочки, то есть выпуклого многоугольника с вершинами в некоторых точках из заданного множе-

Смотрите также файлы

Вопросы а судоустройство.docx

Дисциплина Психологическое бизнесконсультирование Практическое задание 1, Модуль 1.doc

Реферат Особенности эмо на энергетических и промышленных объектах студент гр. Эд43 Мамаев А. Ю. Проверил.doc

Идентификаторлар(айнымалылар) атауы ріппен басталатын цифрлар мен ріптер тізбегі. Идентификатор латын ріптерінен, тменгі сызу табасы k1 жне 0 мен 9 арасындаы цифрлардан ралады..ppt

камчатский государственный технический университет.docx

Файл: Практикум по информатике рекомендовано в качестве учебного пособия.docx

Индивидуальное задание

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ ПОВЫШЕННОЙ СЛОЖНОСТИ

Смотрите также файлы

Информация

Списки файлов

Дополнительно