Задача № 1

Введем массив b[1]..b[n], отмечающий начало "остающейся части" массивов a[1]..a[n].

  for k:=1 to n do begin
   b[k]:=1;
 end;
 eq := true;
 for k := 2 to n do begin
  eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части  пересекаются,т.е.существует такое  х,
что для всякого i из [1..n] найдётся j из [1..m],
не меньшее b[i], для которого a[i][j] =  х;  eq  <=>  первые элементы оставшихся частей равны}
while not eq do begin
 s := 1; k := 1;
  {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
  while k <> n do begin
 k := k + 1;
 if a[k][b[k]] < a[s][b[s]] then begin
 s := k;
 end;
 end;
 {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
 b [s] := b [s] + 1;
 for k := 2 to n do begin
 eq := eq and (a[1][b[1]] = a[k][b[k]]);
 end;
 end;
 writeln (a[1],b[1]);

Задача №2

Для более удобного хранения информации заведем матрицу

C[1...n,1..n] (так называемую матрицу смежности) в которой C[i,j]=1, если в наборе есть пара (A_i,A_j) и C[i,j]=0 иначе. Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину. В качестве начального символа цепочки можно взять любой символ из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы C слева направо элемент C[i,j]=1 (другими словами, ищем пару с первым элементом Ai). Если такого элемента не существует, то берем в качестве начала строки другой элемент множества A. Если элемент C[i,j]=1 найден, то ему соответствует пара (A_i,A_j). Помечаем ее как уже использованную полагая, например, C[i,j]=-1. Далее просматриваем слева направо строку j матрицы C в поисках еще не использованной пары (A_j,A_k) (C[j,k]=1). Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку A_i A_j A_k ... A_s A_l A_p и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем эту строку как рекорд. После этого "отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с индексом, большим p. Если да, то приписываем уже этот элемент к строке и пытаемся затем снова увеличить длину полученной строки, если же нет, то "отщепляем" от строки элемент A₁, в строке S ищем единичный элемент с индексом, большим l и т.д.

Останов осуществляется тогда, когда мы должны "отщепить" от строки A_i. Перебираем цепочки, начинающиеся со всех возможных элементов множества 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.

Задача № 3

Введем массив b[1]..b[n], отмечающий начало "остающейся части" массивов a[1]..a[n].

  for k:=1 to n do begin
   b[k]:=1;
 end;
 eq := true;
 for k := 2 to n do begin
  eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части  пересекаются,т.е.существует такое  х,
что для всякого i из [1..n] найдётся j из [1..m],
не меньшее b[i], для которого a[i][j] =  х;  eq  <=>
первые элементы оставшихся частей равны}
while not eq do begin
 s := 1; k := 1;
  {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
  while k <> n do begin
 k := k + 1;
 if a[k][b[k]] < a[s][b[s]] then begin
 s := k;
 end;
 end;
 {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
 b [s] := b [s] + 1;
 for k := 2 to n do begin
 eq := eq and (a[1][b[1]] = a[k][b[k]]);
 end;
 end;
 writeln (a[1],b[1]);

Задача №4

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

    procedure Next;
     begin
        {найти i: (i<L) and ( (X[i-1]>X[i]) or (i=1) )}
        X[i]:=X[i]+1;
        { L:= i + X[i+1]+...+X[L] - 1 }
X[i+1]:=...:=X[L]:=1
end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

  program Razbieniya;
type Razb=array [byte] of byte;
var N,i,L:byte;
        X:Razb;
   procedure Next(var X:Razb;var L:byte);
     var i,j:byte;
          s:word;
   begin
     i:=L-1;s:=X[L];
     {поиск i}
     while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;
     inc(X[i]);
     L:=i+s-1;
     for j:=i+1 to L do X[j]:=1
   end;
 begin
   write('N=');readln(N);
   L:=N; for i:=1 to L do X[i]:=1;
   for i:=1 to L do write(X[i]);writeln;
   repeat
     Next(X,L);
     for i:=1 to L do write(X[i]);writeln
until L=1
end.

Задача №5

Пусть x=x₁,x₂, ... ,x_m, y=y₁,y₂, ... ,y_n.

Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной

максимальной общей подпоследовательности y x₁, ... ,x_i и y y₁, ..., y_j. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n. Пусть x_i=y_j, тогда требуется увеличить длину максимальной общей подпоследовательности x₁, ... ,x_i-1 и y₁, ... ,y_j-1 на 1: A[i,j]=A[i-1,j-1]+1, если x_i=y_j. В случае, если x_i<>y_j, то , очевидно, A[i,j]=max{A[i-1,j],A[i,j-1],A[i-1,j-1]}, но так как всегда A[i-1,j-1]<=A[i,j-1], то A[i,j]=max{A[i-1,j],A[i,j-1]}. Величина A[m,n] и дает длину максимальной общей подпоследовательности. Найдем саму подпоследовательность. Пусть A[m,n]=d. Двигаясь по последней строке справа налево ищем самый левый элемент в этой строке со значением d. Двигаемся от него вверх по столбцу в поиске элемента столбца с минимальным первым индексом и значением d. Пусть это A[i,j]. Элемент A[i-1,j-1] обязан быть равен d-1, а x_i и y_i - это последние общие совпадающие элементы в x и y. Начиная от элемента A[i-1,j-1] повторяем, как было описано выше, движение влево и вверх по матрице, находим предпоследний совпадающий элемент в x и y, и т.д.

Программа

for i:=0 to m do A[i,0]:=0;

for j:=0 to n do A[0,j]:=0; for i:=1 to m do

for j:=1 to n do

if x[i]=y[i]

then A[i,j]:=A[i-1,j-1]+1

else A[i,j]:=max(A[i-1,j],A[i,j-1]);

writeln('Длина последовательности =',A[m,n]); d:=A[m,n]; i:=m; j:=n;

while (d<>0) do begin

while A[i,j-1]=d do j:=j-1;

while A[i-1,j]=d do i:=i-1;

write('Элемент последовательности номер', d,'есть', x[i]);

i:=i-1; j:=j-1; d:=d-1;

{переход к поиску предшествующего элемента в последовательности}

end;