Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[49]

Постановка задачи нахождения маршрутов включает определение матрицы коэффициентов aij, характеризующих связи между узлами i и j. Связь узла A задается коэффициентами a0j, узла В - коэффициентами aiN+ 1. Матрица имеет вид:

a1NЕсли aij = aji = 0, то связь

a2Nмежду узлами i и j отсутствует.

a3NЕсли aij=0 и aji<>0, то связь

между узлами i и j односторонняя.

Если aij<>0 и aji<>0, то связь между узлами i и j двусторонняя. Если aij = aji при i =1, 2, . . , N; j = 1, 2, . . , N, то матрица симметричная. Если aij = 0 при j =1, 2, . . , N; i > j, то матрица треугольная.

Значение aij может содержать значение ребра, связывающего узлы i и j (например, стоимость проезда), либо значение, содержащееся в узле i или j, либо любое значение, указывающее на существование связи между узлами i и j.

Введем линейный массив "Y", коэффициенты которого обозначают номера узлов графа через которые проходит маршрут, а индексы показывают номер пункта по порядку следования на маршруте. Операторы по перебору маршрутов имеют вид:

Y[0]:=0;{номер узла "А" графа}

repeat{цикл по числу узлов на маршруте}

for j:= 1 to M do Y[j]:=1;{ начальные номера узлов на маршруте}

Y[M+1]:=N+1;{номер узла "B" графа}

repeat{ цикл по перебору номеров узлов на маршруте}

for j:=1 to M+1 do if a[y[j-1],y[j]]=0 then goto METKA; {проверка}

{ связей}

{****** здесь ставятся операторы фильтра ************}

for j:=0 to M+1 do write(-, Y[j]); writeln; { вывод маршрута} METKA: Y[1]:=Y[1]+1; { изменение номера узла первого пункта на маршруте} for j:=1 to M-1 do{ определяем номера узлов на маршруте}

if Y[j]>N then begin Y[j]:=1; Y[j+1]:=Y[j+1]+1 end else Break; until Y[M]=N+1; M:=M+1 until M>M1;

В начале программы задается возможный маршрут 0- 1 - 1 - 1 - . . . - 1 - N+1 для заданного значения M>0. Проверяется наличие связей и ставятся фильтры для определения маршрута. Затем увеличивается номер узла первого пункта по порядку следования на маршруте: 0- 21 - 1 - . . . - 1 - N+1 и т. д. до 0- N- 1 - 1 - . . . - 1 - N+1. При превышении номера узла значения N, номер узла сбрасывается до единицы, а номер следующего узла увеличивается на единицу: 0- 1 - 2- 1 - . . . - 1 - N+1 и снова увеличивается номер узла первого пункта до значения N: 0- N- 2- 1 - . . . - 1 - N+1 и далее сбрасывается до единицы с увеличением номера следующего узла: 0- 1 - 3- 1 - . . . - 1 - N+1. После (N- 1)- го сброса и увеличения значения узла первого пункта до N получим маршрут: 0-N-N-1-. . . -1-N+1 и далее: 0-1-1-2-. . . -1-N+1. Таким образом, происходит перебор всех возможных маршрутов до 0- N- N- N- . . . - N- N+1. После этого рассматриваются маршруты для M=M+1 включая M=M1. Отметим, что при необходимости маршрут 0- N+1 для M=0 нужно рассмотреть отдельно.

При решении конкретных задач необходимо определить значение коэффициентов aij матрицы связи и установить необходимые фильтры.

Рассмотрим задачу определения стоимости маршрутов из A в B.


1) Определим матрицу связей:

for i:=0 to N+1 do for j:=i to N+1 do a[j,i]:=0; {нижний треугольник} for i:=0 to N+1 do for j:=i to N+1 do a[i,j]:=1; {верхний треугольник}

2) Определение числа коробок каждого вида аналогично суммированию повторяющихся номеров узлов на маршруте.

Практическое задание N 2. 27

1)Вывести в файл стоимость маршрутов без повторяющихся узлов при N=4, M=3, M1=4, Х=9. Определить номера маршрутов с наименьшей и наибольшей стоимостью

для разных значений М.

2)Вывести символами псевдографики в текстовом режиме маршруты движения в прямоугольнике 2х4, либо 4х2. Начало движения при NH=8.

1. ) Зададим стоимость проезда из узла i в узел j: for i:=0 to N+1 do for j:=i to N+1 do a[i,j]:=Random(X); {Х-дано} for i:=0 to N+1 do a[i,i]:=0;{ движение внутри узла запрещено}

for i:=0 to N+1 do for j:=i to N+1 do a[j,i]:=a[i,j];{связи }

{двусторонние и равнозначные}

2). Матрицу связей можно вывести на экран для проверки. При выводе маршрута на экран или в файл можно выводить также значение стоимости маршрута.

S:=0; for m:=1 to M1+1 do S:=S+a[y[m-1],y[m]]; {стоимость маршрута} Рассмотрим задачу расстановки мин на прямоугольном поле

размером Nx*Ny. При этом M=M1=N=Nx*Ny и все узлы должны быть пройдены без повторений. Расстановка начинается из узла с заданным номером NH и может закончиться в узлах на верхней границе.

1) Определим матрицу связей: for i:=0 to N+1 do for j:=1 to N+1 do a[i,j]:=0; for i:=1 to N-1 do begin a[i,i+1]:=1; a[i+1,i]:=1 end; { связи по гориз}

for j:=1 to Ny-1 do begin k:=Nx*j; a[k,k+1]:=0; a[k+1,k]:=0 end; for i:=1 to Nx do for j:=1 to Ny-1 do{ связи по вертикали}

begin k:=Nx*(j-1)+i; a[k,k+Nx]:=1; a[k+Nx,k]:=1 end; a[0,NH]:=2;{ NH - узел связи c узлом 0}

for i:=1 to Nx do a[i,N+1]:=3;{ 1, . . , Nx - узлы связи c узлом N+1}

2). Установим фильтр, запрещающий возврат в узел на маршруте: for k:=1 to M do c[y[k]]:=0; for k:=1 to M do

begin c[y[k]]:=c[y[k]]+1; if c[y[k]]=1 then goto METKA end;

Здесь производится суммирование повторяющихся номеров узлов на маршруте. При совпадении номера узла значение счетчика c[y[k]] =1 -маршрут не рассматривается.

Рассмотрим задачу загрузки N - видов коробок в машину. Задается число коробок каждого вида: Ki, их вес Mi и объем Vi, где i=1, 2, . . , N. Ограничения могут быть по общему весу и объему. Число узлов графа равно N. Число узлов на маршруте M=1, М1=K1+K2+. . . +KN. Интервал М-М1 можно уменьшить просчитав наибольшее допустимое по весу и объему число коробок KMi каждого вида загружаемых в машину (KMi<=Ki). Тогда М = min(KMi), а М1 = max(KMi). Поскольку порядок загрузки не имеет значения, то все связи односторонние.0


3) Вывести общий вес и число коробок каждого из 3-х видов, загружаемых в машину. Задать веса функцией Random(50)+50; Установить фильтр по общему весу G<900. Общее число коробок: M=10, M1=12.

2. 5. Программы математических расчетов 2. 5. 1. Численное решение уравнений

Решение уравнения F(x) = 0 заключается в определении значений переменной "x", при которых функция обращается в нуль, т. е. в нахождении корней уравнения. Методы решения уравнений в конечном, аналитическом виде называются прямыми. Например, для уравнения F(x) = a*X+b = 0; решение имеет вид X = -в/а. Аналитически можно определить корни алгебраических уравнений не выше четвертой степени, причем для показателя степени больше двух формулы получаются достаточно сложные. Для определения корней алгебраических и трансцендентных уравнений разработаны численные методы, основанные на уточнении значения корня в предположении, что на отрезке [A, B] функция Y=F(x) непрерывна и имеет только один корень. В этом случае значения функции на концах отрезка имеют разные знаки. Знак вещественного числа "Y" можно определить при помощи функции:

FUNCTION SGN( Y: real): integer;

Begin if Y < 0 then SGN:= -1 else SGN:= 1 End;

Значение переменной SGN= -1 если Y<0, SGN= 1 если Y>=0. Рассмотрим некоторые численные методы нахождения корней уравнения.

Метод половинного деления (дихотомии) при нахождении корня уравнения F(x)=0 состоит в делении пополам отрезка [A, B], где находится корень. Затем анализируется изменение знака функции на половинах отрезка и одна из границ отрезка [A, B] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [A, B] становится меньше заданной погрешности нахождения корня "Е", либо функция попадает в полосу шума (Е1) - значение функции сравнимо с погрешностью расчетов.

REPEAT{ начало итерации }

x:= (A + B)/2;{ x - середина отрезка [A, B] }

Y:= F(x); YA:= F(A); { значения функции в середине и на конце отрезка } if SGN(Y) * SGN(YA) > 0 { если знаки функции в точках "A" и "x" совпадают } then A:= x else B:= x{ то, перенос границы "A", иначе - "В" }

UNTIL (ABS(B-A)< E) OR (ABS(F(x))< E1);

Метод дихотомии уменьшает интервал определения корня за 1 итерацию в 2 раза - за 20 итераций это составит 220.

Метод секущих (хорд) при нахождении корня уравнения Y = F(x)=0 состоит в определении точки пересечения секущей с осью "x". Секущей называется линия, соединяющая точки с координатами (A, F(A)) и (B, F(B)) на плоскости XoY. Приближенное значение корня определяется точкой пересечения с осью "X" секущей и находится по формуле:

x = (A*F(B) - B*F(A))/(F(B) - F(A));



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53]