Лекции по Turbo Pascal (стр. 28 )

Выходные данные. В первую строку выходного файла нужно вывести минимальные затраты на установку сети (с тремя знаками после десятичной точки), во вторую - количество устанавливаемых станций. Далее вывести координаты станций (с тремя знаками после десятичной точки), а затем - список из n целых чисел, в котором i-ое число задает номер станции, к которой будет подключен i-ый город. (Кировский командный турнир по программированию, 2000 г.)

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

Решение геометрических задач.

Пусть даны две точки А (х1,у1) и В (х2,у2), как известно на плоскости они однозначно определяют одну единственную прямую. Давайте вспомним, как выглядит общее уравнение прямой: Ах+Ву+С=0. Тогда если считаем что наша прямая задана точками А и В, то уравнение прямой проходящей через эти две точки выглядит так:. Если пользоваться данной формулой, то нам придется постоянно делать проверку на деление на ноль, что не очень удобно, чтобы это избежать, лучше использовать такое равенство: (х-х1)(у2-у1)=(у-у1)(х2-х1).

Иногда бывает удобнее пользоваться уравнением прямой заданной в параметрическом виде:

, где t некий параметр, а (х1,у1) и (х2,у2) – координаты точек расположенных на рассматриваемой прямой.

Полезно будет так же вспомнить и как вычисляется расстояние между двумя точками: .

Задача: Вычислить расстояние которое пройдет путник двигаясь из точки А в точку В (при этом необходимо вычислить кратчайшее расстояние), если известно, что от точки (-1,0) до (1,0) вырыт непроходимый ров, пересечь который нельзя, можно лишь проходить по его краю.

(Пояснение: )

Решение задачи будет несколько проще, если мы введем функцию, которая позволяет определять взаимное положение трех точек. Итак, значит, у нас есть три точки: А (х1,у1), В (х2,у2) и С (х3,у3). Две из них однозначно определяют одну прямую и следовательно расположены на ней, весь вопрос состоит в том, а будет ли на этой же прямой располагаться и третья точка. Пусть прямую у нас определяют точки А и В, для того чтобы определить лежит на этой прямой точка С, составим следующую функцию:. Или F=((х3-х1)(у2-у1)-(у3-у1)(х2-х1)). Если F=0, то все три точки лежат на одной прямой, если же F>0 или же F<0, то третья точка лежит по одну из сторон от исходной прямой.

Тогда наша рассмотренная ранее задача будет сводиться к следующему: необходимо определить будут ли лежать точки по разные стороны ото рва, то есть вычислить произведение функций FА* FВ и если оно отрицательно, то точки расположены по разные стороны ото рва, но при этом необходимо еще проверить, а будут ли они пересекаться.

(Тесты: А(-3,1), В(5,4) – расстояние 8,54; А(-1,4), В(4,-4) – расстояние 9,43; А(-2,-3), В(2,5) – расстояние 8,99; А(0,0), В(4,-1) – расстояние 4,12; А(0,5), В(0,-2) – расстояние 7,34).

Рассмотрим теперь, в зависимости от того, по какую сторону от прямой будет лежать точка, какой знак будет иметь функция F? Для этого рассмотрим вполне определенный пример, а именно, пусть А(-1,0), В(1,0), а С(0,1). Вычислим F=(0-(-1))(0-0)-(1—0)(1-(-1))=0-2=-2<0, следовательно, получили, что если точка лежит слева от прямой, то функция имеет отрицательное значение, а если справа, то соответственно положительный.

Задачи:

1.  В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. И поэтому за каждый левый поворот установлен штраф в размере 50$. Определить количество левых поворотов и размер штрафа, если известны координаты площадей, через которые проезжает автомобилист.

2.  В городе Глупове транспорт может делать повороты и развороты только на площадях, причем левые повороты мэр запретил. При этом он установил такую систему штрафов, за первый левый поворот штраф 50$, за каждый последующий на 10% больше предыдущего, но любой разворот на 180° или проезд через площадь без поворота сбрасывает размер штрафа опять до 50$.

3.  Известны координаты вершин многоугольника в порядке их обхода. Определить является ли данный многоугольник выпуклым.

4.  Известны координаты вершин многоугольника в порядке их обхода. Определить является ли данный многоугольник выпуклым. При этом если многоугольник является не выпуклым, то проверить можно ли выбросить одну точка, такую чтобы многоугольник стал выпуклым. Указать порядковый номер этой точки, ее координаты, а также изобразить исходный и полученный многоугольники на экране.

Помимо того, что рассмотренная нами с вами функция F позволяет определить взаимное расположение трех точек, а так же в случае, когда эти точки не лежат на одной прямой, определить по какую сторону третья точка расположена от прямой, она удобна еще и тем, что модуль значения этой функции (в случае, когда она не равна нулю) равен двум площадям треугольника, вершины которого расположены в исходных трех точках, то есть Sr=1/2|F|.

Задачи:

1.  Вычислить площадь произвольного четырехугольника.

2.  Вычислить площадь произвольного n-угольника.

Контрольная работа.

Задача: Заданы координаты концов двух отрезков, определить взаимное расположение этих отрезков (определить лежат они параллельных, совпадающих или пересекающихся прямых, в случае совпадения прямых определить имеют отрезки общую точку, общую часть или не имеют общих точек, в случае пересечения прямых определить имеют отрезки общую точку или нет).

Приближенные методы вычислений.

Задача 1. Вычислить приближенное значение суммы

1 + x/1! + x2/2! + x3/3! + …

Считаем, что нужное приближение получено, если вычислена сумма нескольких слагаемых, и очередное слагаемое оказалось по модулю меньше, чем данное малое положительное число e.

Для решения задачи мы должны выполнить следующие действия:

2)  получить очередное слагаемое (назовем его а);

3)  сравнить абсолютную величину слагаемого а с e и, в зависимости от результата сравнения, либо продолжить, либо прекратить вычисления.

Program p;

var a: real;

x : real;

e : real;

i : integer;

S : integer;

begin

readln(x, e);

i:=1;

a:=1;

S:=0;

WHILE a>e DO

begin

S:=S+a; i:=i+1; a:=a*x/i;

end;

writeln(‘приближенное значение суммы=’,S:4:2)

end.

Задача 2. Рассмотрим часто встречающуюся задачу приближенного решения уравнения f(x)=0, где f(x) – заданная функция. Решить уравнение – значит найти такое значение х*, при котором f(x*)=0. Поиск решения осуществляется на интервале [a;b], причем f(a)<0, а f(b)>0. Используем метод деления пополам. Находим точку с=(а+b)/2 – середина отрезка. Если f(c)>0, то границу b изменяем на значение с, а если f(с)<0, то изменяем а. Процесс продолжаем, пока длина интервала не будет меньше заданной точности.

Y f(x) 0 a c b X

Пусть f(x)=x2-2, т. е. мы попытаемся найти значение квадратного корня из 2.

Program popolam;

const eps=1.0E-3;

var a, b,c:real;

Function eg(x, y:real):boolean;

begin

Eg:=Abs(x-y)<eps

end;

Function F(x:real):real;

begin

F:=Sgr(x)-2

end;

BEGIN

Writeln(‘введите интервал’); readln(a, b);

if F(a)*F(b)>0 then writeln(‘на этом интервале мы не можем

найти решение уравнения’)

else begin

while Not Eg(a, b) do

begin c:=(a+b)/2;

if F(c)>0 then b:=c else a:=c

end;

writeln(‘Результат ’,a)

end;

readln

end.

Можно с помощью этой программы решить уравнения :

x2-6x+5=0 x-cosx=0 x-lnx-2=0 2x3-9x2-60x+1=0

Метод итераций

Пусть нужно решить уравнение f(х)=0, из которого мы получаем уравнение следующего вида: х=u(х), для решения этого уравнения методом итераций необхдимо составить последовательность приближений, причем надо учитывать что далеко не каждая последовательность приведет нас к нахождению корня, необходимым и достаточным условием для использования метода итераций является u’(x)<1. Итак, для нахождения последовательности выбираем произвольно х0, вплоть до случайного числа, вычисляем х1=U(х0), х2=U(х1) х3=U(х2) и т. д. опка не будет выполнено неравенство |хi-xi+1|<e.

Y 0 a x1 x2…..... xn-2 xn X

Задача 3. Пусть непрерывная положительная на отрезке [a, b] (a<b) функция. Вычислим площадь фигуры, ограниченную графиком функции f(x), осью х и прямыми х=а и х=b. Для этого разобьем отрезок [a, b] на n равных отрезков одинаковой длины Dx=(b-a)/n a=x0<x1<…<xi<xi+1<….<xn=b

На каждом из отрезков [xi, xi+1] как на основании, построим прямоугольник с высотой f(xi).