Пусть мы обработали все N элементов массива A и нашли максимальный элемент массива B. Пусть это элемент с индексом IndexMax. По построению это длина максимальной подпоследовательности.
Получить искомую подпоследовательность можно следующим образом. Пусть j – индекс текущего элемента подпоследовательности, распечатываемой с конца. Сначала полагаем j: = IndexMax и печатаем элемент A[j], который является последним. Предшествующий ему в последовательности элемент имеет индекс C[j], поэтому индекс следующего с конца элемента определяется следующим образом j: = C[j]. Распечатываем этот элемент. Описанные действия повторяем до тех пор, пока j не станет равным 0 (т. е. мы дошли до начала последовательности).
Запись алгоритма на языке Pascal:
for i: = 2 to N do B[i]: = 0;
C[1]: = 0; B[1]: = 1; Max: = 1; IndexMax: = 1;
for i: = 2 to N do
for k: = 1 to i – 1 do
if (A[k]<A[i]) and (B[i]<B[k] + 1) then
begin
C[i]: = k;
B[i]: = B[k] + 1;
if B[i]>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). Для хранения подпоследовательности для каждого элемента удобно хранить номер предшествующего ему элемента.
б) Для каждого индекса 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].
14. Для решения задачи элементы массива удобно упорядочить по абсолютной величине (в порядке неубывания). Если в массиве есть элементы, равные 0, то один из них и будет последним элементом искомой последовательности, поэтому их можно игнорировать. Пусть К 4i 0 обозначает максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством, последним элементом которой является i-й элемент.
Понятно, что наименьшему по абсолютной величине элементу ничего не может предшествовать ни один элемент, поэтому Kр = 0, где р - индекс первого ненулевого элемента.
Для каждого следующего элемента с номером j, j = р + 1, ..., N, необходимо определить максимальное количество элементов, которое может предшествовать рассматриваемому элементу, с учетом требуемого свойства. Понятно, что это количество есть максимум из величин Кр1, Кр2, ..., Крm, где элементы с номерами p1, p2, ..., pm, p £ p1 < p2 < ... < pm < j являются делителями элемента с номером j. Поэтому мы имеем рекуррентную формулу для вычисления Kj:
Kj = max (Kp1, Kp2, ..., Kpm).
Значение KN, вычисленное по описанному выше правилу, и определяет максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством (без учета возможного нуля в конце последовательности).
Для того, чтобы установить, какие элементы образуют максимальную последовательность, достаточно для каждого номера j помнить тот номер из p1, p2, ..., pm, на котором достигается максимум для чисел Kp1, Kp2, ..., Kpm. Эти номера можно определять параллельно с вычислением значения K(j) в некотором массиве, например ПРЕДОК. Используя эту информацию, легко определить номера элементов последовательности, проходя от элемента i с максимальным значением Ki к элементу, который ему предшествует (ПРЕДОК(i)), до тех пор, пока не придем к первому элементу f последовательности (ПРЕДОК(f) = 0).
15. Очевидно, что параллелепипеды можно повернуть так, чтобы размеры ребер параллелепипеда шли в неубывающем порядке. Зафиксируем этот порядок. Вложение параллелепипеда B в C возможно только тогда, когда для двух параллелепипедов B(b(1), ..., b(n)) и C(c(1), ..., c(n)) выполняются неравенства b(k) £ c(k), k = 1, ..., n.
16. Метод решения этой задачи аналогичен использованному при решении задачи о нахождении максимальной по длине возрастающей подпоследовательности.
Пусть a, b, c – натуральные числа.
Будем рассматривать только случай a>c, так как в случае a<b задача неразрешима, а в случае b£ a£ c сразу получаем, что k = 1 и x[1] = a.
Обозначим через L множество делителей числа a, лежащих на отрезке [b, c]. Количество всех делителей числа a имеет порядок log2a (если a = f * g, то f£ log2a, g> = a, всего разных f может быть не более a, столько же и разных g). Пусть L1 – минимальный элемент из L, a L2 – максимальный. Пусть в массиве S[1..p] первый элемент равен единице, а все остальные – делители числа a, не меньшие b, записанные в порядке возрастания. Из утверждения выше следует, что p£ a + 2.
Будем искать минимальную по длине подпоследовательность элементов массива S, которая начинается единицей, заканчивается a, каждый элемент которой делится на предыдущий, причем частное принадлежит множеству L.
В случае, если a, b, c, x[i] – целые, в массив S помещаем в порядке возрастания модуля все делители числа a, начиная с минимального элемента в L. Далее – аналогично.
17. Задачу можно переформулировать следующим образом:
Последовательность из n вагонов, занумерованных от 1 до n, необходимо разбить на не более чем m подпоследовательностей, в каждой из которых номера вагонов возрастают.
Одним из самых простых алгоритмов сортировки вагонов является алгоритм, основывающейся на следующем правиле:
Помещаем очередной вагон (номер которого k) на путь с минимально возможным номером, при условии что последний вагон, стоящий на этом пути, имеет номер, меньший k.
Если все вагоны состава будут таким образом расположены на станции, то, очевидно, что вагон №1 на каком то пути будет самым правым и его можно подать на выход. Затем вагон №2 также может быть подан на выход, т. к. не может стоять на пути за вагоном, с номером большим 2, и т. д.
Если же какой-то вагон нельзя поместить ни на один путь на станции, то это значит, что все пути "перекрыты" вагонами с большими номерами, причем последние вагоны на этих путях расположены в порядке убывания. Вместе с последним вагоном, не нашедшим себе места, эти m вагонов в исходной последовательности составляют убывающую подпоследовательность длины m + 1.
Отметим, что если можно отсортировать последовательность вагонов, то можно отсортировать также и любую их подпоследовательность, и наоборот. Поэтому из существования убывающей подпоследовательности длины m + 1 следует, что исходную последовательность отсортировать нельзя.
18. Можно, конечно, число A умножить само на себя n – 1 раз, но для этого надо выполнить n – 1 операцию умножения. Рассмотрим метод, требующий меньшего числа умножений (он, однако, не всегда дает минимальное число умножений).
Если n – четное, n = 2m то будем вычислять An, используя тождество
An = (Am)2
если же n = 2m + 1, то An = (Am)2 * A.
Таким образом, возведение A в 13 степень будет выглядеть следующим образом (символ ^ означает возведение в степень):
A^13 = (A^6)^2 * A = ((A^3)^2)^2 * A = ((A * A * A)^2)^2 * A
и вычисление требует 5 операций умножения.
Используя данный метод, для возведения числа в степень n потребуется порядка log2n операций умножения.
Программа на Паскале может выглядеть так:
var A, N: integer;
function power(N: integer): integer;
begin
if N>1 then
if odd(N) then { N нечетно? }
power: = SQR(power(N div 2)) * A
else power: = SQR(power(N div 2))
else power: = A
end;
begin
read(A, N);
writeln(power(N));
end;
Можно ту же самую идею реализовать и по другому (далее мы приводим выдержку из книги Д. Кнута "Искусство программирования для ЭВМ", т. 2, с. 482):
"Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру "1" парой букв SX, а каждую цифру "0" – буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева направо, превращается в правило вычисления x^n, если букву "S" интерпретировать как операцию возведения в квадрат, а букву "X" – как операцию умножения на x. Например, если n = 23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило вычисления: S SX SX SX. Согласно этому правилу, мы должны "возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x"; при этом мы последовательно вычисляем x2, x4, x5, x10, x11, x22, x23.
Этот "бинарный метод" легко обосновать, рассмотрев последовательность получаемых в ходе вычисления показателей: если "S" интерпретировать как операцию умножения на 2, а "X" – как операцию прибавления 1 и если начать с 1, а не с x, то наше правило дает нам в соответствии со свойствами двоичной системы счисления число n".
Приведенный метод не дает минимального числа операций умножения. Для вычисления x23 нам, по изложенному выше методу, потребуется 7 операций умножения. В действительности их необходимо только 6:
x ® x2 ® x3 ® x5 ® x10 ® x20® x23.
Алгоритм нахождения минимального числа операций (кроме полного перебора) сейчас неизвестен (см. там же, у Д. Кнута).
19. Пусть z есть массив из N элементов, y – из M. Положим i = 1 и j = 1. Берем элемент z[i] и ищем минимальное k, k> = j, k£ M, такое что y[k] = z[i] (мы находим очередной совпадающий символ в строках z и y). Полагаем i = i + 1 и j = k + 1. Повторяем поиск элемента z[i] в оставшемся куске последовательности y. Условия окончания поиска:
а) Если i стало больше N (т. е. все элементы массива z являются подпоследовательностью элементов y), – и тогда z можно получить вычеркиванием элементов из y.
б) Если в оставшимся куске последовательности y не найдено элемента, совпадающего с очередным z[i], то z из y получить нельзя.
20. Пусть x = (x1, x2, ..., xm), y = (y1, y2, ..., yn).
Заведем матрицу A[0..m, 0..n]. Элемент A[i, j] будет длиной максимальной общей подпоследовательности (x1, ..., xi) и (y1, ..., yj). Сначала A[i, 0] = A[0, j] = 0, i = 0, ..., m, j = 0, ..., n.
Пусть xi = yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1, ..., xi – 1 и y1, ..., yj – 1 на 1:
A[i, j] = A[i – 1, j – 1] + 1, если xi = yj.
В случае, если x i¹ yj, то, очевидно, 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, а xi и yi – это последние общие совпадающие элементы в x и y.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
