Задача 1.
Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2, ..., An}. Необходимо составить цепочку максимальной длины по правилу
(Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak).
При образовании этой цепочки любая пара может быть использована не более одного раза.
|
Решение задачи 1.
Для более удобного хранения информации заведем матрицу
C[1...n,1..n] (так называемую матрицу смежности) в которой C[i,j]=1, если в наборе есть пара (Ai,Aj) и C[i,j]=0 иначе.
Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину.
В качестве начального символа цепочки можно взять любой символ из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы C слева направо элемент C[i,j]=1 (другими словами, ищем пару с первым элементом Ai). Если такого элемента не существует, то берем в качестве начала строки другой элемент множества A. Если элемент C[i,j]=1 найден, то ему соответствует пара (Ai,Aj). Помечаем ее как уже использованную полагая, например, C[i,j]=-1. Далее просматриваем слева направо строку j матрицы C в поисках еще не использованной пары (Aj,Ak) (C[j,k]=1). Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку
Ai Aj Ak ... As Al Ap
и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем эту строку как рекорд. После этого "отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с индексом, большим p. Если да, то приписываем уже этот элемент к строке и пытаемся затем снова увеличить длину полученной строки, если же нет, то "отщепляем" от строки элемент A1, в строке S ищем единичный элемент с индексом, большим l и т.д.
Останов осуществляется тогда, когда мы должны "отщепить" от строки Ai.
Перебираем цепочки, начинающиеся со всех возможных элементов множества A. Находим строку максимальной длины:
const M=10; {максимально число элементов в A}
{будем считать, что A состоит из чисел от 1 до N} var c:array[1..M,1..M] of integer;
curstr, maxstr: array[0..M] of integer;
{в этих переменных хранятся текущая цепочка и}
{цепочка максимальной длины.}
{В нулевом элементе хранится длина цепочки}
N,E : integer; {N - число элементов в A}
i,j,k : integer; {E - число пар в наборе}
procedure find;
var l,j : integer;
begin
l:=curstr[curstr[0]]; {l = последний элемент цепочки}
for j:=1 to N do {просмотр строки l}
if C[l,j]=1
then begin
curstr[0]:=curstr[0]+1;
curstr[curstr[0]]:=j; {j -> в цепочку}
c[l,j]:=-1; {пара использована}
find;
c[l,j]:=1; {пару снова разрешено использовать}
curstr[0]:=curstr[0]-1;
end;
if curstr[0]>maxstr[0] {если нашли более}
then maxstr:=curstr {длинную строку}
end;
begin
readln(N); readln(E);
for i:=1 to N do
for j:=1 to N do
C[i,j]:=0;
for k:=1 to E do begin
write('очередная пара: ',i,j);
c[i,j]:=1
end;
for i:=1 to N do begin
curr[0]:=1; {поиск цепочки}
curr[1]:=i; {начинающейся элементом i}
find;
end;
for i:=1 to maxstr[0] do
write(maxstr[i]); {печать максимальной строки} end.
|
