LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

систему координат:
29


Function GetAngle(Const x,y:Real):Extended;
{Возвращает угол от 0 до 2Pi, начиная от Ох, против часовой стрелки}
Var rs, c:Real;
Begin
rs:= Sqrt(Sqr(x)+Sqr(y));
if rs=0 Then GetAngle:=0
Else Begin
C:=x/rs;
If c=0 Then C:=Pi/2 {При определении угла следует учитывать
период функции Tan(x) }
Else C:=Arctan (Sqrt(Abs(1- Sqr(c)))/c);
If c<0 Then C:=Pi+c;
If y<0 Then C:=2*Pi-C;
GetAngle:=C;
End;
End;

Procedure TurnDecPol(Const a:TvecDec; Var b:TvecPol);
{Перевод из декартовой системы координат в полярную}
Begin
b.rst:=Sqrt(Sqr(a.x)+Sqr(a.y));
b.angle:=getangle(a.x,a.y);
End;

Procedure TurnPolDec(Const a:TvecPol; Var b:TVecDec );
{Перевод из полярной системы координат в декартовую}
Begin
b.x:=a.rst*cos(a.angle);
b.y:=a.rst*sin(a.angle);
End;

Function VectorMulDec (Const a,b:TvecDec): Extended;
{Скалярное произведение векторов в декартовой системе координат}
Begin
SkalarMulDec:=a.x*b.x+a.y*b.y;
End;

Function VectorMulDec(Const a,b:TVecDec):Extended;
{Векторное произведение векторов в декартовой системе координат}
Begin
VectorMulDec:=a.x*b.y-a.y*b.x;
End;

Function SkalarMulPol(Const a,b:TvecPol): Extended;
30
{скалярное произведение векторов в полярной системе координат}
Begin
SkalarMulPol:= cos(a.angle-b.angle)*a.rst*b.rst;
End;

Function VectorMulPol(const a,b:TvecPol): Extended;
{Векторное произведение векторов в полярной системе координат}
Begin
VectorMulPol:=sin(b.angl-a.angl)*a.rst*b.rst;
End;


5.3 ТРЕУГОЛЬНИК
5.3.1 ПЛОЩАДЬ ЛЮБОГО ТРЕУГОЛЬНИКА
Даны точки p1=(x1,y1), p2=(x2,y2), p3=(x3,y3), образующие некоторый
треугольник
x1 y1 1
Определитель x2 y2 1
x3 y3 1
дает удвоенную ориентированную площадь треугольника
(p1,p2,p3).Значение площади положительно тогда и только тогда, когда обход
(p1,p2,p3) ориентирован против часовой стрелки.


5.3.2 ЗАМЕЧАТЕЛЬНЫЕ ЛИНИИ И ТОЧКИ
ТРЕУГОЛЬНИКА.

Высоту треугольника, опущенную на сторону а, обозначим через ba.
Через три стороны она выражается формулой
ba = 2*sqrt(p*(p-a)*(p-b)*(p-c))/a, где p=(a+b+c)/2.
Медианы треугольника пересекаются в одной точке (всегда внутри
треугольника ), являющейся центром тяжести треугольника. Эта точка делит
каждую медиану в отношении 2: 1, считая от вершины.
Медиану на сторону А обозначим через ma. Через три стороны
треугольника она выражается формулой
ma = sqrt(2*b*b+2*c*c-a*a)/2.
Три биссектрисы треугольника пересекаются в одной точке (всегда
внутри треугольника), являющейся центром вписанного круга. Его радиус
вычисляется по формуле
r = sqrt((p-a)*(p-b)*(p-c)/p).
Биссектрису к стороне a обозначим через la, она выражается формулой
la = 2*sqrt(b*c*p*(p-a))/(b+с), где p – полупериметр.
31
5.3.3 СВОЙСТВА ТРЕУГОЛЬНИКОВ.

В РАВНОБЕДРЕННОМ треугольнике высота, медиана и биссектриса,
опущенные на основание, а также перпендикуляр, проведенный через
середину основания, совпадают друг с другом.
В РАВНОСТОРОНЕМ те же свойства имеют место для всех трех
сторон.
Центр тяжести, центр вписанного круга и центр описанного круга
совпадают друг с другом.

Процедуры и функции:

Procedure Read; {Ввод координат точек треугольника}
Var k:integer;
Begin
For k:=1 to 3 do
Begin
Writeln(‘Ввод координат точки № ’,k);
Readln (P[k].x,P[k].y) {Массив P описан в глобальных переменных}
End;
End;

Procedure Trian (var a,b,c:extended); {Вычисление длин сторон треугольника}
Begin
A:=sqrt(sqr(P[1].x-P[2].x)+Sqr(P[1].y-P[2].y));
B:=sqrt(sqr(P[2].x-P[3].x)+Sqr(P[2].y-P[3].y));
C:=sqrt(sqr(P[3].x-P[1].x)+Sqr(P[3].y-P[1].y));
End;

Function IsTriangle(Const a,b,c: Extended): Boolean;
{проверка существования треугольника со сторонами a,b,c}
Begin
IsTriangle:=(a+b>c) And (a+c>b) And (b+c>a);
End;

Fuction SquareTrian : extended;
{Вычисление ориентированной площади треугольника, P-глобальный}
Begin
SquareTrian:=
(P[1].x*(P[2].y-P[3].y)+P[2].x*(P[3].y-P[1].y) + P[3].x(P[1].y-P[2].y))/2;
End;

Function GetHeight(Const A,B,C: Extended):Extended;
{Вычисление длины высоты, проведенной из вершины, противоположной
стороне треугольника с длиной А}
32
Var p: Extended;
Begin
P:=(A+B+C)/2;
GetHeight:=2*Sqrt(p*(p-A)*(p-B)*(p-C))/A
End;

Function GetMed(Const A,B,C: extended): extended;
{Вычисление длины медианы, проведенной из вершины, противоположной
стороне треугольника с длиной А}
Begin
GetMed:=Sqrt(2*(b*b+c*c)-a*a)/2
End;

Function GetBiss(Const A,B,C: Extended):Extended;
{Вычисление длины биссектрисы, проведенной из вершины,
противоположной стороне треугольника с длиной А}
Var p:Extended;
Begin
P:=(A+B+C)/2;
GetBiss:=2*Sqrt(B*C*P*(P-A))/(B+C)
End;

Function GetRadInc(Const A,B,C :Extended):Extended
{Вычисление радиуса окружности, вписанной в треугольник с длинами
сторон A, B, C}
Var p:Extetnded;
Begin
P:=(A+B+C)/2;
GetRadInc:=Sqrt((P-A)*(P-B)*(P-C)/P)
End;

Function GetRadOut(Const A,B,C: Extended):Extended;
{Вычисление радиуса окружности, описанной около треугольника с длинами
сторон А, В,С}

Var p:Extended;
Begin
P:=(A+B+C)/2;
GetRadOut:=A*B*C/(4*Sqrt(P*(P-A)*(P-B)*(P-C)))
End;


5.4 МНОГОУГОЛЬНИК
Многоугольник называется простым, если никакая пара
непоследовательных его ребер не имеет общих точек.
33
Реализация в программе: если нет ни одного пересечения сторон,
включая случай их частичного наложения, то многоугольник простой.

Function CheckSimple(Const A:Array Of Tpoint; Const N:Word):Boolean;
{проверка простоты многоугольника}
Var i,j:Integer:
Rs:Tpoint;
Begin
CheckSimple:=False;
For i:=0 To N-2 Do
For J:=i+1 To N-1 Do
Case checkMutL(A[i],A{i+1},A[j},A[(j+1 Mod N},rs) Of
{Функция проверки взаимного расположения двух отрезков описана ранее}
0: If (J<>I+1) And (I<>(J+1) Mod N) Then Exit;
2: Exit:
End;
CheckSimple :=True;
End;


5.4.1 ОПРЕДЕЛЕНИЕ ВЫПУКЛОСТИ
МНОГОУГОЛЬНИКА

1 способ
Многоугольник является выпуклым, если все диагонали лежат внутри
него.
Сумма внутренних углов в выпуклом многоугольнике равна 180*(N-2),
где N – число сторон многоугольника.

2 способ
Все треугольники, образованные тройками соседних вершин в порядке
их обхода, имеют одну ориентацию. (Нахождение тройки вершин на одной
прямой не нарушают факта выпуклости).

Function CheckPromin (Const A:Array Of Tpoint; Const N:Word):Boolean;
{Функция равна True, если многоугольник выпуклый }
Var bn,nw:Byte;
I:Integer; rp:Extended;
Begin
CheckPromin:=False;
If n>3 Then Begin
Bn:=1;
For i:=0 To N-1 Do Begin
Rp:= SguareTrian(A[(I+N-1) Mod N], A[i], A[(i+1)Mod N]);
34
{Ориентированная площадь треугольника, построенного по трем соседним
вершинам многоугольника}
If rp=0 Then nw:=1 {Точки находятся на одной прямой}
Else If rp<0 Then Nw:=0 Else nw:=2;
If (bn=1) Then bn:=nw Else
If (nw<>1) And (nw<>bn) Then Exit;
{Вершины многоугольника лежат не на одной прямой и ориентация
«соседних» треугольников не совпадает – многоугольник не выпуклый}
End;
End;
CheckPromin:=True;
End;


5.4.2 ПЛОЩАДЬ ПРОСТОГО ПЛОСКОГО
МНОГОУГОЛЬНИКА
Пусть N-угольник задан координатами своих вершин. Его
ориентированная площадь (точки перечисляется против часовой стрелки)
будет равна:
S:=1/2*(X1Y2-X2Y1+X2Y3-X3Y2+.....+XnY1-X1Yn)

Процедуры и функции:

{ Считает определитель 2x2 }
Function Det(Const a,b,c,d : Extended) : Extended;
Begin
Det:=a*d-b*c;
End;

{ Вычисляет ориентированную площадь треугольника, }
{ натянутого на отрезок [P1,P2] и начало координат }
Function SSquare(Const P1,P2: TPoint): Extended;
Begin
SSquare:=Det(P1.x,P2.x,P1.y,P2.y)/2;
End;

{ Вычисляет ориентированную площадь треугольника, }
{ натянутого на точки P1, P2 и P3 }
Function P3Square(Const P1,P2,P3: TPoint) : Extended;
Begin
P3Square:=Det(P1.x-P3.x,P2.x-P3.x,P1.y-P3.y,P2.y-P3.y)/2;
End;

{ Вычисляет ориентированную площадь многоугольника,}
{ заданного массивом вершин A, N - число вершин}
35
Function PolySquare(N: Word; Const A: Array Of Point): Extended;
Var S : Extended;
i : Word;
Begin
S:=SSquare(A[N-1],A[0]);
For i:=0 To N-2 Do S:=S+SSquare(A[i],A[i+1]);
PolySquare:=S;
End;

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ
1. На плоскости заданы треугольник и отрезок. Определить их
взаимное расположение.
2. На плоскости действительными координатами своих вершин
заданы два треугольника. Используя перемещения и повороты, определить,
можно ли один из треугольников вложить в другой.
3. На плоскости заданы N точек. Найти ближайшего «соседа» для
каждой точки.
4. На плоскости заданы N точек. Найти минимальное количество
прямых, из которых можно разместить все точки.
5. Определить радиус и центр окружности, на которой лежит
наибольшее число точек заданного на плоскости множества точек.
6. ПЕРЕСЕЧЕНИЕ. Найти площадь пересечения N
прямоугольников со сторонами, параллельными осям координат.
Входные данные: число N (2<=N<=1000) и N четверок действительных
чиселXi1 Yi1 Xi2 Yi2 , задающих координаты левого нижнего и правого
верхнего углов прямоугольника.
Выходные данные: Площадь пересечения (общая часть) всех данных
прямоугольников, либо выдать, что они не пересекаются.
7. ОБЪЕДИНЕНИЕ. Найти площадь объединения N
прямоугольников со сторонами, параллельными осям координат.
Входные данные: число N (2<=N<=1000) и N четверок действительных
чисел (два знака после запятой) Xi1 Yi1 Xi2 Yi2 , задающих координаты
левого нижнего и правого верхнего углов прямоугольника.
Выходные данные: Площадь объединения прямоугольников.(два знака
после запятой)
8. ТОРТИК. Требуется разрезать торт (выпуклый N-угольник) на К
частей равной площади. Разрешается проводить прямые вертикальные
разрезы от одной границы торта до другой. Различные разрезы могут иметь
общие точки лишь в своих концевых вершинах. Написать программу
построения требуемых К-1 разрезов.
36
Входные данные: Два числа К и N (1<=K, N<=50)/ Далее следуют N
пар вещественных чисел (2 знака после запятой) – координаты
последовательно расположенных вершин многоугольника.
Выходные данные: Каждый из Л-1 разрезов должен быть представлен
четверкой чисел- координатами концов соответствующего разреза.
9. КАРТИННАЯ ГАЛЕРЕЯ. В картинной галерее, имеющей форму
N-угольника, расположено М люстр, которые мы будем считать точечными
источниками света. Точка стены называется освещенной, если из нее видна
хотя бы одна из люстр. Неосвещенным участком называется максимальное
связное множество точек стены галереи, ни одна их которых не освещена
(участок может содержать углы галереи). Определить все неосвещенные
участки.
Входные данные: N и M(1<=N,M<=30)). В каждой из следующих N
строк записаны координаты очередного угла галереи. Углы перечислены в
порядке обхода стены по часовой стрелке.. Далее идут М строк, которые
содержат координаты очередной из люстр.
10. Простой многоугольник задан своими вершинами в порядке обхода.
Определить, лежит ли заданная точка внутри многоугольника.


§6. ПЕРЕБОР И МЕТОДЫ ЕГО СОКРАЩЕНИЯ.
Данный раздел рассматривает, вероятно, самые «старые» по способам
исследования их решений задачи. Один из локальных методов их решения –
метод динамического программирования был найден в 70-е годы ХХ
столетия.
Как показывает опыт, элементы перебора встречаются, фактически,
почти во всех решаемых задачах.
Большое значение при изучении данного раздела имеет формирование
у учащихся умения «диагностировать» способ решения определенной задачи.


6.1 NP – ПОЛНЫЕ ЗАДАЧИ

Существует достаточно много задач, которые требуют перебора всех
комбинаций данных для выбора оптимального решения – т.н. NP – полные
задачи (решение которых нельзя найти за полиномиальное время). Такие
задачи реализуются только при определенных ограничениях (т.к. очень
трудоемки для памяти ПК) и практически не рассматриваются в школьном
программировании, поэтому рассмотрим их кратко.


6.1.1 РЕШЕНИЕ NP-ПОЛНЫХ ЗАДАЧ
В соответствии с представлением алгоритма решения NP-задач с
помощью алгоритма угадывания и алгоритма проверки NP-полные задачи
37
требуют полного перебора и решаются рекурсивно, так, что алгоритм поиска
решения задачи размера n на каждом шаге рассматривает все возможные
варианты решений на глубину 1 и оставшуюся задачу меньшего размера n-1.

6.1.1.1 ТИПЫ РЕКУРСИВНЫХ АЛГОРИТМОВ
Рассмотрим случаи, в которых разработка рекурсивных алгоритмов
является наиболее эффективной. Обычно рекурсивный алгоритм
целесообразно разрабатывать при наличии одного из следующих условий:

1. При необходимости обработки данных, имеющих рекурсивную
структуру. Процедуры анализа рекурсивных структур наиболее эффективны,
когда они сами рекурсивны, т.к. эти процедуры отражают особенности
построения данных, и в результате строение программы соответствует
структуре обрабатываемых данных.
2. Если алгоритм, обрабатывающий набор некоторых данных, можно
построить, разбивая эти данные на части и получая из этих частичных
решений общее решение на всей совокупности данных. Этот прием,
особенно если применять его рекурсивно, часто приводит к эффективному
решению задачи, подзадачи которой представляют собой ее меньшие версии.
Данный прием получил название "разделяй и властвуй". При этом, как
правило, задачу следует разбивать на подзадачи равных размеров.
Поддержание равновесия - основной принцип при разработке хорошего
алгоритма.
3. Если задача поставлена так, что ее решением является выбор какого-
то варианта из некоторого множества возможных решений. Решение задачи
определяется после некоторого конечного числа шагов, так что выбирая на
каждом шаге вариант решения, мы удаляем часть информации из всей
подлежащей обработке информации и пытаемся решить задачу на меньшем
объеме данных. Поиск решения завершается в двух случаях:
• либо когда кончаются данные;
• либо находится решение на текущем наборе данных.
Одним из приемов решения олимпиадных задач является выход из
перебора решений по истечению времени, отпущенного на тест. И если
решение за данное время не найдено на всем множестве решений, то
выдается ответ «NO». В частности, таким методом обычно решаются NP-
полные задачи.
4. Если имеется рекурсивная схема некоторой функции. Существуют
некоторые функции, которые легко можно определить рекурсивно, но

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign