При образовании этой цепочки любая пара может быть использована не более одного раза

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

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;beginl:=curstr[curstr[0]]; {l = последний элемент цепочки}for j:=1 to N do {просмотр строки l}if C[l,j]=1then begincurstr[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;beginreadln(N); readln(E);for i:=1 to N dofor j:=1 to N doC[i,j]:=0;for k:=1 to E do beginwrite('очередная пара: ',i,j);c[i,j]:=1end;for i:=1 to N do begincurr[0]:=1; {поиск цепочки}curr[1]:=i; {начинающейся элементом i}find;end;for i:=1 to maxstr[0] dowrite(maxstr[i]); {печать максимальной строки} end.

Задача № 8

Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются.Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результаты задавать таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить.

Легко понять, что сеть дорог будет реализовывать некоторый связный (так как можно проехать из любого города в любой) граф без циклов (так как одно ребро из цикла можно выбросить, а связный граф останется связным). Поэтому алгоритм построения сети дорог минимальной суммарной стоимости очень прост. На каждой итерации необходимо находить дорогу минимальной стоимости, которая не образует цикла с уже выбранными дорогами на предыдущих итерациях. Основную трудность такого решения составляет проверка условия, образуют ли ребра цикл. Однако решение существенно упрощается, если рассматривать только минимальные ребра только между двумя множествами: множеством помеченных вершин и множеством непомеченных вершин. Понятно, что эти множества должно соединять хотя бы одно ребро, чтобы граф был связным. Ясно, что оно должно быть минимальным по длине. В описываемом ниже алгоритме это делается следующим образом. Для каждой вершины к из множества непомеченных вершин (а на начальном этапе это все вершины, кроме первой) определяется ближайшая вершина из множества помеченных вершин БЛИЖ[к]. На каждой итерации определяется кратчайшее ребро (i,j) между множеством помеченных вершин и множеством непомеченных вершин, используя массив БЛИЖ. Найденное ребро выбирается для системы дорог, а соответствующая вершина j считается помеченной. После этого пересчитывается массив БЛИЖ. При этом учитывается, что к изменение некоторой величины БЛИЖ[k] может произойти только тогда, когда расстояние от k до j меньше, чем от k до БЛИЖ[k].

Алгоритм

для i от 1 до N выполнятьнцфлаг[i]:=0;БЛИЖ[i]:=1кцфлаг[1]:=1;для k от 1 до N-1 выполнятьнцминрас:=бесконечность;для i от 2 до N выполнятьесли флаг[i]=0 и минрас > C[БЛИЖ[i],i]то минрас:=C[БЛИЖ[i],i];j:=i;всеВывод ребра (БЛИЖ[j],j)флаг[j]:=1;для i от 2 до N выполнятьесли флаг[i]=0 и C[БЛИЖ[i],i]>C[i,j]то БЛИЖ[i]:=j;всекц

Задача № 9

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.

Введем массив 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]]);

Задача №10

На пpямой своими концами заданы N отpезков и точка X. Опpеделить, пpинадлежит ли точка межотpезочному интеpвалу. Если да, то указать концевые точки этого интервала. Если нет, то найти,