Алгоритмы на графах. Кратчайшие расстояния на графах (стр. 3 из 3)
Входной файл INPUT.TXT
Формат ввода:
1 строка> <общее количество функций N>
2 строка> <имя функции, которую необходимо вычислить>
3 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
...N+2 строка> <имя функции> <кол-во параметров>[<список имен параметров>]
Выходной файл OUTPUT.TXT
Формат вывода:
Размер памяти (в ячейках)
имя 1-й вычисляемой функции
имя 2-й вычисляемой функции
....имя функции, которую необходимо вычислить
Примечание: имя функции есть натуральное число от 1 до N.
Пример.
В кратком изложении в данной задаче требуется сделать следующее:
- найти 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]);
inc(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.
Заключение
Существует целый класс задач по программированию, которые проще решаются, если ученик владеет определенным набором знаний, умений и навыков в области алгоритмов на графах. Это происходит потому, что такие задачи могут быть переформулированы в терминах теории графов.
Теория графов содержит огромное количество определений, теорем и алгоритмов. И поэтому данный материал не может претендовать, и не претендует, на полноту охвата материала. Однако, по мнению автора, предлагаемые сведения являются хорошим компромиссом между объемом материала и его "коэффициентом полезного действия" в практическом программировании и решении олимпиадных задач.
Необходимо отметить, что данный материал в существенной степени опирается на наличие у ученика определенных навыков в использовании рекурсивных функций и рекуррентных соотношений, которые, в частности, могут появиться при работе над предыдущими главами этой книги.
1. Абдеев Р.Ф. Философия информационной цивилизации. - М.: Владос, 1994.
2. Адамар Ж. Исследование психологии процесса изобретения в области математики. - М.: Сов. радио, 1970.
3. Болтянский В.Г. Информатика и преподавание математики// Математика в школе. 1989. № 4.-С.86-90
4. Вейценбаум Дж. Возможности вычислительных машин и человеческий разум. - М.: Радио и связь, 1982.
5. Вирт Н. Алгоритмы+Структуры данных=Программа. - М.:Мир, 1989
6. Вирт Н. Систематическое программирование: Введение. - М.: Мир, 1977.
7. Громов Г.Р. Очерки информационной технологии. - М.: ИнфоАрт, 1993.
8. Дейкстра Э. Дисциплина программирования. - М.: Мир, 1978.
9. Ильенков Э. В. Философия и культура. - М.: Полит. лит., 1991.
10. Йодан Э. Структурное проектирование и конструирование программ. - М.: Мир, 1979.
11. Майерс Г. Надежность программного обеспечения. - М.: Мир, 1980.
12. Махмутов М.И. Организация проблемного обучения в школе. - М., 1986.