Последовательности и их подпоследовательности

В семидесятые годы возникла задача, авторство которой установить
уже не представляется возможным. Она формулируется так:
Из последовательности A, состоящей из n чисел, вычеркнуть мини-
мальное количество элементов так, чтобы оставшиеся образовали строго
возрастающую последовательность (или. что то же, найти максимальную по
длине строго возрастающую подпоследовательность последовательности A).
Впоследствие эта задача в различных формулировках не раз предла-
галась на олимпиадах различного уровня. Мы рассмотрим решение этой за-
дачи и несколько ее нестандартных модификаций.
Задачи, подобные приведенным ниже, имеют многочисленные приложе-
ния в разных областях (организация структур данных, проектирование пе-
чатных схем и т.п.).

Рассмотрим сначала наиболее очевидный, но, как это обычно бывает,
наименее эффективный (медленный) алгоритм. Мы будем генерировать все
подпоследовательности данной n-элементной последовательности и для
каждой из подпоследовательностей проверять, является ли она строго
возрастающей и максимальной по длине.
Для генерации подпоследовательностей заведем массив B[1..n+1] из
(n+1) элемента (n+1-ый элемент фиктивный и используется для определе-
ния окончания работы). B[i]=0, если i-ый элемент в подпоследова-
тельность не входит, и B[i]=1 иначе. Таким образом, пустой подпоследо-
вательности будет соответствовать набор из n нулей, а n-элементной
подпоследовательности — набор из n единиц. Тут явно заметна связь под-
последовательности с двоичным представлением числа.
Алгоритм: будем генерировать числа от 0 до 2n-1, находить их
двоичное представление и формировать подпоследовательность из элемен-
тов массива А с индексами, соответствующими единичным битам в этом
представлении.
Но при таком подходе возникает следующая трудность: число 2n-1
может не поместиться в разрядную сетку машины. Поэтому генерацию бу-
дем проводить, используя массив B. Вначале определим B[i]=0 для всех i
от 1 до n+1, что соответствует пустой подпоследовательности. Будем
рассматривать массив B как запись двоичного числа B[n+1]…B[1], и мо-
делировать операцию сложения этого числа с единицей. При сложении бу-
дем просматривать число справа налево, заменяя единичные биты нулями
до тех пор, пока не найдем нулевой бит, в который занесем 1. Генера-
ция подпоследовательностей заканчивается, как только B[n+1]=1 (преды-
дущая конфигурация была 1…12 = 2n-1).
Приведем фрагмент программы генерации всех подпоследовательностей:

while B[n+1]=0 do begin
i:=1; { индекс бита двоичного числа }
while (B[i]=1) do begin
B[i]:=0; { моделируем перенос в следующий разряд, }
i:=i+1 { возникающий при сложении }
end;
B[i]:=1;
{ Распечатываем индексы единичных элементов массива B —
новая сгенерированная подпоследовательность }
For i:=1 to n do
if B[i]=1 then write(i:3);
writeln; { переход на новую строку при печати }
end;

Всего существует 2n таких подпоследовательностей, поэтому даже
при небольших n результата придется ждать очень долго.

Предположим, что при генерации подпоследовательностей мы нашли
k-элементную строго возрастающую подпоследовательность. В дальнейшем
имеет смысл рассматривать только подпоследовательности, состоящие из
более чем k элементов (подумайте, почему?).
Рассмотрим исходную n-элементную последовательность. Если она не
является искомой, то будем генерировать (n-1)-элементные подпоследова-
тельности. Если и среди них не найдено решение, то будем рассматри-
вать подпоследовательности из (n-2)-х элементов, и т.д.
Воспользуемся следующим алгоритмом генерации k-элементных подпос-
ледовательностей.
В массиве B будем хранить в порядке возрастания индексы ис-
пользуемых на данном шаге элементов из A (общее их число k). В качес-
тве начальной конфигурацией возьмем следующую: B[j]=j, j=1,…,k. Для
генерации очередной конфигурации найдем B[j] с максимальным индексом j
так, что выполняется неравенство B[j]j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и
мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы
при заполнении возрастающими значениями элементов массива B[m], m>j,
последний элемент B[k] не превосходил бы n). Если такого B[j] не су-
ществует, то генерация подпоследомательностей длины k закончена.
В худшем случае (каком?) придется анализировать порядка 2n ва-
риантов.
Для более быстрого решения этой задачи можно применить дихотомию
по k — количеству элементов в подпоследовательности (как?).
Рассмотрим другое, более эффективное решение этой задачи. Заве-
дем массивы A, B и C длины n: массив A[1..n] используется для хране-
ния чисел исходной последовательности. Элемент B[i] — значение длины
максимальной возрастающей подпоследовательности, последний элемент ко-
торой A[i]. Величина C[i] есть индекс элемента, предшествующего эле-
менту A[i] в этой максимальной подпоследовательности (A[i]=0 если
предшествующего элемента нет).
Если n=1, то A[1] и есть искомая подпоследовательность. При этом
B[1]=1, C[1]=0. Предположим, что мы заполнили массивы B и C от начала
и до элемента i-1. Попытаемся получить элементы B[i] и C[i]. Для это-
го будем просматривать массив A от 1 до i-1-го элемента и искать та-
кой индекс k, для которого одновременно выполняются следующие условия:
1) A[k]Max
then begin Max:=B[i]
IndexMax:=i
end;
end;
j:=IndexMax;
while j<>0 do begin
writeln(A[j]);
j:=C[j]
end;

В программе переменная Max используется для хранения длины теку-
щей максимальной подпоследовательности.
В этой задаче элемент массива C[i] содержит ссылку на элемент,
предшествующий A[i] в подпоследовательности максимальной длины. Такая
ссылочная структура данных называется однонаправленным списком. Если у
элемента есть ссылка как на предыдущий, так и на последующий за ним
элемент, то список — двунаправленный (его можно реализовать, если ис-
пользовать не один массив ссылок, а два).
Метод решения задачи, когда для поиска очередного оптимального
значения используются оптимальные значения, полученные на предшествую-
щих шагах, называется методом динамического программирования. В разоб-
ранной выше задаче оптимальные значения хранятся в массиве B.
Получить более эффективное решение можно, если на каждом шаге
хранить не все полученные ранее оптимальные значения и соответствую-
щие подпоследовательности, а только наиболее перспективные из них.
Пусть К(L,i) обозначает множество возрастающих подпоследова-
тельностей длины L, которые составлены из элементов с номерами от 1 до
i-1. Из двух подпоследовательностей длины L более перспективной будет
та, у которой величина последнего элемента меньше, так как ее может
продолжить большее число элементов. Пусть SP(L,i) — это самая перспек-
тивная подпоследовательность длины L (с минимальным по величине пос-
ледним элементом), а S(i) — множество всех подпоследовательностей
SP(L,i) при всевозможных L. В S(i) содержится не более i-1 подпоследо-
вательностей (с длинами 1,…,i-1).
Пусть мы знаем S(i). Для того, чтобы определить, какие подпосле-
довательности может продолжать i-й элемент последовательности A, дос-
таточно знать последние элементы перспективных подпоследовательностей
длины 1,2,…, n, индексы которых будут храниться в массиве Ind.
Последний элемент перспективной подпоследовательности длины p
строго меньше последнего элемента перспективной подпоследовательности
длины p+1 (объясните почему?). Поэтому i-ый элемент должен продол-
жить подпоследовательность максимальной длины, последний элемент кото-
рой меньше i-го элемента. Учитывая упорядоченность последних элемен-
тов перспективных подпоследовательностей, поиск можно сделать методом
половинного деления (дихотомией), используя массив Ind. При присоеди-
нении i-го элемента к такой подпоследовательности длины p ее длина
увеличивается на 1, a последним элементом становится A[i]. При этом
множество S(i+1) совпадает с S(i) за исключением подпоследовательнос-
ти SP(p+1,i+1), полученной добавлением i-го элемента к подпоследова-
тельности SP(p,i). Для хранения подпоследовательности для каждого эле-
мента удобно хранить номер предшествующего ему элемента.
Рассмотрим несколько задач подобного типа, решение которых опи-
рается на изложенные выше методы.
Задача 1.
а) Из заданной числовой последовательности A[1..n] вычеркнуть ми-
нимальное число элементов так, чтобы в оставшейся подпоследовательнос-
ти каждый последующий элемент был больше предыдущего кроме, быть мо-
жет, одной пары соседних элементов (одного «разрыва» возрастающей под-
последовательности).
Например: A=(1,2,3,2,4,3,4,6);
Искомая подпоследовательность (1,2,3,2,3,4,6)
Разрыв подчеркнут.
б) Из заданной числовой последовательности A[1..n] вычеркнуть ми-
нимальное число элементов так, чтобы в оставшейся подпоследовательнос-
ти каждый последующий элемент был больше предыдущего за исключением не
более m пар соседних элементов (возрастающая подпоследовательность с m
«разрывами»).

Решение задачи 1.
а) Для каждого индекса i найдем подпоследовательность макси-
мальной длины с разрывом в A[i]. Будем искать максимальную по длине
подпоследовательность, заканчивающуюся в элементе A[i], и макси-
мальную по длине подпоследовательность, начинающуюся в нем (для этого
будем просматривать массив A не слева направо, а справа налево).
б) Заведем массив С[0..m+1,1..n]. В нем i-тая строка будет хра-
нить информацию о последовательностях с i-1 разрывом (нулевая строка —
фиктивная); j-ый элемент в этой строке есть длина самой длинной под-
последовательности элементов «хвоста» массива А (от j-го элемента до
n-го), начинающейся в j-ой позиции и имеющей не более i-1 разрывов.
Правило заполнения массива:
Заполним нулевую строку нулями (чтобы можно было заполнить пер-
вую строку по общему алгоритму).
Для каждой строки i от 1 до m+1 выполнять следующие действия:
Для j-го элемента массива A (j изменяется от n до 1) найти макси-
мальную по длине подпоследовательность, которую можно присоединить к
этому элементу так, чтобы получить подпоследовательность максимальной
длины с не более чем i-1 разрывом. Для этого:
1) найти элемент A[k] последовательности A, больший A[j], стоя-
щий в массиве A правее j-го элемента и с максимальным С[i,k];
2) просмотреть элементы i-1-ой строки матрицы С, начиная с
j+1-го и до конца; найти максимальный из них, пусть это
C[i-1,s];
3) сравнить C[i-1,s] с С[i,k]. Больший из них (обозначим его
C[row,col]), увеличенный на 1, запомнить в C[i,j]. Это и бу-
дет длина максимальной подпоследовательности, начинающейся в
позиции j, с не более чем i-1 разрывом.
4) Запомнить индексы row и col элемента массива C, предшесвую-
щего C[i,j], как элементы X[i,j] и Y[i,j] соответственно.

После окончания цикла максимальный элемент m+1-ой строки матрицы
C и есть максимальная длина возрастающей подпоследовательности с m
разрывами. Выписать всю подпоследовательность в обратном порядке мож-
но следующим образом: для каждого элемента подпоследовательности в
массивах X и Y хранится информация о предшественнике. Мы, начиная с
максимального элемента m+1-ой строки матрицы C, восстанавливаем всю
подпоследовательность.
Обоснование алгоритма:
Пусть мы знаем C[i-1,j] для всех j от 1 до n и для некоторого i,
а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].
Для j-го элемента массива А существует максимальная по длине под-
последовательность с не более чем i-1 разрывом, начинающаяся с A[j].
Второй элемент (обозначим его A[k]) этой максимальной подпоследова-
тельности (если он, конечно, есть) может быть
1) больше A[j]. Тогда мы находим его среди элементов, обладающих
следующими свойствами:
а) k>j,
б) C[i,k] максимальный (т.е. мы присоединяем к A[j] макси-
мальную по длине подпоследовательность с не более чем i-1
разрывом, формируя подпоследовательность опять не более чем
с i-1 разрывом);
2) меньше или равный A[j]. Тогда мы ищем его среди элементов, об-
ладающих следующими свойствами:
а) k>j;
б) C[i-1,k] максимальный (т.е. мы присоединяем максимальную
подпоследовательность с не более чем i-2 разрывами, форми-
руя подпоследовательность с не более чем i-1 разрывом).
Полученная подпоследовательность имеет максимальную длину, так
как длина подпоследовательности, которая начинается с A[k] — макси-
мальна. Упоминавшиеся выше индексы row и col, которые запоминаются в
X[i,j] и Y[i,j] соответственно, обозначают следующее: col — индекс
следующего за A[j] элемента в максимальной по длине подпоследова-
тельности, начинающейся в позиции j и имеющей не более i-1 разрывов;
row-1 — максимальное количество разрывов в подпоследовательности, на-
чинающейся в A[col].

Решение предлагаемых ниже задач основывается на изложенных ранее
принципах.

Задача 2.
В заданной последовательности целых чисел найти максимально длин-
ную подпоследовательность чисел такую, что каждый последующий элемент
подпоследовательности делился нацело на предыдущий.

Задача 3.
Задаются число n>1 — размерность пространства и pазмеpы М
n-мерных параллелепипедов (ai1, …, ain), i=1,…,m.
Паpаллелепипед может располагаться в пространстве любым из спосо-
бов, при которых его ребра параллельны осям координат. Найти макси-
мальную последовательность вкладываемых друг в друге паpаллелепипедов.

Указание к решению задачи 3.
Очевидно, что параллелепипеды можно повернуть так, чтобы размеры
ребер параллелепипеда шли в неубывающем порядке. Зафиксируем этот по-
рядок. Вложение параллелепипеда B в C возможно только тогда, когда для
двух параллелепипедов B(b(1), …, b(n)) и C(c(1),…, c(n)) выпол-
няются неравенства b(k)єc(k), k=1,…,n.

Задача 4.
Ввести три числа а,b,с.
Можно ли представить число а таким образом, чтобы
k
а = х[1]*x[2]*…*x[k] = П x[i],
i=1
где bєx[i]єc, х[i], а, в, с — целые. Лучшим считается алгоритм находя-
щий такое представление с наименьшим числом множителей. Предусмотреть
вариант, когда такого представления не существует.

Решение задачи 4.
Метод решения этой задачи аналогичен использованному при решении
задачи о нахождении максимальной по длине возрастающей подпоследова-
тельности.
Пусть a, b, c — натуральные числа.
Будем рассматривать только случай a>c, так как в случае a

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

методические материалы по информатике