Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Математический факультет
Кафедра МПУ
Курсовая работа
Решение задач на графах
Исполнитель:
Студентка группы М-42
Макарченко А.Ю.
Научный руководитель:
олинский М.С.
Гомель 2006
Введение
Существует целый класс олимпиадных задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.
Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим копромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.
Необходимо отметить, что данный материал в существенной степени опирается на наличие у ученика определенных навыков в использовании рекурсивных функций и рекуррентных соотношений, которые, в частности, могут появится при работе над авторскими материалами [9] и [10] соответственно.
Далее материал построен следующим образом. Приводится минимальное количество базовой теории, после чего приводится решение большого количества задач из Белорусских республиканских и международных (IOI - International Olympiad in Informatics) олимпиад по информатике для школьников.
Автору представляется наиболее эффективным следующий способ изучения излагаемого материала. После ознакомления с общими сведениями, разбор каждой новой задачи проводить в таком порядке. Прочитав условия, отложить материал в сторону и попытаться решить задачу самостоятельно. Если же Вам покажется, что Вы зашли в тупик, и дальнейшие размышления не могут привести к полезному результату, нужно возвращаться к материалу, прочитать полное решение и самостоятельно реализовать его на компьютере. Чем полнее и напряженнее будет проведенная Вами работа над текущей задачей, тем больше шансов, что Вы решите следующую задачу самостоятельно. Более того, такая работа над каждой из приведенных в данном материале задач, приведет к значительному увеличению шансов на то, что Вы решите новые задачи такого класса, которые Вам обязательно встретятся. И, наоборот, поверхностное чтение может привести, в лучшем случае, к тому, что Вы просто поймете и, возможно, запомните решение десятка приведенных задач. Это, конечно, тоже не мало, ведь Вам могут встретиться эти, либо похожие, задачи. Но автор ставит другую задачу - помочь Вам научиться решать новые задачи такого класса.
2.1 Задача "Маневры" (Автор - Перепечко С.Н.)
Республиканская олимпиада по информатике 2000г
На территории некоторого государства с сильно пересеченной, горной местностью идут военные маневры между двумя противоборствующими сторонами - "Синими" и "Зелеными". Особенности ландшафта и сложные климатические условия вынуждают подразделения обеих сторон размещаться только на территории некоторых населенных пунктов. Общее количество населенных пунктов в этом государстве равно N.
Тактика ведения боевых действий "Синих" рассчитана на нанесение противнику быстрых и внезапных ударов, что возможно лишь в том случае, если в операциях используются моторизованные части, а их передвижение происходит только по дорогам.
Разнообразие используемой боевой техники приводит к тому, что время перемещения различных боевых частей из одного пункта в другой оказывается различным и определяется величиной Vj - скоростью движения подразделений боевой части, расквартированной в j-ом населенном пункте.
Используя подавляющий перевес в технике одна из сторон, под кодовым названием "Синие", планирует организовать ночной налет на базы противника, под кодовым названием "Зеленые", и полностью их разгромить. Все боевые подразделения "Синих" приступают к выполнению операции одновременно. Если боевая часть "Синих" врывается в населенный пункт, занятый "Зелеными", то, учитывая фактор внезапности, им удается полностью разгромить эту группировку.
К сожалению, блестящему проведению этой операции помешало то обстоятельство, что спустя время T после начала операции "Зелеными" был осуществлен радиоперехват сообщения о начавшейся операции. После радиоперехвата группировки "Зеленых" мгновенно рассеиваются в окрестных горах, и остаются невредимыми.
Выясните какое количество группировок "Зеленых" и в каких населенных пунктах удастся все-таки разгромить "Синим"?
Предполагается, что в начальный момент времени группировки "Зеленых" и "Синих" не могут находиться в одном и том же населенном пункте. Если сигнал тревоги поступает в тот момент, когда боевая часть "Синих" только врывается в населенный пункт занятый "Зелеными", то используя превосходное знание местности, "Зеленым" все-таки удается скрыться в горах. Подавляющее превосходство в технике и живой силе позволяет боевым частям "Синих" организовать из каждой части любое количество экспедиций для разгрома "Зеленых". Ничто не мешает одной экспедиции за время проведения операции уничтожить несколько группировок.
Описание формата входных данных
Исходные данные задачи содержатся в файлах MAP.IN и TROOPS.IN Структура файла MAP.IN описывает карту местности. В первой строке этого файла содержатся два целых числа: N - количество населенных пунктов (0<N<256) и K - количество дорог, соединяющих эти населенные пункты (0<=K<=1000). Дороги нигде не пересекаются. В последующих K строках файла содержится схема дорог. В каждой строке записана пара двух натуральных чисел i и j и одно положительное вещественное число Lij, означающее, что между населенными пунктами i и j существует дорога длиной Lij километров (Lij < 1000).
Содержимое файла TROOPS.IN отражает размещение боевых частей воюющих сторон. Первая строка файла содержит число MF - количество боевых частей "Синих". Каждая из последующих MF строк содержат по два числа. Первое - целое число j - номер населенного пункта, в котором размещается часть, второе - вещественное неотрицательное число Vj - скорость движения боевых колонн этой части в км/час (Vj < 110). Далее в отдельной строке файла записано число MB - количество боевых группировок "Зеленых", за которым перечислены MB чисел - номера населенных пунктов, в которых эти группировки находятся. И, наконец, в последней строке файла хранится положительное вещественное число T, измеренное в часах (T < 24). Все числа в строках файлов разделены пробелами.
Описание формата выходных данных
Результат решения задачи необходимо вывести в текстовый файл VICTORY.OUT. В первую строку файла выводится количество разгромленных группировок, а во вторую - в порядке возрастания номера населенных пунктов, в которых эти группировки базировались.
Пример входных и выходных данных
MAP.IN
8 7 1 C
1 2 80 |
2 4 25 80|
4 5 10 | 5 6 10 7 15 8
6 2 5 2 o---С----o----З
2 3 40 /
7 6 10 25/ 40
8 7 15 /
TROOPS.IN 4 З 3 З
2 |
1 50 10|
6 20 |
4 4 5 3 8 5 З
2.0
VICTORY.OUT
2
4 8
Кратко алгоритм решения задачи может быть описан иак:
Методом Флойда вычисляем кратчайшие расстояния от каждой вершины до каждой. Циклом по всем вершинам "Зеленых", циклом по всем вершинам "Синих", если "Синие" успевают, значит соответствующая группировка "Зеленых" разбита.
Рассмотрим решение задачи подробнее:
Вначале идет ввод исходных данных:
read(N,K); {ввод количества пунктов и дорог}
for x:=1 to N do {инициализация дорог для метода Флойда}
for y:=1 to N do a[x,y]:=1000000000000.0;
for i:=1 to K do
begin
read(x,y,z);
a[x,y]:=z; a[y,x]:=z; {корректировка матрицы смежности}
end;
read(NumBlue); {ввод расположения и скоростей "Синих"}
for i:=1 to NumBlue do read(Blue[i],VBlue[i]);
read(NumGreen); {ввод расположения "Зеленых"}
for i:=1 to NumGreen do read(Green[i]);
read(T); {ввод времени проведения операции}
Затем - расчет расстояний между всеми населенными пунктами методом Флойда:
for i:=1 to N do
for x:=1 to N do
for y:=1 to N do
a[x,y]:=min(a[x,y],a[x,i]+a[i,y]);
Затем расчет количества уничтоженных группировок
Deleted:=0;
for i:=1 to NumGreen do {Для всех "Зеленых"}
for j:=1 to NumBlue do {Для всех "Синих"}
if a[Green[i],Blue[j]]<Vblue[j]*T {Если "Синие" успеют}
then
begin
inc(Deleted); {Уничтоженых инкрементируем}
Num[Deleted]:=Green[i]; {Номер заносим в Num}
break; {Переходим к следующим "Зеленым"}
end;
Наконец, в соответствии с требованиями задачи сортируем номера уничтоженных группировок (в массиве Num) и выводим их.
Sort;
writeln(Deleted);
for I:=1 to Deleted do write(Num[i], );
Ниже приводится полный текст решения задачи.
Размерность исходного графа уменьшена до 100*100, поскольку 255*255 вещественных чисел не помещается в статической памяти Турбо-Паскаля. (Смотри замечание в пункте 6).
{$R+,E+,N+}
program by00d1m3;
var
a : array [1..100,1..100] of single;
blue, green, Num : array [1..100] of longint;
Vblue : array [1..100] of real;
i,j,K,N,x,y,NumBlue,NumGreen,Deleted : longint;
z,T : real;
function min(a,b:real):real;
begin
if a<b then min:=a else min:=b
end;
procedure Sort;
begin
for i:=1 to Deleted-1 do
begin
x:=Num[i]; y:=i;
for j:=i+1 to Deleted do
if num[j]<x
then begin x:=Num[j]; y:=j; end;
Num[y]:=Num[i]; Num[i]:=x;
end;
end;
begin
assign(input,map.in); reset(input);
assign(output,victory.out); rewrite(output);
read(N,K);
for x:=1 to N do
for y:=1 to N do a[x,y]:=1000000000000.0;
for i:=1 to K do
begin
read(x,y,z);
a[x,y]:=z; a[y,x]:=z;
end;
read(NumBlue);
for i:=1 to NumBlue do read(Blue[i],VBlue[i]);
read(NumGreen);
for i:=1 to NumGreen do read(Green[i]);
read(T);
for i:=1 to N do
for x:=1 to N do
for y:=1 to N do
a[x,y]:=min(a[x,y],a[x,i]+a[i,y]);
Deleted:=0;
for i:=1 to NumGreen do
for j:=1 to NumBlue do
if a[Green[i],Blue[j]]<=Vblue[j]*T+0.00001
then
begin
inc(Deleted);
Num[Deleted]:=Green[i];
break;
end;
Sort;
writeln(Deleted);
for I:=1 to Deleted do write(Num[i], );
close(input); close(output);
end.
2.2 Задача "Пирамида Хеопса" (Автор - Котов В.М.)
Республиканская олимпиада по информатике 1996г
Внутри пирамиды Хеопса есть N комнат, в которых установлены 2М модулей, составляющих М устройств каждое устройство состоит из двух модулей, которые располагаются в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за 0.5 условных единицы времени. В начальный момент времени модули всех устройств переходят в "подготовительный режим". Каждый из модулей имеет некоторый свой целочисленный период времени, в течение которого он находится в "подготовительном режиме". По истечении этого времени модуль мгоновенно "срабатывает" после чего опять переходит в "подготовительный режим". Устройством можно воспользоваться только в тот момент, когда одновременно "срабатывают" оба его модуля.
Индиана Джонс сумел проникнуть в гробницу фараона (комната 1). Обследовав ее, он включил устройства и собрался уходить, но в этот момент проснулся хранитель гробницы. Теперь Джонсу необходимо как можно быстрее попасть в комнату N, в которой находится выход из пирамиды. При этом из комнаты в комнату он может попадать только при помощи устройств, так как проснувшийся хранитель закрыл все двери в комнатах пирамиды.
Необходимо написать программу, которая получает на входе описания расположения устройств и их характеристик (смотри описание формата ввода), а выдает значение оптимального времени и последовательность устройств, которыми надо воспользоваться, что бы попасть из комнаты 1 в комнату N за это время.
Входной файл: input2.txt Выходной файл: output2.txt
Формат ввода:
N
M
R11 T11 R12 T12
RM1 TM1 RM2 TM2
где N (2<=N<=100) - количество комнат
M (M<=100) - количество устройств
Ri1 и Ri2 - номера комнат, в которых располагаются модули устройства i Ti1, Ti2 (Ti1,Ti2<=1000) - периоды времени, через которые срабатывают эти модули Все числа - натуральные.
Пример
4
5
1 5 3 2
1 1 2 1
2 5 3 5
4 4 3 2
3 5 4 5
Оптимальное время: 8.5 искомая последовательность: 2 3 4
Кратко алгоритм решения может быть изложен следующим образом.
Представив комнаты - вершинами, а пары устройств (с временами срабатывания) - взвешенными дугами, можем применить алгоритм Дейкстра для поиска кратчайшего пути от первой вершины до последней. Точнее, алгоритм Дейкстра построит кратчайшие пути от первой до всех остальных, но в данной задаче нас интересует только кратчайший путь от первой до последней. Нужно учитывать, что дуги существуют только в моменты, кратные временам срабатывания.
Рассмотрим решение более подробно.
Ввод исходных данных :
read(N,M); for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2);
nok:= (t1*t2) div Nod(t1,t2); {nok - наименьшее общее кратное}
{Nod-наибольший общий делитель}
{чисел t1 и t2}
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;
Исходный граф по условиям задачи неориентированный. Поэтому мы вводим обе дуги. При этом граф представляется в виде списка дуг смежных с текущей:
kG[i] - количество дуг из вершины i
G[i,j] - вершина, в которую из вершины i идет дуга под порядковым номером j
P[i,j] - вес дуги из вершины i вершину G[i,j]
Для вычисления nod используется функция, основанная на алгоритме Евклида:
function Nod (a,b:longint):longint;
begin
while (a<>b) do if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;
Затем проводится подготовка к выполнению алгоритма Дейкстры:
for i:=1 to N do {Для всех вершин}
begin
Labl[i]:=FREE; {Помечаем как свободную}
pred[i]:=1; {Предок - первая}
d[i]:=maxlongint; {Расстояние до первой - маx}
end;
Labl[1]:=DONE; {Первая - обработана}
Pred[1]:=0; {Предок у первой - 0}
d[1]:=0; {Расстояние от первой до первой - 0}
for j:=1 to kG[1] do {Для всех дуг из первого ребра}
d[G[1,j]]:=P[1,j]+0.5; {Расстояние до первой вершины}
{равно весу ребра + 0.5}
Заметим, что в последней строке к весу ребер добавляется 0.5, поскольку по условиям задачи перемещение с помощью устройств из одной комнаты в другую занимает 0.5 единицы времени.
Далее идет основной цикл алгоритма Дейкстра
for i:=1 to N-1 do
begin
Поиск ближайшей к первой вершине из необработанных
Пересчет кратчайших расстояний через ближайшую вершину до вершин, смежных с ближайшей
end;
Первый этап - "Поиск ближайшей к первой вершине из необработанных"
MinD:=maxlongint; {MinD - max}
for j:=1 to N do {Для всех вершин}
if (Labl[j]=FREE) {если вершина свободна}
and (d[j]<MinD) {и расстояние от нее до первой}
{вершины меньше MinD}
then
begin
MinD:=d[j]; {Заносим это расстояние в MinD}
Bliz:=j {Вершину запоминаем как ближайшую}
end;
Labl[Bliz]:=DONE; {Найденную ближайшую помечаем}
{как обработанную}
Второй этап - "Пересчет кратчайших расстояний через ближайшую вершину до вершин, смежных с ближайшей"
for j:=1 to kG[Bliz] do {Для всех вершин смежных с ближайшей}
if (Labl[G[Bliz,j]]=FREE) {Если вершина еще не обрабатывалась}
then
begin
NewTime:=Calculat(d[bliz],P[bliz,j]); {Вычислитьрасстояниедонее}
{в терминах задачи-время}
{перемешения в нее}
if d[G[Bliz,j]]> NewTime +0.5 {Если новое время лучше}
then
begin
d[G[Bliz,j]]:= NewTime+0.5; {заносим его в массив D}
pred[G[Bliz,j]]:=Bliz; {указываем ближайшую как}
end; {предыдущую для текущей}
end;
При вычислении кратчайшего расстояния до текущей вершины через ближайшую (в терминах алгоритма Дейкстра) или времени перемещения из первой комнаты через ближашую в текущую (в терминах данной задачи) используется функция Calculat (T,Tnok):
function Calculat (T:single; Tnok:longint):longint;
var i : longint;
begin
TRes:=0;
while (T>TRes) do inc(TRes,Tnok);
Calculat:=TRes ;
end;
Эта функция вычисляет время TRes (которое передается в вызывающую программу непосредственно через имя функции Calculat), ближайшее большее текущего времени T (T равно минимальному значению времени, которое потребовалось, что бы оптимальным образом добраться из первой вершины до ближайшей вершины) и кратное Tnok - периоду срабатывания пары устройств, связывающих комнаты Bliz (ближайшая) и G[Bliz,j] (текущая).
После выполнения алгоритма Дейкстра сформированы массивы
d[j] - кратчайшее расстояние от начальной вершины до вершины j
pred[j] - предок вершины j на оптимальном маршруте
По этой информации вывод результата осуществляется следующим образом:
tg:=N; i:=0; {Начиная с последней вершины}
while tg<>0 do {Пока не закончились предшествующие}
begin
inc(i); {Инкрементируем количество вершин в пути}
path[i]:=tg; {Заносим текущую в массив пути}
tg:=pred[tg]; {Переустанавливаем предыдущую}
end;
writeln(Оптимальное время: ,D[N]:0:1);
write(искомая последовательность:);
for j:=i-1 downto 1 do write( ,path[j]);
Ниже приведен полный текст решения задачи.
{$R+,E+,N+}
program by96d1s2;
const
FREE=1;
DONE=2;
var
G : array[1..100,1..100] of byte;
P : array[1..100,1..100] of longint;
D : array[1..100] of single;
Labl,pred,kG : array[1..100] of byte;
path : array[1..100] of byte;
is,t1,t2,nok,Tres,NewTime : longint;
i,j,x,y,A,B,C,N,M,tg,Bliz : byte;
r1,r2 : byte;
Yes : boolean;
MinD : single;
function Nod (a,b:longint):longint;
begin
while (a<>b) do
if a>b then a:=a-b else b:=b-a;
Nod:=a;
end;
function Calculat (T:single; Tnok:longint):longint;
var i : longint;
begin
TRes:=0;
while (T>TRes) do inc(Tres,Tnok);
Calculat:=TRes ;
end;
begin
assign(input,input2.txt); reset(input);
assign(output,output2.txt); rewrite(output);
read(N,M);
for I:=1 to N do kG[i]:=0;
for i:=1 to M do
begin
read(r1,t1,r2,t2); nok:= (t1*t2) div Nod(t1,t2);
inc(kG[r1]); G[r1,kg[r1]]:=r2; P[r1,kg[r1]]:=nok;
inc(kG[r2]); G[r2,kg[r2]]:=r1; P[r2,kg[r2]]:=nok;
end;
for i:=1 to N do
begin
Labl[i]:=FREE; pred[i]:=1; d[i]:=maxlongint;
end;
Labl[1]:=DONE; Pred[1]:=0; d[1]:=0;
for j:=1 to kG[1] do d[G[1,j]]:=P[1,j]+0.5;
for i:=1 to N-1 do
begin
MinD:=maxlongint;
for j:=1 to N do
if (Labl[j]=FREE) and (d[j]<MinD)
then begin MinD:=d[j]; Bliz:=j end;
Labl[Bliz]:=DONE;
for j:=1 to kG[Bliz] do
if (Labl[G[Bliz,j]]=FREE)
then begin
NewTime:=Calculat(d[bliz],P[bliz,j]);
if d[G[Bliz,j]]> NewTime +0.5
then
begin
d[G[Bliz,j]]:= NewTime+0.5;
pred[G[Bliz,j]]:=Bliz;
end;
end;
end;
tg:=N; i:=0;
while tg<>0 do
begin
inc(i); path[i]:=tg; tg:=pred[tg];
end;
writeln(Оптимальное время: ,D[N]:0:1);
write(искомая последовательность:);
for j:=i-1 downto 1 do write( ,path[j]);
close(input); close(output);
nd.
2.3 Задача "Эх, дороги" (Автор - Котов В.М.)
Республиканская олимпиада по информатике 1998г
Имеется N городов, которые пронумерованы от 1 до N (где N - натуральное, 1<N<=100). Некоторые из них соединены двухсторонними дорогами, которые пересекаются только в городах. Имеется два типа дорог - шоссейные и железные. Для каждой дороги известна базовая стоимость проезда по ней.
Необходимо проехать из города А в город В, уплатив минимальную сумму за проезд. Стоимость проезда зависит от набора проезжаемых дорог и от способа проезда. Так, если вы подъехали к городу С по шоссейной (железной) дороге X->C и хотите ехать дальше по дороге C->Y того же типа, то вы должны уплатить только базовую стоимость проезда по дороге C->Y. Если тип дороги C->Y отличен от типа дороги Х->C, то вы должны уплатить базовую стоимость проезда по дороге C->Y плюс 10% от базовой стоимости проезда по этой дороге (страховой взнос). При выезде из города А страховой взнос платится всегда. Написать программу, которая находит самый дешевый маршрут проезда в виде последовательности городов и вычисляет стоимость проезда по этому маршруту.
Спецификация входных данных
Входные данные находятся в текстовом файле с именем TOUR.IN и имеют следующий формат:
- в первой строке находятся число N
- во второй строке - число M (количество дорог, натуральное M<=1000);
- в каждой из следующих M строк находятся 4 числа x, y, t, p, разделенные пробелом, где x и y - номера городов, которые соединяет дорога, t - тип дороги (0 - шоссейная, 1 - железная), p - базовая стоимость проезда по ней (p - вещественное, 0<p<=1000).
- в последней строке задается номера начального и конечного городов A и B.
Спецификация выходных данных
Выходные данные должны быть записаны в текстовый файл с именем TOUR.OUT и иметь следующий формат:
- в первой строке находится число S - стоимость проезда по самому дешевому маршруту, с точностью 2 знака после запятой;
- в каждой из последующих строк, кроме последней, находится два числа - номер очередного города в маршруте (начиная с города А) и тип дороги, по которой он выезжает из этого города (0 или 1), разделенные пробелом.
- в последней строке находится единственное число - номер города B.
Пример входного файла Пример выходного файла
TOUR.IN TOUR.OUT
3 22.0
2 1 0
1 2 0 10.00 2 1
2 3 1 10.00 3
1 3
Метод Дейкстра непосредственно (города - вершины) не может быть применен, поскольку оптимальный маршрут может потребовать заезда в один и тот же город два раза с целью меньше платить за страховой сбор на выезд из этого города.
Вводим 2*N вершин (где N - число городов). Для каждого города - две вершины. Первая, если мы въехали в город по дороге типа 0, вторая - если въехали в город по дороге типа 1.
Теперь можно применять непосредственно метод Дейкстра для вычисления кратчайших расстояний от заданного города A до всех введенных вершин.
Для конечного города B мы выбираем лучший из вариантов - заехать в B по дороге типа 0 или по дороге типа 1.
Метод Дейкстра позволяет сохранять предшественников вершин на оптимальном маршруте, что и используется для вывода полного ответа в заданном формате.
Рассмотрим решение задачи более подробно, основываясь на тексте программы - решения:
Ввод исходных данных осуществляется следующим образом:
read(N); {N - число городов}
read(M); {M - число дорог}
for x:=1 to N do {Устанавливаем}
for y:=1 to N do {между всеми городами}
for t:=0 to 1 do p[x,y,t]:=MAXR; {максимальную стоимость}
for i:=1 to M do {x - номер города "откуда"}
begin {y - номер города "куда"}
readln (x,y,t,p[x,y,t]); {t - тип дороги}
p[y,x,t]:=p[x,y,t]; {P[x,y,t] - стоимость}
end; {проезда от x к y по дороге типа t}
read(A,B); {Начальный и конечный пункты маршрута}
Подготовка к выполнению алгорима Дейкстра:
for i:=1 to N do {При выезде из города}
for t:=0 to 1 do {страховой взнос}
p[a,i,t]:=1.1*p[a,i,t]; {платится всегда}
for i:=1 to N do {Для всех городов}
begin {кратчайшие стоимости до первого}
D[i,0]:=P[a,i,0]; {по шоссейной дороге}
D[i,1]:=P[a,i,1]; {по железной дороге}
end;
for i:=1 to N do {Для всех городов}
begin
Labl[i,0]:=FREE; {Свободны}
Labl[i,1]:=FREE; {по обоим типам дорог}
pred[i,0]:=A; {Предыдущий город равен A}
pred[i,1]:=A; {для обоих типов дорог}
end;
Labl[A,0]:=DONE; {Начальный город обработан}
abl[A,1]:=DONE; {для обоих типов дорог}
pred[A,0]:=0; {Предыдущий у начального-0}
pred[A,1]:=0; {для обоих типов дорог}
Основная часть алгоритма Дейкстра представляет собой цикл по количеству вершин оставшихся необработанными
for i:=1 to 2*N-2 do
begin
Поиск ближайшей к первой вершине из необработанных
Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей end;
Первый этап - "Поиск ближайшей к первой вершине из необработанных"
MinD:=MaxR; {MinD - максимум}
for J:=1 to N do {Для всех городов}
for t:=0 to 1 do {Для дорог обоих типов}
if (Labl[j,t]=FREE) {Если въезд в город j по дороге типа t}
and {еще не обрабатывался и}
(minD>d[j,t]) {стоимость от города A до города j}
then {по дороге типа t меньше чем MinD, то}
begin
Bliz:=j; {Ближайшаяя - j}
bt:=t; {ее тип - bt}
MinD:=d[j,t] {минимальную стоимость в MinD}
end;
Labl[Bliz,bt]:=DONE; {Пометить как обработанную вершину}
{с минимальной стоимостью от города A}
{из еще необработанных вершин}
Второй этап - "Пересчет наименьших стоимостей через ближайшую вершину до вершин, смежных с ближайшей"
for j:=1 to N do {Для всех городов}
for t1:=0 to 1 do {Для дорог обоих типов}
if (Labl[j,t1]=FREE) {Если дорога до города j типа t необработана}
and (d[j,t1] {и стоимость до нее от вершины A}
> {больше чем}
d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1]) {стоимость через ближайшую}
then {то}
begin
d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1]; {заменяем стоимость}
Pred[j,t1]:=Bliz; Typp[j,t1]:=bt; {запоминаем}
end; {предыдущие город и тип дороги}
При вычислении стоимости проезда через ближайшую вершину учитывается страховой сбор при переходе с дороги одного типа на дорогу другого типа с помощью функции C(t1,t2):
function C(t1,t2:byte):real;
begin
if t1=t2 then C:=1.0 else C:=1.1
end;
Вывод результатов осуществляется так:
G:=B; is:=0; {Текущий город - конечный город}
if d[B,0]<d[B,1] {Тип въезда -}
then t:=0 else t:=1; {лучший из двух возможных}
stt[1]:=t; {Текущий тип - выбранный лучший}
while (G<>0) do {Пока текущий город не равен 0}
begin
inc(is); {Инкрементируем количество городов}
stg[is]:=pred[G,t]; {сохраняем текущий город в путь}
stt[is+1]:=typp[G,t]; {и его тип}
NG:=pred[G,t]; {Переустанавливаем текущие город}
NT:=typp[G,T]; {и тип на предыдущие город}
G:=NG; t:=NT; {и тип}
end;
writeln(min(d[B,0],d[B,1]):0:2); {выводим минимальную стоимость}
for i:=is-1 downto 1 do writeln(stg[i], ,stt[i]); {и путь}
writeln(B); {добавляем в путь последний город}
Далее приводится полный текст решения задачи.
{$R+,E+,N+}
program by98d1m2;
const
FREE = 0;
DONE = 1;
MAXR = 1e4;
var
p : array [1..80,1..80,0..1] of single;
D : array [1..80,0..1] of single;
pred : array [1..80,0..1] of 0..100;
typp,Labl : array [1..80,0..1] of 0..1;
stg : array [1..100] of 0..100;
stt : array [1..100] of 0..1;
M : 0..1000;
N,x,y,A,B,i,k,j,G,NG : 0..100;
t,t1,t2,bt,NT : 0..1;
is,Bliz : 0..100;
Mind : single;
Mint,MT : byte;
function C(t1,t2:byte):real;
begin
if t1=t2 then C:=1.0 else C:=1.1
end;
function min(x,y:single):single;
begin
if x<=y then min:=x else min:=y
end;
begin
assign(input,tour.in); reset(input);
assign(output,tour.out); rewrite(output);
read(N);
read(M);
for x:=1 to N do
for y:=1 to N do
for t:=0 to 1 do p[x,y,t]:=MAXR;
for i:=1 to M do
begin
readln (x,y,t,p[x,y,t]); p[y,x,t]:=p[x,y,t];
end;
read(A,B);
for i:=1 to N do
for t:=0 to 1 do p[a,i,t]:=1.1*p[a,i,t];
for i:=1 to N do
begin D[i,0]:=P[a,i,0]; D[i,1] :=P[a,i,1]; end;
for i:=1 to N do
begin
Labl[i,0]:=FREE; Labl[i,1]:=FREE;
pred[i,0]:=A; pred[i,1]:=A;
end;
Labl[A,0]:=DONE; Labl[A,1]:=DONE; pred[A,0]:=0; Pred[A,1]:=0;
for i:=1 to 2*N-2 do
begin
MinD:=MaxR;
for J:=1 to N do
for t:=0 to 1 do
if (Labl[j,t]=FREE) and (minD>d[j,t])
then begin
Bliz:=j; bt:=t; MinD:=d[j,t]
end;
Labl[Bliz,bt]:=DONE;
for j:=1 to N do
for t1:=0 to 1 do
if (Labl[j,t1]=FREE) and
(d[j,t1]>d[Bliz,bt] + C(t1,bt)*P[Bliz,j,t1])
then begin
d[j,t1]:=d[Bliz,bt]+C(t1,bt)*P[Bliz,j,t1];
Pred[j,t1]:=Bliz; Typp[j,t1]:=bt;
end;
end;
G:=B; is:=0;
if d[B,0]<d[B,1] then t:=0 else t:=1;
stt[1]:=t;
while (G<>0) do
begin
inc(is);
stg[is]:=pred[G,t]; stt[is+1]:=typp[G,t];
NG:=pred[G,t]; NT:=typp[G,T];
G:=NG; t:=NT;
end;
writeln (min(d[B,0],d[B,1]):0:2);
for i:=is-1 downto 1 do writeln(stg[i], ,stt[i]);
writeln(B);
close(input); close(output);
end.
3.1 Задача "Дороги"
Республиканская олимпиада по информатике 1997г
Дана система односторонних дорог, определяемая набором пар городов. Каждая такая пара (i,j) указывает, что из города i можно проехать в город j, но это не значит, что можно проехать в обратном направлении.
Необходимо определить, можно ли проехать из заданного города А в заданный город В таким образом, чтобы посетить город С и не проезжать ни по какой дороге более одного раза.
Входные данные задаются в файле с имене м PATH.IN следующим образом. В первой строке находится натуральное N(N<=50) - количество городов (города нумеруются от 1 до N). Во второй строке находится натуральное M(M<=100) - количество дорог. Далее в каждой строке находится пара номеров городов, которые связывает дорога. В последней (M+3)-й строке находятся номера городов А, В и С.
Ответом является последовательность городов, начинающаяся городом А и заканчивающаяся городом В, удовлетворяющая условиям задачи, который должен быть записан в файл PATH.OUT в виде последовательности номеров городов по одному номеру в строке. Первая строка файла должна содержать количество городов в последовательности. При отсутствии пути записать в первую строку файла число -1.
Пример Ответ
3 3
2 1
1 2 2
2 3 3
1 3 2
Кратко идея решения может быть изложена следующим образом:
Поиск в глубину.
Если встречаем вершину B, устанавливаем соответствующий флаг.
Если встречаем вершину C и флаг B установлен - выводим результат и завершаем работу.
После завершения поиска (требуемый маршрут не найден) выводим -1.
Изложим решение более подробно.
Ввод исходных данных осуществляется следующим образом:
read(N,M);
for i:=1 to M do
begin
read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
Здесь, как и прежде,
kG[i] - количество дуг из вершины i
G[i,j] - (для j от 1 до kG[j]) - вершины, с которыми вершина i связана соответствующей дугой/
Кроме того, введен цвет дуги
FREE - свободна (DONE - занята, FREE/DONE - константы)
Главная программа фактически включает только следующие операторы:
LabC:=0; {Установить метку - вершину C еще не посещали}
DFS(A); {Поиск в глубину от вершины A}
writeln(-1); {Вывод признака отсутствия требуемого пути}
Рекурсивная процедура поиска в глубину от вершины V выглядит следующим образом:
procedure DFS(v:byte);
var j : byte;
begin
for j:=1 to kG[v] do
if (color[v,j]=FREE)
then
begin
if (G[v,j]=B) and (LabC=1)
then begin OutRes; halt; end;
if G[v,j]=C then LabC:=1;
color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];
DFS(G[v,j]);
color[v,j]:=FREE; sled[ks]:=0; dec(ks);
if G[v,j]=C then LabC:=0;
end;
end;
То есть для всех еще необработанных (color[v,j]=FREE) дуг от текущей вершины выясняем - если она ведет в конечный пункт, а город C уже проходили - вызов процедуры вывода результата и останов.
Если текущая дуга ведет в город С, устанавливаем соответствующую метку (LabC=1).
Помечаем дугу как обработанную, заносим ее в массив SLED, который содержит текущий обрабатываемый путь, KS - количество элементов в нем.
Вызываем процедуру DFS от вершины (G[v,j]), в которую ведет текущая дуга.
Перед выходом из процедуры DFS восстанавливаем состояние, "исходное" перед ее вызовом: снимаем отметку обработки с дуги (color[v,j]:=FREE), удаляем ее из массива SLED (dec(ks), оператор sled[ks]:=0; делать необязательно, но он предоставляет удобства отладки - что бы в масcиве SLED ненулевыми были только реально входящие в путь элементы).
И, наконец, процедура вывода результата:
procedure OutRes;
begin
writeln(ks+2);
writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
Поскольку по алгоритму построения начальный (A) и конечный (B) города не заносились в массив SLED, то они выводятся отдельно, а количество городов в пути (KS) перед выводом увеличивается на 2.
Полный текст программы приводится ниже.
program by97d2s3;
const
FREE=1;
DONE=2;
var
G,color : array[1..50,1..100] of byte;
D : array[1..50] of longint;
kG,sled : array[1..50] of byte;
path : array[1..100] of byte;
MinD,is : longint;
i,j,x,y,A,B,C,N,M,ks,LabC : byte;
Yes : boolean;
procedure OutRes;
begin
writeln(ks+2);
writeln(A); for i:=1 to ks do writeln(sled[i]); writeln(B);
end;
procedure DFS(v:byte);
var j : byte;
begin
for j:=1 to kG[v] do
if (color[v,j]=FREE)
then
begin
if (G[v,j]=B) and (LabC=1)
then begin OutRes; halt; end;
if G[v,j]=C then LabC:=1;
color[v,j]:=DONE; inc(ks); sled[ks]:=G[v,j];
DFS(G[v,j]);
color[v,j]:=FREE; sled[ks]:=0; dec(ks);
if G[v,j]=C then LabC:=0;
end;
end;
begin
assign(input,path.in); reset(input);
assign(output,path.out); rewrite(output);
read(N,M);
for i:=1 to M do
begin
read(x,y); inc(kG[x]); G[x,kG[x]]:=y; color[x,kG[x]]:=FREE;
end;
read(A,B,C);
LabC:=0;
DFS(A);
writeln(-1);
close(input); close(output);
nd.
3.2 Задача "Перекрестки" (Автор - Котов В.М.)
Республиканская олимпиада по информатике 1998г
Даны декартовы координаты N перекрестков города, которые пронумерованы от 1 до N. На каждом перекрестке имеется светофор. Некоторые из перекрестков соединены дорогами с двухсторонним (правосторонним) движением, которые пересекаются только на перекрестках. Для каждой дороги известно время, которое требуется для проезда по ней от одного перекрестка до другого.
Необходимо проехать от перекрестка с номером А до перекрестка с номером В за минимальное время.
Время проезда зависит от набора проезжаемых дорог и от времени ожидания на перекрестках. Так, если вы подъехали от перекрестка X к перекрестку C по дороге Х->C и хотите ехать дальше по дороге C->У, то время ожидания на перекрестке C эависит от того, поворачиваете ли вы налево или нет. Если вы поворачиваете налево, то время ожидания равно D*К, где D равно количеству дорог, пересекающихся на перекрестке C, а К - некоторая константа. Если вы не поворачиваете налево, то время ожидания равно нулю.
Написать программу, которая определяет самый быстрый маршрут.
Спецификация входных данных.
Входные данные находятся в текстовом файле с именем PER.IN и имеют следующую структуру:
- в первой строке находится число N (натуральное, <=1000);
- во второй строке - количество дорог M (натуральное, <=1000);
- в третьей строке - константа K (натуральное число, <=1000);
- в каждой из N следующих стpок находится паpа чисел х и у, разделенных пробелом, где x, y - кооpдинаты перекрестка (целые числа, не пpевышающие по модулю 1000);
- в каждой из M следующих строк находится 3 числа p, r, t, разделенные пробелом, где p и r - номера перекрестков, которые соединяет дорога, а t (натуральное, <=1000) - время проезда по ней;
- в последней строке находятся номера начального А и конечного В перекрестков.
Спецификация выходных данных.
Выходные данные должны быть записаны в текстовый файл с именем PER.OUT и иметь следующий формат:
- в первой строке находится натуральное число T - время проезда по самому быстрому маршруту;
- в каждой из следующих строк находится одно число - номер очередного перекрестка в маршруте (начиная с перекрестка с номером А и кончая В).
Кратко идея решения может быть изложена следующим образом.
Алгоритм Дейкстры напрямую не применим, поскольку:
а) оптимальное решение в следующей вершине не является суммой оптимального решения для предыдущей вершины и веса текущего ребра
б) вес текущего ребра - непостоянная величина, зависящая от того, каким поворотом мы вышли из вершины.
Поэтому предлагается решение поиском в глубину. При этом разрешается использовать каждую вершину столько раз, сколько у нее есть ребер. Отсекаются решения хуже текущего оптимального.
Можно еще ускорить решение, если обеспечивать перебор, начиная с правых поворотов (отсечения работали бы более эффективно).
Замечание:
В тексте задачи явно не указано, но авторы оригинальных тестов к задаче полагали, что поворот на 180 градусов - это левый поворот (как в армии: поворот на 180 градусов - "через левое плечо").
Рассмотрим решение более подробно:
Ввод исходных данных осуществляется следующим образом:
read(N,M,K);
for i:=1 to N do readln(x[i],y[i]);
for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;
for i:=1 to M do
begin
readln(p,r,t); inc(kG[p]); inc(kG[r]);
G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);
G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);
end;
readln(vA,vB);
Здесь
kG[i] - количество дуг из вершины i
G[i,j,1] - вершина, с которой соединена вершина i дугой
с номером j в списке всех дуг из вершины i.
$G[i,j,2] - время проезда от вершины i до вершины, с которой она соединена дугой j в списке всех дуг из вершины i.
D[i] - количество дорог, пересекающихся на перекрестке i (то есть суммарное количество дуг, исходящих из вершины i и входящик в нее)
vA и vB указывают, откуда и куда нужно добираться.
Поскольку по условиям задачи дороги двусторонние, то, для каждой введенной дороги, мы добавляем в граф две дуги.
Основной алгоритм выглядит следующим образом:
for i:=1 to N do
begin
for j:=1 to kG[i] do Color[i,j]:=WHITE; {все дуги свободны}
Time[i]:=maxlongint; {время маршрута до I - максимально}
end;
OptT:=Maxlongint; {Оптимальное время - максимально}
Sled[1]:=vA; {Заносим в маршрут вершину vA}
kv:=1; {Количество вершин в маршруте = 1}
Time[vA]:=0; {Оптимальное время до вершины vA =0}
DFS(vA); {Поиск в глубину от вершины vA}
... вывод ответа ...
Рекурсивная процедура DFS(i) обеспечивает выполнение cледующей работы:
Procedure DFS(i)
...
begin
for j:=1 to kG[i] do
if G[i,j,1]<>vB
then
begin
if color[i,j]=FREE
then
begin
... продолжение пути с вызовом DFS
end
end
else
begin
... сравнение пути с текущим оптимальным
end;
end;
Если текущая вершина - конечная (vB), то делаем " ... сравнение пути с оптимальным"
Иначе проверяем, если текущая дуга еще не использовась (color[i,j]=FREE) то делаем "... продолжение пути с вызовом DFS".
При этом, перед входом в DFS помечаем дугу как использованную (color[i,j]:=DONE), а после выхода - как вновь свободную (color[i,j]:=FREE);
"... продолжение пути с вызовом DFS" включает в себя следующие операторы:
inc(kv); sled[kv]:=G[i,j,1]; {помещаем в путь новую вершину}
NewTime:=Time[i]+G[i,j,2]+CountTime; {вычисляем новое время}
if NewTime<OptT {если новое время меньше оптимального}
then {то продолжаем,иначе - отсекаем}
begin
color[i,j]:=DONE; {Помечаем - ребро использовано}
RetTime:=Time[G[i,j,1]]; {Сохраняем старое время}
Time[G[i,j,1]]:=NewTime; {Устанавливаем новое время}
DFS(G[i,j,1]); {Вызываем поиск от G[i,j,1]}
Time[G[i,j,1]]:=RetTime; {Восстанавливаем старое время}
color[i,j]:=FREE; {Помечаем - ребро свободно}
end;
Sled[kv]:=0; dec(kv); {Удаляем вершину из пути}
Для вычисления нового времени здесь используется функция CounTime с параметром kv - номер последней вершины в стеке.Эта функция делает следующее: Восстанавливает номера вершин, прохода через перекресток "из i1 через i2 в i3":
if kv=2 then begin CountTime:=0; exit; end;
i1 := sled[kv-2];
i2 := sled[kv-1];
i3 := sled[kv];
if i3=i1 then begin CountTime:=K*D[i2]; exit; end;
Попутно, выясняется
а) если вершин в пути всего 2, то есть не было никакого поворота - это шаг из начальной вершины и CountTime=0.
б) если i1=i3 то это поворот на 180 градусов и авторы задачи считают, что это тоже левый поворот, CountTime=K*D[i2]; где, K - коэффициент который вводится, i2 - перекресток, D[i2] - количество дорог, входящих в этот перекресток.
Затем из массивов координат перекрестков выбираются координаты текущих перекрестков: (x1,y1) (откуда); (x2,y2) (через какой); (x3,y3) (куда).
x1 := x[i1]; x2:=x[i2]; x3:=x[i3];
y1 := y[i1]; y2:=y[i2]; y3:=y[i3];
Вычисляется уравнение прямой по точкам (x1,y1) и (x2,y2)
A := y2-y1;
B := x1-x2;
C := y1*(x2-x1)-x1*(y2-y1);
Подстановкой координат (x3,y3) в уравнение прямой Ax+By+C=0, построенной по первым двум точкам (x1,y1) и (x2,y2) и с учетом крайних случаев, когда прямая параллельна осям координат, вычисляем, был ли поворот левым или правым и соответственно устанавливаем значение функции CountTime.
Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or
(((x2<x1) and ((A*x3+B*y3+C)<0))) or
(((y2=y1) and (x1>x2) and (y3<y1))) or
(((y2=y1) and (x1<x2) and (y3>y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1<y2) and (x3<x1))) ;
if Left
then CountTime:=K*D[i2]
else CountTime:=0;
"Сравнение пути с оптимальным" выполняется следующим образом:
inc(kv); sled[kv]:=G[i,j,1];
T := Time[i]+G[i,j,2] + CountTime;
if T < OptT
then begin
OptT:=T;
OptKv:=kv; OptSled:=Sled;
end;
Sled[kv]:=0; dec(kv);
Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так:
writeln(OptT);
for i:=1 to OptKv do writeln(OptSled[i]);
Полный текст программы приводится ниже
program by98d2s2;
Const
FREE = 1;
DONE = 2;
Type
int1000 = 0..1000;
int3 = 1..3;
var
G : array[1..1000,1..10,1..2] of int1000;
Time,D : array[1..1000] of longint;
x,y,kG,Sled,OptSled,pred : array[1..1000] of int1000;
Color : array[1..100,1..10] of int3;
N,M,K,i,p,r,t,vA,vB,v,kv,OptKv,j : int1000;
OptT : longint;
function CountTime(i:int1000):longint;
var
Left : boolean;
i1,i2,i3 : int1000;
x1,x2,x3,y1,y2,y3,A,B,C : longint;
begin
if kv=2 then begin CountTime:=0; exit; end;
i1 := sled[kv-2];
i2 := sled[kv-1];
i3 := sled[kv];
if i3=i1 then begin CountTime:=K*D[i2]; exit; end;
x1 := x[i1]; x2:=x[i2]; x3:=x[i3];
y1 := y[i1]; y2:=y[i2]; y3:=y[i3];
A := y2-y1;
B := x1-x2;
C := y1*(x2-x1)-x1*(y2-y1);
Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or
(((x2<x1) and ((A*x3+B*y3+C)<0))) or
(((y2=y1) and (x1>x2) and (y3<y1))) or
(((y2=y1) and (x1<x2) and (y3>y1))) or
(((x2=x1) and (y1>y2) and (x3>x1))) or
(((x2=x1) and (y1<y2) and (x3<x1))) ;
if Left
then CountTime:=K*D[i2]
else CountTime:=0;
end;
Procedure DFS(i:int1000);
var
j : byte;
T : longint;
RetSled,RetPred,RetTime :longint;
begin
for j:=1 to kG[i] do
if G[i,j,1]<>vB
then
begin
if color[i,j]=FREE
then
begin
inc(kv); sled[kv]:=G[i,j,1];
NewTime:=Time[i]+G[i,j,2]+CountTime;
if NewTime<OptT
then
begin
color[i,j]:=DONE;
RetTime:=Time[G[i,j,1]];
Time[G[i,j,1]]:=NewTime;
DFS(G[i,j,1]);
Time[G[i,j,1]]:=RetTime;
color[i,j]:=FREE;
end;
Sled[kv]:=0; dec(kv);
end
end
else
begin
inc(kv); sled[kv]:=G[i,j,1];
T := Time[i]+G[i,j,2] + CountTime;
if T < OptT
then begin
OptT:=T;
OptKv:=kv; OptSled:=Sled;
end;
Sled[kv]:=0; dec(kv);
end;
end;
begin
assign(input,PER.in); reset(input);
assign(output,PER.out); rewrite(output);
read(N,M,K);
for i:=1 to N do readln(x[i],y[i]);
for i:=1 to N do begin kG[i]:=0; D[i]:=0; end;
for i:=1 to M do
begin
readln(p,r,t); inc(kG[p]); inc(kG[r]);
G[p,kG[p],1]:=r; G[p,kG[p],2]:=t; inc(D[p]);
G[r,kG[r],1]:=p; G[r,kG[r],2]:=t; Inc(D[r]);
end;
readln(vA,vB);
for i:=1 to N do
begin
for j:=1 to kG[i] do Color[i,j]:=FREE;
Time[i]:=maxlongint;
end;
Time[vA]:=0; kv:=1; Sled[1]:=vA; OptT:=Maxlongint;
DFS(vA);
writeln(OptT);
for i:=1 to OptKv do writeln(OptSled[i]);
close(input); close(output);
end.
3.3 Задача "Скрудж Мак-Дак" (Автор - Котов В.М.)
Республиканская олимпиада по информатике 1995г
Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.
Его механик Винт Р. сделал устройство, вычисляющее эту функцию в несколько этапов с использование промежуточной памяти и вспомогательных функций. Для вычисления каждой из функций требуется, чтобы в ячейках памяти уже находились вычисленные параметры (которые являются значениями вычисленных функций), необходимые для ее вычисления. Вычисление функции без параметров может производится в любое время.
После вычисления функции ячейки могут быть использованы повторно (хотя бы для записи результата вычисленной функции). Структура вызова функций такова, что каждая функция вычисляется не более одного раза и любой параметр используется не более одного раза. Любой параметр есть имя функции. Так как Скрудж не хочет тратить лишних денег на микросхемы, он поставил задачу минимизировать память прибора. По заданной структуре вызовов функций необходимо определить минимальный возможный размер памяти прибора и указать последовательность вычисления функций.
Входной файл INPUT.TXT
Формат ввода:
1 строка> <общее количество функций N>
2 строка> <имя функции, которую небходимо вычислить>
3 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
...
N+2 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
Выходной файл OUTPUT.TXT
Формат вывода:
Размер памяти (в ячейках)
имя 1-й вычисляемой функции
имя 2-й вычисляемой функции
....
имя функции, которую необходимо вычислить
Примечание: имя функции есть натуральное число от 1 до N.
Пример.
Ввод Вывод
5 Размер памяти: 2 ячейки
1 Порядок:
1 2 2 3 Функция 4
2 0 Функция 5
3 2 4 5 Функция 3
4 0 Функция 2
5 0 Функция 1
В кратком изложении в данной задаче требуется сделать следующее:
- найти S - максимальную степень среди тех вершин, что подлежат обходу (поиск в глубину DFS1)
- необходимая память вычисляется по формуле
MaxS = S + k -1
где S - найдено на предыдущем шаге (DFS1),
а k - максимальное количество вершин одного уровня вложенности с такой же степенью S.
Для вычисления k совершается обход повторным поиском в глубину DFS2
- третьим поиском в глубину DFS3 находим и помещаем в очередь V все вершины, степень которых равна S.
- последним, четвертым поиском в глубину обходим данное дерево в порядке вершин в очереди V. То есть, в первую очередь вычисляем те функции, для которых требуется максимальная память.
Рассмотрим реализацию алгоритма более подробно.
Ввод исходных данных осуществляется следующим образом:
Read (N,FC);
for i:=1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
Здесь
N - исходное количество вершин,
FC - номер функции, которую нужно вычислить
kG[i] - количество параметров для вычисления функции i
G[i,j] - j-тый параметр, требуемый для вычисления функции i
Тело главной программы выглядит так :
for i:=1 to N do color[i]:=WHITE; {пометить свободными все вершины}
DFS1(FC); {находим S - максимальную степень вершин используемых для вычисления функции FC}
MaxS:=S;
DFS2(FC); {Вычисляем
K - количество вершин со степенью S в текущем слое и
MaxS - максимальная из значений по слоям величина S+K-1}
kv:=0;
DFS3(FC); {Поместить в массив V все вершины, степень которых равна S, количество таких вершин - в переменной kv}
kr:=0;
for i:=1 to kv do DFS4(v[i]); {Обход графа поиском в глубину начиная с вершин с максимальной степенью из массива V.
Найденные вершины заносить в массив r}
writeln(MaxS); {вывод количества ячеек памяти}
for i:=1 to kr do writeln(r[i]); {вывод порядка вычисления функций}
Полное решение задачи приводится ниже
program by95d2t1;
const
WHITE = 1;
GRAY = 2;
BLACK = 3;
var
G : array [1..100,1..100] of longint;
kG,v,color,r : array [1..100] of longint;
N,FC,i,j,s,f,kv,MaxS,kr : longint;
procedure DFS1(u:longint);
var
i,k : longint;
begin
if s<kG[u] then s:=kG[u];
for i:=1 to kG[u] do DFS1(G[u,i]);
end;
procedure DFS2(u:longint);
var
i,k : longint;
begin
k:=0;
for i:=1 to kG[u] do
if kG[G[i,j]]=s then inc(k);
if MaxS<s+k-1 then MaxS:=s+k-1;
for i:=1 to kG[u] do DFS2(G[u,i]);
end;
procedure DFS3(u:longint);
var
i,k : longint;
begin
if kG[u]=s
then
begin
for i:=1 to kG[u] do DFS3(G[u,i]);
nc(kv); v[kv]:=u;
end;
end;
procedure DFS4(u:longint);
var
i : longint;
begin
color[u]:=GRAY;
if kG[u]<>0
then
for i:=1 to kG[u] do
if color[G[u,i]]<>GRAY
then DFS4(G[u,i]);
inc(kr); r[kr]:=u;
end;
begin
assign(input,input.txt); reset(input);
assign(output,output.txt); rewrite(output);
read(N,FC);
for i:=1 to N do
begin
read(f,kG[f]);
for j:=1 to kG[f] do read(G[f,j]);
end;
for i:=1 to N do color[i]:=WHITE;
DFS1(FC);
MaxS:=s; DFS2(FC);
kv:=0; DFS3(FC);
kr:=0; for i:=1 to kv do DFS4(v[i]);
writeln(MaxS);
for i:=1 to kr do writeln(r[i]);
close(input); close(output);
end.
4.1 Задача "Карточки"
Республиканская олимпиада по информатике 1994г
1. Есть N карточек. На каждой из них черными чернилами написан ее уникальный номер - число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми "красными" числами могут помечаться несколько карточек).
Например, N=5, 5 карточек помечены следующим образом:
---------------
"черное" число ¦ 1¦ 2¦ 3¦ 4¦ 5¦
---------------
"красное" число ¦ 3¦ 3¦ 2¦ 4¦ 2¦
---------------
Необходимо выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества "красных" и "черных" чисел на них совпадали.
Для примера выше это будут карточки с "черными" номерами 2, 3, 4 (множество красных номеров, как и требуется в задаче, то же - {2,3,4}).
ВВОД: <N=> N, N<=50
<"Черный" номер 1, "красный" -> "красное"_число_1
......
<"Черный" номер N, "красный" -> "красное"_число_N
ВЫВОД:
<В выбранном множестве элементов количество элементов> S
<"Черные" номера выбранных карточек> a1, ..., aS
Пример ввода Пример вывода
6 6
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
6 6 6
Фактически в задаче требуется найти все сильно связные компоненты представляемого карточками ориентированного графа и добавить к ним карточки, на которых и красным и черным цветом написаны одни и те же числа.
Опишем решение задачи более подробно, опираясь на исходный текст соответствующей программы.
Тело главной части программы будет выглядеть так:
readln(N); {Читаем количество карточек}
M:=0; {Количество карточек в результате}
for i:=1 to N do {Для всех карточек}
begin
readln(u,v); {Читаем карточку}
inc(kG[u]); G[u,kG[u]]:=v; {Пополняем по ней граф}
if u=v {Если красное число равно черному}
then
begin inc(M); T[M]:=u;end; {заносим карточку в результат}
end;
BuildDominators; {Строим множество доминаторов}
Reverse; {Обращаем граф}
BuildDominators2; {Строим множество доминаторов обращенного графа, попутно получая все сильносвязные компоненты графа}
Рассмотрим процедуру BuildDominators:
Procedure BuildDominators;
begin
Time:=0; {Время обработки вершин = 0}
for i:=1 to N do {Для каждой вершины i помечаем}
begin
Color[i] := WHITE; {Вершина свободна}
Dom[i] := WHITE; {Доминаторов нет}
CurC[i] := WHITE; {Свободна на текущем шаге}
F[i] := 0; {Время завершения обработки - 0}
end;
for v:=1 to N do {Для всех вершин}
if color[v]=WHITE {Если вершина v свободна}
then
begin
DFS(v); {Поиск в глубину от вершины v}
AddDominator(v); {Добавить найденного доминатора}
end;
end;
Таким образом в ходе обработки вершин графа на этом этапе у нас есть 3 множества
Dom - найденные на текущий момент доминаторы графа
Color - все обработанные вершины
CurC - вершины, обработанные во время поиска в глубину от текущей базовой вершины V
Рекурсивная процедура поиска в глубину выглядит для данной задачи таким образом:
Procedure DFS(i:byte);
var
j : byte;
begin
color[i]:=GRAY; {Вершина i обработана вообще}
curC[i]:=GRAY; {Вершина i обработана на текущем шаге}
inc(Time); {Увеличить время обработки вершин}
for j:=1 to kG[i] do {Пока у вершины есть наследники}
if curC[G[i,j]]=WHITE {Если наследник не обрабатывался на текущем шагу}
then DFS(G[i,j]); {Запустить поиск в глубину от наследника}
inc(Time); {Увеличить время обработки вершин}
if F[i]=0 {Если вершине i не устанавливалось время}
then F[i]:=Time; {завершения обработки - то установить}
end;
Процедура AddDominator(v), также вызываемая из процедуры BuildDominators, добавляет в список доминаторов вершину v следующим образом: все вершины, достигнутые из текущей (Curc[i]<>WHITE) вычеркиваем из доминаторов; текущую добавляем в список доминаторов (dom[Domi]:=GRAY;).
Procedure AddDominator (Domi:longint);
begin
for i:=1 to N do {Для всех вершин}
if (CurC[i]<>WHITE) {Если она достигнута от текущей}
then dom[i]:=WHITE; {Вычеркиваем ее из доминаторов}
dom[Domi]:=GRAY; {Вносим текущую в список доминаторов}
for i:=1 to N do {Для всех вершин устанавливем отметку}
curC[i]:=WHITE; {недостигнута от текущей}
end;
Следующий шаг за построением доминаторов исходного графа - транспонирование графа (другими словами смена стрелок на дугах на противоположные). Это делается с помощью процедуры Reverse. Процедура Reverse по исходному графу G[1..N,1..M], kg[1..N] строит граф B[1..N,1..M], kB[1..N]:
Procedure Reverse;
begin
for i:=1 to N do KB[i]:=0; {Обнуляем количества дуг из вершины i}
for i:=1 to N do
for j:=1 to kG[i] do
begin
inc(kB[G[i,j]]); {Инкрементируем количество дуг из вершины i}
b[G[i,j],kB[G[i,j]]]:=i; {Добавляем в граф обратную дугу}
end;
end;
Процедура BuildDominator2 строит множество доминаторов на транспонированном графе, параллельно формируя сильно связные компоненты (ССК) исходного графа:
Procedure BuildDominators2;
begin
Time:=0;
for i:=1 to N do {Для всех вершин}
begin
Color[i]:=WHITE; {Свободна вообще}
CurC[i] :=WHITE; {Свободна в текущем цикле}
Kart[i]:=WHITE; {Не входит в ССК}
end;
SortF; {Сортируем в порядке убывания времена завершения обработки вершин при построении множества доминаторов исходного графа - результат Q[1..N]}
for v:=1 to N do {В порядке убывания времен обработки}
if color[Q[v]]=WHITE {Если вершина свободна}
then
begin
DFS2(Q[v]); {Построить доминатора}
AddDominator2(Q[v]); {Добавить доминатора}
end;
for i:=1 to N do {Для всех вершин}
if (Kart[i]<>WHITE) {Если входит в ССК}
then begin
inc(M); {вносим в результат}
T[M]:=i;
end;
SortT; {Сортируем результирующее множество}
writeln(M); for i:=1 to M do writeln (T[i]); {выводим его}
end;
Процедура DFS2 поиска глубину по транспонированному графу выглядит следующим образом:
Procedure DFS2(i:byte);
Var j : byte;
begin
color[i]:=GRAY; curc[i]:=GRAY;
for j:=1 to kB[i] do
if color[B[i,j]]=WHITE then DFS2(B[i,j]);
end;
Процедура AddDominator2 обеспечивающая корректное построение доминаторов транспонированного графа и сильносвязных компонент исходного (и транспонированного) графов такова:
Procedure AddDominator2 (Domi:longint);
var
MinT, MinK, KS : longint;
FlDom : boolean;
begin
KS:=0; {Количество вершин в текущей ССК}
for i:=1 to N do {Для всех вершин}
if Curc[i]<>WHITE {Если вершина достигнута}
then inc(KS); {инкрементировать к-во вершин в текущей ССК}
if ks>1 {Если в текущей ССК вершин}
then {больше чем одна}
for i:=1 to N do {то внести их всех в KART}
if CurC[i]<>WHITE then Kart[i]:=GRAY;
for i:=1 to N do curC[i]:=WHITE; {Сделать все вершины свободными для нового шага}
end;
Полный текст программы, решающей поставленную задачу приводится ниже.
program by94d1t1;
Const
WHITE = 1;
GRAY = 2;
var
G,B : array [1..100,1..100] of byte;
Color,kG,kB,Dom,CurC,Kart: array [1..100] of byte;
D,F,T,Q : array [1..100] of longint;
N,i,j,Time,v,u,M,GRA_Y : longint;
Function max(a,b:longint):longint;
begin
if (a>b) then max:=a else max:=b
end;
Procedure Reverse;
begin
for i:=1 to N do KB[i]:=0;
for i:=1 to N do
for j:=1 to kG[i] do
begin
inc(kB[G[i,j]]);
b[G[i,j],kB[G[i,j]]]:=i;
end;
end;
Procedure AddDominator (Domi:longint);
begin
for i:=1 to N do
if CurC[i]<>WHITE then dom[i]:=WHITE;
dom[Domi]:=GRAY;
for i:=1 to N do curC[i]:=WHITE;
end;
Procedure DFS(i:byte);
Var j : byte;
begin
color[i]:=GRAY; curC[i]:=GRAY; inc(Time);
for j:=1 to kG[i] do
if curC[G[i,j]]=WHITE then DFS(G[i,j]);
inc(Time);
if F[i]=0 then F[i]:=Time;
end;
Procedure BuildDominators;
begin
Time:=0;
for i:=1 to N do
begin
Color[i]:=WHITE; Dom[i]:=WHITE;
CurC[i]:=WHITE; F[i]:=0;
end;
for v:=1 to N do
if color[v]=WHITE
then begin DFS(v); AddDominator(v); end;
end;
Procedure SortF;
var
i,j,MaxD,k,Temp :longint;
begin
for i:=1 to N do Q[i]:=i;
for i:=1 to N-1 do
begin
MaxD:=F[i]; K:=i;
for j:=i+1 to N do
if F[j]>MaxD
then begin MaxD:=F[j]; k:=j; end;
F[k]:=F[i]; F[i]:=MaxD; Temp:=Q[k];
Q[k]:=Q[i]; Q[i]:=Temp;
end
end;
Procedure SortT;
var
i,j,MaxD,k,Temp :longint;
begin
for i:=1 to M-1 do
begin
MaxD:=T[i]; K:=i;
for j:=i+1 to M do
if T[j]<MaxD
then begin MaxD:=T[j]; k:=j; end;
T[k]:=T[i]; T[i]:=MaxD;
end
end;
Procedure DFS2(i:byte);
var
j : byte;
begin
color[i]:=GRAY; curc[i]:=GRAY;
for j:=1 to kB[i] do
if color[B[i,j]]=WHITE then DFS2(B[i,j]);
end;
Procedure AddDominator2 (Domi:longint);
var
MinT, MinK, KS : longint;
FlDom : boolean;
begin
KS:=0;
for i:=1 to N do
if Curc[i]<>WHITE then inc(KS);
if ks>1
then
for i:=1 to N do
if CurC[i]<>WHITE then Kart[i]:=GRAY;
for i:=1 to N do curC[i]:=WHITE;
end;
Procedure BuildDominators2;
begin
Time:=0;
for i:=1 to N do
begin
Color[i]:=WHITE;
CurC[i] :=WHITE; Kart[i]:=WHITE;
end;
SortF;
for v:=1 to N do
if color[Q[v]]=WHITE
then begin DFS2(Q[v]); AddDominator2(Q[v]); end;
for i:=1 to N do
if (Kart[i]<>WHITE)
then begin inc(M); T[M]:=i;end;
SortT;
writeln(M);
for i:=1 to M do writeln (T[i]);
end;
begin
assign(input,input.txt); reset(input);
assign(output,output.txt); rewrite(output);
readln(N);
M:=0;
for i:=1 to N do
begin
readln(u,v);
inc(kG[u]); G[u,kG[u]]:=v;
if u=v then begin inc(M); T[M]:=u;end;
end;
BuildDominators;
Reverse;
BuildDominators2;
close(input); close(output);
end.
4.2 Задача "Межшкольная сеть"
IOI96 - Международная олимпиада по информатике (Венгрия)
Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ получателей, которым она рассылает программное обеспечение всякий раз, получив новое бесплатное программное обеспечение (извне сети или из другой школы). При этом, если школа В есть в списке получателей школы А, то школа А может и не быть в списке получателей школы В.
Требуется написать програму, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, что бы распространить его по всем школам сети в соответствии с соглашениями (подзадача А).
Кроме того, надо обеспечить возможность рассылки нового программного обеспечения из любой школы по всем остальным школам. Для этого расширить списки получателей некоторых школ, добавляя в них новые школы. Требуется найти минимальное суммарное количество расширений списков, при которых программное обеспечение из любой школы достигло бы остальных школ (подзадача В). Одно расширение означает добавление одной новой школы-получателя в список получателей одной из школ.
Входные данные
Первая строка файла INPUT.TXT содержит целое число N - количество школ в сети (2<=N<=100). Школы нумеруются первыми N положительными целыми числами. Каждая из следующих N строк задает список получателей. Строка i+1 содержит номера получателей i-й школы. Каждый такой список заканчивается нулем. Пустой список содержит только 0.
Выходные данные
Ваша программа должна записать 2 строки в файл OUTPUT.TXT. Его первая строка должна содержать одно положительное целое число - решение подзадачи А. Вторая строка должна содержать решение подзадачи B.
Пример ввода и вывода
INPUT.TXT
5
2 4 3 0
4 5 0
0
0
1 0
OUTPUT.TXT
1
2
Подазадача A требует найти доминантное множество - то есть минимальное множество вершин исходного графа, из которого есть цепи ко всем остальным вершинам графа.
Обходом в глубину пока есть свободные (неперекрашенные из белого в серый цвет) вершины находим все, которые достижимы из нее. И из множества доминант вычеркиваем все достижимые на текущем ходу и добавляем в множество доминант исходную свободную.
Подзадача B требует найти количество ребер, которые нужно добавить, что бы исходный ориентированный граф стал сильно связным. По исходному графу строится транспонированный (стрелки на дугах меняются на противоположные). И для нового (транспонированного) графа опять строятся доминантное множество.
Если и первое и второе доминантное множество состоят из одного и того же элемента - вершины 1, то граф был сильносвязный и добавлять ребер не нужно. Иначе нужно добавить максимум из количеств элементов в построенных доминантных множествах.
Поскольку практически почти такая же задача полностью рассмотрена в предыдущем пункте, полное описание решения здесь не приводится.
Другое решение этой же задачи:
Методом Флойда строим матрицу достижимости.
В результате все вершины разбиваются на группы
- истоки (в них нет входящих дуг)
- стоки (из них нет исходящих дуг)
- промежуточные (есть и входящие и исходящие)
Ответ подзадачи A - количество истоков
Для подзадачи B:
Если нет ни истоков, ни стоков, то граф - ССК (сильносвязная компонента) и добавлять ребер не нужно. Иначе, выбираем максимальное из количеств истоков и стоков - это и есть количество ребер которые нужно добавить.
Пояснение: Добавляем связи между истоками и стоками в результате чего граф и становится сильносвязной компонентой
4.3 Задача "Винни-Пух и Пятачок" (Автор - Котов В.М.)
Республика, школьники, 1995г.
Винни-Пух и Пятачок нанялись защищать компьютерную сеть от хаккеров, которые выкачивали из компьютеров секретную информацию. Компьютерная сеть Винни-Пуха и Пятачка состояла из связанных между собой больших ЭВМ, к каждой из которых подключалось несколько терминалов. Подключение к одной из больших ЭВМ позволяло получить информацию, содержащуюся в памяти этой ЭВМ, а также всю информацию, доступную для ЭВМ, к которым данная ЭВМ могла направлять запросы. Хаккеры и раньше напа дали на подобные компьютерные сети и их тактика была известна. Поэтому Винни-Пух и Пятачок разработали специальную программу, которая помогла принять меры против готовившегося нападения.
Тактика хаккеров.
При нападениях хаккеры всегда получают доступ к информации всех ЭВМ сети. Добиваются они этого, захватывая некоторые ЭВМ сети, так чтобы от них можно было запросить информацию у оставшихся ЭВМ. Вариантов захвата существует множество.
Например, захватить все ЭВМ. Но хаккеры всегда выбирают такой вариант, при котором суммарное количество терминалов у захваченных ЭВМ минимально.
Примечание.
В сети Винни-Пуха и Пятачка ни у каких 2-х ЭВМ количество терминалов не совпадает.
Техническое задание.
Вам необходимо написать программу, входными данными которой было бы описание сети, а выходными - список номеров ЭВМ, которые могут быть выбраны хаккерами для захвата сети согласно их тактике. Ввод осуществляется из файла с именем INPUT.TXT. Возможен ввод с клавиатуры.
Формат ввода.
Количество ЭВМ в сети : N
ЭВМ #1 имеет терминалов : T[1]
ЭВМ #2 имеет терминалов : T[2]
...
ЭВМ #N имеет терминалов : T[N]
Права на запрос :
A[1] B[1]
A[2] B[2]
...
A[K] B[K]
0 0
A[i] и В[i] - номера ЭВМ, последняя строка 0 0 обозначает конец списка прав на запрос, каждая пара A[i] B[i] обозначает, что ЭВМ с номеров A[i] имеет право запрашивать информацию у ЭВМ с номером B[i] (A[i] не равно B[i]).
При вводе числа N и T[i] - натуральные, T[i] <=1000, N<=50, K<=2450.
Входные данные соответствуют приведенным условиям.
Формат вывода.
Номера захватываемых ЭВМ : С[1] C[2] ... С[M].
Количество захватываемых ЭВМ : <M>
Input.txt
5
100
2
1
3
10
1 3
3 2
4 3
4 5
5 4
0 0
Output.txt
1 4
2
Поиском в глубину находим множество доминаторов сети. (истоки графа). Однако для оптимального выбора машин по количеству терминалов необходимо выбрать лучшую машину (с наименьшим количеством терминалов) в каждой сильно связной компоненте.
Для этого инвертируем граф (меняем направление всех дуг графа на противоположное) и поиском в глубину по инвертированному графу находим все его сильно связные компоненты (последовательные деревья, которые получаются поиском в глубину.). Нас интересуют только сильно связные компоненты с количеством вершин больше 1. В этом случае находим из них вершину с минимальным количеством терминалов и заменяем соответствующий доминатор (если от этой ССК ранее в доминаторы попала другая вершина).
Опять же полное решение не приводится по причине его сильной близости к полному решению задач из двух предыдущих пунктов.
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |