|
||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[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)); |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||||||||||||