Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Рекурсия >> Номер 26

[Назад]    [Содержание ]    [Вперед]

  


Номер 26


  Условие: Номер 26


Задача 25. Пусть x и y - две бинарных последовательности (т.е. элементы последовательностей - нули и единицы); x и y можно рассматривать как запись в двоичной форме некоторых двух натуральных чисел. Найти максимальное число z, двоичную запись которого можно получить вычеркиванием цифр как из x, так и из y. Ответ выдать в виде бинарной последовательности.

  Решение задачи: Номер 26


Решение задачи 25. В последовательностях 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 do for j:=0 to n do S[i,j]:=''; for i:=1 to m do for j:=1 to n do begin if x[i]=y[j] then begin A[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].

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017