LINEBURG


<< Пред. стр.

страница 3
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

предыдущего, в случае равенства элементов они перечисляются
подряд
А [1] >= А [2] >= ... >= A [N].

Известно достаточно много алгоритмов сортировки, эффективность
которых совпадает и равна О(N2), где N – число элементов массива.
Рассмотрим в сравнении эффективности два алгоритма сортировки:
общеизвестный «Метод пузырька» и «быстрый», быстродействие которых
очень сильно различаются, что немаловажно при решении больших
олимпиадных задач и прикладных задач практического программирования.


4.1.1 СОРТИРОВКА ПРОСТЫМ ОБМЕНОМ
(метод "пузырька")
Название это происходит от образной интерпретации, при которой в
процессе выполнения сортировки более "легкие" элементы (элементы с
заданным свойством) всплывают на "поверхность".
Рассмотрим идею метода на примере. Отсортируем по возрастанию
массив из 5 элементов: 5 2 8 4 9. Длина текущей (неупорядоченной) части
массива — (N — k + 1), где k — номер просмотра,
i — номер первого элемента проверяемой пары,
N — k - номер последней пары .
Первый просмотр: рассматривается весь массив.
i= 1 5 4 8 2 9 (k=1, i=1, N-k=4) > меняем
i= 2 4 5 8 2 9 < не меняем
i= 3 4 5 8 2 9 > меняем
i = 4 4 5 2 8 9 < не меняем 9 находится на своем месте.
Второй просмотр: рассматриваем часть массива с первого до предпоследнего
элемента.
i= 1 5 2 8 9 < не меняем
i= 2 4 5 2 8 9 > меняем
i= 3 4 2 5 8 9 < не меняем 8 — на своем месте.
Третий просмотр: рассматриваемая часть массива содержит три первых
элемента.
i= 1 4 2 5 8 9 > меняем
21
i= 2 2 4 5 8 9 < не меняем 5 — на своем месте.
Четвертый просмотр: рассматриваем последнюю пару элементов.
i= 1 2 4 5 8 9 < не меняем 4 — на своем месте.
Наименьший элемент — 2 оказывается на первом месте.
Количество просмотров элементов массива равно N-1.

Программная реализация :
Procedure Sort;
Var k, i, t:Integer; {k — номер просмотра, изменяется от 1 до N-1;
i — номер первого элемента рассматриваемой
пары; t — рабочая переменная для перестановки
местами элементов массива.}
Begin
For k:=l To N-1 Do
{Цикл по номеру просмотра.}
For i:=l To N-k Do
If 'A[i]>A[i+l] Then
{Перестановка элементов.} Begin
t:=A[i];A[i] :=A[i+l] ;A[i+l] :=t;
End;
End;
ЭФФЕКТИВНОСТЬ АЛГОРИТМА:
При сортировке методом "пузырька" выполняется N — 1 просмотров,
на каждом i-м просмотре производится N — i сравнений. Общее количество
С равно N* (N—1)/2,или O(N2).

4.1.2 БЫСТРАЯ СОРТИРОВКА

Данный метод был предложен Ч.Э.Р. Хоаром в 1962 году. В общем
случае его эффективность достаточно высока (О(n*logn)), поэтому автор
назвал его "быстрой сортировкой". Такая эффективность достигается за счет
отсечения ненужных перестановок для уже отсортированного массива.

АЛГОРИТМ:
В исходном массиве А выбирается некоторый элемент X (его называют
"барьерным"). Целью является запись Х "на свое место" в массиве, пусть это
будет место k, такое, чтобы слева от Х были элементы массива, меньшие или
равные X, а справа — элементы массива, большие X, т.е. массив А будет
иметь вид:
(A[1], A[2], ..., A[k - 1] ), A[k] = (X), (A[k + 1], ..., A[n] ).
В результате элемент A[k] находится на своем месте и исходный
массив А разделен на две неупорядоченные части, барьером между которыми
является элемент А[k]. Далее требуется отсортировать полученные части тем
же методом до тех пор, пока в каждой из частей массива не останется по
одному элементу, то есть пока не будет отсортирован весь массив.
22


ПРИМЕР.
Исходный массив состоит из 8 элементов: 8 12 3 7 19 11 4 16. В
качестве барьерного элемента возьмем средний элемент массива (7).
Произведя необходимые перестановки, получим: (4 3) 7 (12 19 11 8 16);
теперь элемент 7 находится на своем месте. Продолжаем сортировку.
Левая часть: Правая часть:
(3) 4 7 (12 19 11 8 16) 3 4 7 (8) 11 (19 12 16)
3 4 7 (12 19 11 8 16) 3 4 7 8 11 (19 12 16)
3 4 7 8 11 12 (19 16)
3 4 7 8 11 12 (16) 19
3 4 7 8 11 12 16 19
Из описания алгоритма видно, что он может быть реализован
посредством рекурсивной процедуры, параметрами которой являются
нижняя и верхняя границы изменения индексов сортируемой части
исходного массива.

Программная реализация :
Procedure Quicksort (m, t: Integer);{Быстрая сортировка, первый вызов
Quicksort(1,N)}
Var i , j , x , w: Integer;
Begin
i:=m; j:=t; x:=A[ (m+t) Div 2]; {Определение «барьерного элемента»}
Repeat
While A[i]<x Do Inc(i);
While A[j]>x Do Dec(j);
If i<=j Then Begin w:=A[i]; A[i]:=A[j]; A[jl:=w; Inc(i); Dec(j) End {Меняем
местами-если больше}
Until i>j;
If m<j Then Quicksort(m, j); {Рекурсия}
If i<t Then Quicksort(i,t),
End;


4.2 ПОИСК ДАННЫХ
Основной вопрос задачи поиска: где в заданной совокупности данных
находится элемент, обладающий заданным свойством?


4.2.1 ЛИНЕЙНЫЙ ПОИСК.
Большинство задач поиска сводится к простейшей — к поиску в
массиве элемента с заданным значением.
Рассмотрим именно эту задачу. Пусть требуется найти элемент Х в
массиве А. В данном случае известно только значение разыскиваемого
элемента, никакой дополнительной информации о нем или о массиве, в
23
котором производится поиск, нет. Наверное, единственным способом
является последовательный просмотр массива и сравнение значения
очередного рассматриваемого элемента массива с X. Напишем фрагмент:
For i:=1 To N Do If A[i]=X Then k:=i;
В этом цикле находится индекс последнего элемента А, равного X, при
этом массив просматривается полностью.
Эффективность алгоритма: O(N).

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ:
1. Найти первый элемент, равный Х.
2. Найти последний элемент, равный Х.
3. Написать программу поиска заданного слова в тексте. Слово и текст
являются массивами символов заданной длины. Если слово присутствует
в тексте, то выдать номер начальной позиции совпадения, в противном
случае - 0.
4. Для каждой буквы заданного текста указать, сколько раз она встречается
в тексте.


4.2.2 БИНАРНЫЙ ПОИСК

Если заранее известна некоторая информация о данных, среди которых
ведется поиск, например, известно, что массив данных отсортирован, то
удается сократить время поиска, используя бинарный (двоичный,
дихотомический, методом деления пополам — все это другие названия
алгоритма, основанного на той же идее) поиск.
Итак, требуется определить место Х в отсортированном (например, в
порядке неубывания) массиве А. Делим пополам и сравниваем Х с
элементом, который находится на границе этих половин. Отсортированность
массива А позволяет по результату сравнения со средним элементом массива
исключить из рассмотрения одну из половин.
Пример.
Пусть Х = 6, а массив А состоит из 10 элементов: 3 5 6 8 12 15 17 18 20 25.
1-й шаг. Найдем номер среднего элемента: m =[(1+10)/2] = 5.
Так как 6 < А[5], далее можем рассматривать только элементы,
индексы которых меньше 5:
3 5 6 8 12 15 17 18 20 25.
2-й шаг. Рассматриваем лишь первые 4 элемента массива, находим индекс
среднего элемента этой части
m =[(1+4)/2] = 2, 6 > А [2], следовательно, первый и второй элементы
,из рассмотрения исключаются:
3 5 6 8 12 15 17 18 20 25.
3-и шаг. Рассматриваем два элемента, значение m =[(3+4)/2] = 3:
3 5 6 8 12 15 17 18 20 25.
24
А [3]= 6. Элемент найден, его номер — 3.

Программная реализация бинарного поиска:
Procedure Search;
Var i,j,m:Integer; f:Boolean;
Begin
i:=1; j:=N; {На первом шаге рассматривается весь массив.}
f:=False; {Признак того, что Х не найден.}
While (i<=j) And Not f Do Begin
m:=(i+j) Div 2;
{Или m:=i+.(j-i) Div 2; , так как i+(j-i) Div 2= (2*i+(j-i)) Div 2=(i+j) Div 2.}
If A[m]=X Then f:=True {Элемент найден, поиск прекращается.}
Else If A[m]<X Then i:=m+l {Исключаем из рассмотрения левую часть А}
Else j:=m-l {Правую часть.}
End
End;

Рекурсивная реализация бинарного поиска:
Значением переменной t является индекс искомого элемента или ноль,
если элемент не найден.
Procedure Search (i,j:Integer;Var t:Integer);
{Массив А и переменная Х глобальные величины}
Var m:Integer;
Begin
If i>j Then t:=0 Else Begin m:=(i+j) Div 2;
If A[m]<X Then Search(m+1,j,t) Else
If A[m]>X Then Search(i,m-l,t) Else t:=m
End
End;
Эффективность алгоритма:
Каждое сравнение уменьшает диапазон поиска приблизительно в два
раза. Следовательно, общее количество сравнений имеет порядок O (logN),
но не стоит забывать, сколько может «весить» предварительная сортировка
массива!



ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ:
1. Задано N точек своими целыми координатами на плоскости.
Отсортировать их по возрастанию абцисс.
2. Задана БД «Аптека», содержащая поля: «Наименование», «Страна
изготовитель», «Дата выпуска», «Фасовка». Отсортировать БД по полю
«Дата выпуска».
25
§5. ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ

В олимпиадах по программированию большое место стали занимать
задачи вычислительной геометрии, которые требуют не только
определенных знаний по геометрии, и аккуратности в использовании
структур данных. Геометрические задачи обычно состоят из большого
количества маленьких подзадач, которые оформляются в виде подпрограмм,
что имеет большое значение при формировании структурного стиля
программирования.
В данном разделе сознательно используется тип Extended для
достижения оптимальной точности вычислений. Все локальные задачи
оформлены в едином стиле оформления данных в виде отдельных
подпрограмм, что позволяет осуществлять «сборку» большой программы из
маленьких «кирпичиков».


5.1 ПРЯМАЯ ЛИНИЯ И ОТРЕЗОК ПРЯМОЙ
1. Прямая линия на плоскости, проходящая через две точки V и W,
заданные своими координатами: (Vx;Vy) и (Wx;Wy), определяется следующим
линейным уравнением от двух переменных:
(Wx-Vx)*(y-Vy)=(Wy-Vy)*(x-Vx).
После преобразований получаем:
(Wy-Vy)*x+(Wx-Vx)*y+(Wy-Vy)*Vx-(Wx-Vx)*Vy=0
или после соответствующих обозначений:
A*x+B*y+C=0. , где A= Vy-Wy, B = Wx-Vx, C = (Wy-Vy)*Vx + (Vx-Wx)*Vy
2. Точка пересечения двух прямых, заданных уравнениями
A1*x+B1*y+C1=0 и A2*x+B2*y+C2=0,
Координаты точки их пересечения, в случае ее существования, определяется
по формулам:
X= -(C1*B2-C2*B1)/(A1*B2-A2*B1),
Y=(A2*C1-A1*C2)/(A1*B2-A2*B1).
Существование определяется неравенством (A1*B2-A2*B1)<>0
3. Принадлежность некоторой точки отрезку (Vx;Vy)-(Wx;Wy):
Координаты точек отрезка можно задать двумя параметрическими
уравнениями от одной независимой переменной t:
x=Vx+(Wx-Vx)*t,
y=Vx+(Wy-Vy)*t.
При 0<=t<=1 точка (x, y) лежит на отрезке, а при t<0 или t>1 - вне
отрезка на прямой линии, продолжающей отрезок.
4. Взаимное расположение отрезков на плоскости:
Даны два отрезка. Первый отрезок задан точками p1=(x1;y1) и
p2=(x2;y2), а второй - точками p3=(x3; y3) и p4=(x4; y4). Точка пересечения
(если она есть) обозначена как p=(x;y).
26
Взаимное расположение отрезков можно проверить с помощью
векторных произведений:
V1=p3p4 x p3p1,
V2=p3p4 x p3p2,
V3=p1p2 x p1p3,
V4=p1p2 x p1p4.
Векторное произведение: V ? W = (Vx ? Wy – Vy ? Wx),
Ориентированный отрезок p1p2 определяется как разность векторов W – V ,
т.е. Хp3p4=Хp3-Хp4 , Yp3p4=Yp3-Yp4 , тогда
V1 = p3p4 x p3p1 = Xp3p4*Yp3p1 – Yp3p4*Xp3p1.

Известно, что если:
V1V2<0 и V3V4<0, то отрезки пересекаются;
V1V2>0 или V3V4>0, то отрезки не пересекаются;
V1V2<=0,V3=0,V4<>0, то точка p3 расположена на отрезке p1p2;
V1V2<=0,V4=0,V3<>0, то точка p4 расположена на отрезке p1p2;
V3V4<=0,V1=0,V2<>0, то точка p1 расположена на отрезке p3p4;
V3V4<=0,V2=0,V1<>0, то точка p2 расположена на отрезке p3p4;
V1=0,V2=0,v3=0,V4=0, то отрезки p1p2 и p3p4 расположены на одной
прямой, необходимы дополнительные проверки для выяснения того,
пересекаются они или нет.

5.2 ВЕКТОРНАЯ ГЕОМЕТРИЯ
Каждую точку плоскости можно отождествлять с вектором, начало
которого находится в точке (0,0).Обозначим координаты точки (вектора) V в
декартовой прямоугольной системе координат через (Vx,Vy), точки
W=(Wx,Wy), Q=(Qx,Qy). Для векторов, лежащих в плоскости XOY,
определены следующие операции:
сумма: Gx = Vx + Wx, Gy = Vy + Wy
G=V+W
разность: Gx = Vx – Wx, Gy = Vy – Wy
G=V–W
умножение на число K: Gx = K?Vx, Gy = K?Vy
G = K?V
V?W = Vx?Wx + Vy?Wy
скалярное произведение:
V ? W = (Vx?Wy – Vy?Wx)Z, где Z – единичный
векторное произведение:
вектор, направленный по оси OZ, ?=Vx?Wy–
Vy?Wx – числовой множитель.

Заметим, что если начальная точка вектора V=(Vx,Vy), а конечная
W=(Wx,Wy), то он является разностью векторов W – V или ориентированным
отрезком.
Вектор V можно задать в полярной системе координат через его длину
(модуль) V и угол ? относительно оси OX. Координаты (V, ?) полярной
27
системы координат и (Vx,Vy) прямоугольной декартовой связаны
соотношениями: Vy
V
Vx = Vcos?, Vy = Vsin?,
?
V = sqrt(sqr(Vx) + sqr(Vy)), tg? = Vy/Vx.
Vx
Для скалярного произведения векторов (V, ?) и (W, ?) справедливо
соотношение:
V?W = Vx?Wx + Vy?Wy = V?cos??W?cos? + V?sin??W?sin? = V?W?cos(?-?)
для векторного:
V?W=(Vx?Wy–Vy?Wx)Z=(V?cos??W?sin? - V?sin??W?cos?)Z=
(V?W?sin(? - ?))Z;

Из этих соотношений следует:
• скалярное произведение ненулевых векторов равно нулю, если
векторы перпендикулярны;
• векторное произведение ненулевых векторов равно нулю, если
векторы параллельны;
• при общей начальной точке у двух векторов скалярное
произведение больше нуля, если угол между векторами острый, и меньше
нуля, если угол тупой;
• при общей начальной точке двух векторов их векторное
произведение больше нуля, если второй вектор направлен влево от первого, и
меньше нуля, если вправо.

Процедуры и функции работы с отрезками и линиями:
Type TLine = Record A, B, C:Extended; End; {Описание типа для прямых}
Type TPoint = Record X,Y:Extended; End; {Описание типа для точек }

Procedure Point2ToLine(Const A, B:Tpoint; Var L: TLine);
{Определение уравнения прямой по координатам двух точек}
Begin
L.A:=B.y-A.y; L.B:=A.x-B.x; L.C:=-(A.x*L.A+A.y*L.b)
End;

Function Line2ToPoint(Const fL, sL: TLine; Var P: Tpoint): Boolean;
{Определение координат точки пересечения двух линий. Значение функции
равно true, если точка пересечения есть,и false ,если прямые параллельны }
Var st:Extended;
Begin
st:=fL.A*sL.B-sL.A*fL.B;
If Not (st<>0) Then Begin
Line2ToPoint:=True; {Координаты точки пересечения двух прямых}
28
P.X:=-(fL.C*sL.B-sL.C*fL.B)/st; P.Y:=(sL.A*fL.C-fL.A*sL.C)/st; End
Else Line2ToPoint:=False
End;

Векторная геометрия:
Type
TvecDec = Record x,y:Extended; End;
TvecPol = Record rst, angl: Extended; End; {описание векторов }

Procedure AddVecDec(Const a,b: TvecDec; Var c:TvecDec);
{Сумма двух векторов в декартовой системе}
Begin
C.x:=A.x+B.x;
C.y:= A.y+B.y;
End;

Procedure SubVecDec(Const a,b: TvecDec; Var c:TvecDec);
{Разность двух векторов в декартовой системе координат}
Begin
C.x:=A.x-B.x;
C.y:=A.y-B.y;
End;

Procedure MultVecDecScalar(Const a: TvecPol;const k:extended; Var b:TvecPol);
{Умножение вектора на число в декартовой системе координат}
Begin B.x:=A.x*k;
B.y:=A.y*k; End;

Procedure MulkVecPol(Const A: TvecPol; Const K:Extended; Var B:TvecPol);
{Умножение вектора на число в полярной системе координат}
Begin
If k>=0 then
begin
B.Rst:=A.Rst*K;
B.Angl:= A.Angl;
End else
Begin
B.Rst:=A.Rst*abs(k);
B.Angl:=A.Angl+Pi;
If B.Angl>2*Pi then B.Angl:=B.Angl-2*Pi;
End;
End;

Функция определения угла при переводе из декартовой в полярную

<< Пред. стр.

страница 3
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign