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

107 int t = Array[i];
Array[i] = Array[min];
Array[min] = t;
}
}
}
15.4. Быстрая сортировка
Алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следую- щим образом:
1.
Выбирается некоторый элемент, который называется
опорным
2.
Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все эле- менты, больше опорного, – справа от него.
3.
Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента.
// Быстрая сортировка void
QuickSort(
ref int
[] Array, int
Left, int
Right)
{
// i и j – индексы границ разделяемого массива int i = Left; int j = Right;
// x – индекс опорного элемента int x = Array[(Left + Right) / 2]; do
{
// Ищем элемент слева, который больше опорного while
(Array[i] < x)
++i;
// Ищем элемент справа, который меньше опорного while
(Array[j] > x)
‐‐j;
// Если индексы не поменялись местами,
// то обмениваем элементы if
(i <= j)
{ int t = Array[i];
Array[i] = Array[j];
Array[j] = t; i++; j‐‐;
}

108
} while
(i <= j);
// Рекурсивно выполняем быструю сортировку
// для массивов слева и справа if
(Left < j)
QuickSort(
ref
Array, Left, j); if
(i < Right)
QuickSort(
ref
Array, i, Right);
}
15.5. Поиск элемента
Алгоритмы поиска позволяют найти индекс элемента с требуемым значением.
Если массив не упорядочен, то возможен лишь
простой поиск
: пе- ребор всех элементов массива до тех пор, пока не встретится элемент с нужным значением или не закончится массив. Если элемент найден, по- иск должен быть прекращен, поскольку дальнейший просмотр массива не имеет смысла:
// Простой поиск элемента в массиве int
IndexOf(
ref int
[] Array, int
Value)
{
// Перебираем все элементы массива for
(
int i = 0; i < Array.Length; i++)
// Нашли нужное значение? Возвращаем его индекс if
(Array[i] == Value) return i;
// Перебор закончился безрезультатно – возвращаем –1
return
–1;
}
Если алгоритм поиска не нашел подходящий элемент, он должен каким-то образом сигнализировать об этом вызывающей программе.
Чаще всего в таком случае возвращается значение –1 – число, которое заведомо не может использоваться в качестве индекса массива.
Вычислительная сложность алгоритма простого поиска – линей- ная O(n).
Если массив упорядочен по возрастанию, то возможно использова- ние дихотомического рекурсивного алгоритма: массив каждый раз де- лится пополам, и если искомый элемент меньше среднего, то поиск продолжается в левой его половине, иначе – в правой:
// Дихотомический поиск элемента в массиве int
IndexOf(
ref int
[] Array, int
Value, int
Left, int
Right)

109
{
// Находим середину диапазона int x = (Left + Right) / 2;
// Если нашли значение – возвращаем его индекс if
(Array[x] == Value) return x;
// Если середина совпадает с левой или
// правой границами – значение не найдено if
((x == Left) || (x == Right)) return
–1;
// Продолжаем поиск слева или справа от середины if
(Array[x] < Value) return
IndexOf(
ref
Array, Value, x, Right); else return
IndexOf(
ref
Array, Value, Left, x);
}
Вычислительная сложность алгоритма – логарифмическая.
Индивидуальное задание
Общая часть задания: сформировать массив из 100 случайных чи- сел. Выполнить простой поиск элемента, подсчитать количество итера- ций. Отсортировать массив всеми рассмотренными методами и посчи- тать количество итерация для каждого метода. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сде- лать выводы.

110
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
ПОВЫШЕННОЙ СЛОЖНОСТИ
Для решения геометрических задач повышенной сложности необ- ходимо:
1)
знать, как представляются на плоскости такие геометрические объ- екты, как точка, прямая, отрезок и окружность;
2)
уметь находить уравнение прямой, соединяющей две заданные точки;
3)
уметь определять координаты точки пересечения двух прямых;
4)
знать, как провести перпендикуляр к прямой или определить, яв- ляются ли прямые параллельными;
5)
уметь находить скалярное и векторное произведения;
6)
находить площадь многоугольника;
7)
уметь работать с фигурами на плоскости.
Напомним основные моменты, связанные с этими понятиями.
Каждую точку плоскости можно считать вектором с началом в точ- ке (0, 0). Обозначим через
a
=
(
x
,
y
) вектор с координатами (
x
,
y
). Длина вектора (его модуль) вычисляется по формуле
2 2
a
x
y


Скалярное произведение
двух векторов – это число, равное про- изведению модулей этих векторов на косинус угла между ними,
(
a
,
b
)
=
|
a
| · |
b
| · cos φ. Если вектор
a
имеет координаты (
x
1
,
y
1
),
а вектор
b
координаты – (
x
2
,
y
2
), то скалярное произведение вычисляется по фор- муле (
a
,
b
)
=
x
1
·
x
2
+
y
1
·
y
2
Рис. 16.1. Иллюстрация к скалярному произведению векторов
x
y
a
b
φ
y
1
y
2
x
1
x
2

111
Заметим, что если угол φ острый, то скалярное произведение
(
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
векторное произведение выража- ется следующим образом:
[
a
×
b
]
=
2 2
2 1
1 1
z
y
x
z
y
x
k
j
i
=
(
y
1
·
z
2
–
z
1
·
y
2
)
i
+ (
x
1
·
z
2
–
z
1
·
x
2
)
j
+ (
x
1
·
y
2
–
y
1
·
x
2
)
k,
где
i
,
j
,
k
– единичные вектора осей
Ox
,
Oy
,
Oz
соответственно.
При решении задач на плоскости координаты
z
1
и
z
2
равны нулю.
В этом случае [
a
×
b
]
=
(
x
1
·
y
2
–
x
2
·
y
1
)·
k
Если вектор
a
образует с осью
Ох
угол α, а вектор
b
– угол β, то для ска- лярного произведения справедлива формула [
a
×
b
]
=
(|
a
|
· |
b
| · sin(β
–
α))·
k
Это означает, что для ненулевых векторов векторное произведение равно нулю тогда и только тогда, когда векторы параллельны. Если поворот от вектора
а
к вектору
b
по наименьшему углу выполняется против часовой стрелки, то [
a
×
b
]
>
0, если по часовой стрелке, то [
a
×
b
]
<
0.
Рис. 16.2. Иллюстрация к векторному произведению
Рассмотрим задачи, при решении которых используются скалярное и векторное произведения.
x
y
a
b
α
β

112
Задача 1. «Штраф за левые повороты»
[1]
. В городе Х водителям
запрещено выполнять левые повороты. За каждый такой поворот во-
дитель должен уплатить штраф в размере М рублей. Для слежки
за водителями в городе установлена компьютерная система, фикси-
рующая координаты автомобиля в начале движения, в конце движения
и во время поворота.
Исходные данные
:
N
– количество зафиксированных координат авто- мобиля, (
x
i
,
y
i
) – координаты автомобиля в процессе движения,
i
=
1, 2, …,
N
, где (
x
1
,
y
1
) – точка начала движения, (
x
N
,
y
N
) – последняя точка маршрута автомобиля.
Требуется
по заданной последовательности координат движения вычислить сумму штрафа водителя.
Рис. 16.3. Иллюстрация к задаче «Штраф за левые повороты»
Траекторию движения автомобиля можно представить в виде ло- маной, состоящей из направленных отрезков из точек (
x
i
,
y
i
) в точки
(
x
i+1
,
y
i+1
),
i
=
1, 2,…,
N
–1.
Поворот считается левым, если направление текущего отрезка пути
a
i
+1 меняется относительно предыдущего отрезка
a
i
в левую сторону, т. е. против часовой стрелки.
Таким образом, решение задачи сводится к вычислению количества пар участков пути
a
i
и
a
i
+1
, для которых выполняется условие [
a
i
×
a
i
+1
]
>
0.
Координаты векторов
a
i
и
a
i
+1
вычисляются через координаты точек
(
x
i
,
y
i
):
a
i
=
(
x
i –
x
i
–1
,
y
i –
y
i
–1
),
a
i
+1
=
(
x
i
+1 –
x
i
,
y
i
+1 –
y
i
), следовательно,
[
a
i
×
a
i
+1
]
=
(
x
i
–
x
i
–1
) (
y
i
+1
–
y
i
) – (
y
i –
y
i
–1
)(
x
i
+1
–
x
i
),
i
=
2, …,
N
–
1.

113
Требуется
определить, к каким из посаженных деревьев надо при- вязать веревку так, чтобы все деревья оказались внутри обнесенной зо- ны, а длина веревки была минимальная.
Эта и подобные ей задачи сводятся к определению для заданного множества точек на плоскости выпуклой оболочки, то есть выпуклого многоугольника с вершинами в некоторых точках из заданного множе- ства, охватывающего все его точки. В [2] приведено несколько вариан- тов решения такой задачи с учетом временных затрат на выполнение алгоритмов. Здесь мы рассмотрим способ, использующий свойства ска- лярного произведения векторов.
Будем строить выпуклую оболочку в порядке обхода участка по ча- совой стрелке. Найдем самую левую точку М
0
=
(
x
0
,
y
0
),
x
0
=
min{
x
i
}. Если таких точек несколько, то возьмем самую нижнюю из них. Эта точка на- верняка принадлежит искомой выпуклой оболочке. Зададим первона- чальный вектор
a
0
с началом в точке (
x
0
,
y
0
), параллельный оси Oy.
Следующей точкой оболочки будет такая точка М
1
, чтобы вектор
a
1
с началом в точке М
0
и концом в точке М
1
образовывал с первоначаль- ным вектором
a
0
минимальный угол. Если таких точек несколько, то выбирается точка, расстояние до которой максимально.
Далее процесс продолжаем, то есть ищем точку М
2
с минимальным углом между вектором
a
1
и вектором
a
2
с началом в точке М
1
и концом в точке М
2
, затем точку М
3 и т. д. Процесс прекращаем, когда дойдем до первой выбранной точки или количество точек в оболочке станет равно
N
Для определения угла между векторами используется скалярное произведение. Причем сам угол можно не вычислять, так как мини- мальному углу соответствует максимальный косинус угла.
Задача 3. «Заяц»
[3].
Недалеко от города Х находится зоосад.
Здешний житель, заяц, хаотично прыгая, оставил след в виде замкну-
той самопересекающейся ломаной, охватывающей территорию его
владения. Найти площадь минимального по площади выпуклого много-
угольника, описанного вокруг этой территории.
В данной задаче необходимо не только найти выпуклую оболочку множества точек, но и вычислить площадь выпуклого многоугольника с заданным набором вершин.
Исходные данные
:
N
– количество вершин выпуклого многоуголь- ника, (
x
i
,
y
i
) – координаты вершин,
i
=
1, 2, …,
N
Требуется
определить площадь выпуклого
N
-угольника.
Площадь
N
-угольника может быть вычислена как сумма площадей треугольников, из которых
N
-угольник составлен. Для нахождения пло- щади треугольника используем векторное произведение. Длина векторно-

114 го произведения векторов, как известно, равна удвоенной площади тре- угольника, построенного на этих векторах. Пусть вершины треугольника расположены в точках A
=
(
x
1
,
y
1
), B
=
(
x
2
,
y
2
), C
=
(
x
3
,
y
3
). Совместим начало координат с первой точкой. Векторное произведение равно
[AB × AC]
=
0 0
1 3
1 3
1 2
1 2
y
y
x
x
y
y
x
x
k
j
i




, следовательно, площадь треугольника равна
S
ABC
=
1/2 ((
x
2
–
x
1
) (
y
3
– y
2
) – (
y
2
–
y
1
)(
x
3
–
x
2
)).
Значение величины S
ABC
может быть как положительным, так и от- рицательным числом, так как оно зависит от взаимной ориентации век- торов AB и AC, поэтому говорят, что площадь ориентированная.
Для нахождения площади
N
-угольника последний требуется раз- бить на треугольники и найти сумму ориентированных площадей этих треугольников. Разбиение
N
-угольника на треугольники можно провес- ти так: зафиксировать одну из вершин
N
-угольника, например первую,
A
1
=
(
x
1
,
y
1
) и рассматривать все треугольники A
1
A
i
A
i
+1
,
i
=
2, 3,…,
N
–
1.
Рис. 16.4. Иллюстрация к задаче «Заяц»
Заметим, что аналогичным способом можно находить площадь произвольного многоугольника.
Рис. 16.5. Нахождение площади произвольного многоугольника
А
1
А
2
А
3
А
А
5

115
Использование свойства ориентации площади треугольника, вы- численной по векторному произведению, позволяет определить, являет- ся ли заданный многоугольник выпуклым. Для выпуклого многоуголь- ника все треугольники, образованные тройками соседних вершин в порядке их обхода, имеют одну ориентацию. Поэтому проверка много- угольника на выпуклость может быть проведена с помощью последова- тельного сравнения знаков векторных произведений для всех пар сосед- них сторон многоугольника.
Задача 4. «Тигр в загоне».
Недалеко от города Х находится запо-
ведник, в котором обитают уссурийские тигры. Работники заповедни-
ка очень переживают, когда тигр покидает охраняемую зону. Про-
грамма охраны уссурийских тигров предусматривает снабжение
каждого тигра ошейником с радиомаяком. Сигнал от тигриного ра-
диомаяка поступает в центр охраны и позволяет определить местопо-
ложение тигра. Территория заповедника представляет собой произ-
вольный многоугольник.
Исходные данные
:
N
– количество вершин многоугольника, задаю- щего заповедник, (
x
i
,
y
i
) – координаты его вершин,
i
=
1, 2, …,
N
. (
X
,
Y
) – координаты точки, в которой находится тигр.
Требуется
определить, находится ли тигр на территории заповед- ника, или надо срочно снаряжать спасательную экспедицию.
Рис. 16.6. Иллюстрация к задаче «Тигр»
Очень часто при решении задач геометрического содержания тре- буется проверить, лежит ли заданная точка внутри или вне многоуголь- ника. Таким способом можно решить, например, задачу о Бармаглоте, проверяя каждую точку
Бармаглота относительно одеяла- многоугольника. Есть много способов проверки принадлежности точки многоугольнику, однако мы приведем здесь один из них, основанный на использовании произведения векторов.
Идея метода заключается в том, чтобы определить сумму углов, под которыми стороны многоугольника видны из проверяемой точки.
Если точка лежит внутри многоугольника, то суммарный угол равен 2π
P
Q