В последовательностях x и y избавляемся от лидирующих нулей. Если хоть одна из последовательностей стала пустой, то z=0. Иначе крайние левые цифры и в x и в y есть 1.
Запускаем на полученных последовательностях алгоритм задачи 24 (для получения максимального z необходимо, чтобы старшая цифра z была 1 и двоичная запись z имела максимальную длину), но при этом для каждого A[i,j] - длины последовательности, необходимо хранить добавочно и саму последовательность; при присвоении значения A[i,j] одновременно будем запоминать и последовательность максимальной длины. Если таких несколько, то берем из них последовательность с максимальным значением. Поэтому алгоритм задачи 23 запишется так:
Пусть S[0..m,0..n] - массив строк. В S[i,j] будет храниться подпоследовательность, длина которой A[i,j].
for i:=0 to m do A[i,0]:=0;for j:=0 to n do A[j,0]:=0;for i:=0 to m dofor j:=0 to n do S[i,j]:='';for i:=1 to m dofor j:=1 to n do beginif x[i]=y[j]then beginA[i,j]:=A[i-1,j-1]+1; S[i,j]:=S[i-1,j-1]+x[i];end;A[i,j]:=max(A[i,j],A[i-1,j],A[i,j-1]); S[i,j]:=max(S[i,j],S[i-1,j],S[i,j-1]);end;write(A[m,n],'- длина',S[m,n]);
Попробуйте не заводить массив S[0..m,0..n], а обойтись одномерным массивом S[0..n].
|
|
Задача №18
Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.
Определить
a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;