3.4 Результаты тестирования
Сначала пользователь вводит количество элементов дерева, затем отрезок, на котором необходимо удалить элементы. Результат данных действий показан на рисунке 6.
Рисунок 6 – Результат удаления элементов АВЛ дерева
4 Задача 4.21
4.1 Постановка задачи и ее анализ
Задание: Нахождение наибольшей общей подпоследовательности. Использовать алгоритм из книги Кормена, стр 318.
Данный алгоритм основан на двумерном динамическом программировании. Заключается он в следующем:
Пусть даны две последовательности. Для нахождения НОП необходимо:
Последовательность 1 записать перед строками матрицы, а последовательность 2 над столбцами матрицы. 2) Матрица будет иметь нулевыми первый столбец и первую строку. 3) Саму матрицу назовем a. 4) В элементе матрицы a[i,j] будет хранится длина наибольшей общей подпоследовательности для последовательностей x[1..i] и y[1..j].
Элемент матрицы a[i,j] будем находить по рекуррентной формуле:
3.2 Описание структур данных
В данной программе необходимо реализовать двумерный массив, который будет содержать количество совпавших элементов
var x,y,z:string;//x и y –последовательности, z – будет содержать НОП
a:array[0..100,0..100] of byte;//т. к в задании не указан максимальный размер последовательностей, то будем считать что последовательности не превышают 100 элементов
i,j:byte;//значение строки и столбца
4.3 Проектирование программы
Реализуем данную задачу следующим образом: пользователь вводит две последовательности с клавиатуры (тип каждой - строка). Затем входные данные передаются в процедуру lcs, в которой мы заполняем таблицу по рекуррентной формуле приведенной выше и также «собираем» НОП обратным заполнению способом.
Листинг процедуры lcs:
procedure lcs(a:array[0..100,0..100] of byte; x,y: string);
begin
for j:=1 to length(x)+1 do //зануляем первую строку и столбец нулями
begin
a[1,j]:=0;
end;
for i1:=2 to length(y) do
begin
a[i1,1]:=0;
end;
for i:=2 to (length(x)+1) do
for j:=1 to (length(y)+1) do
begin
if (x[i]=y[j]) then
a[i,j]:=a[i-1,j-1]+1
else
if (a[i-1,j]>=a[i,j-1]) then
a[i,j]:=a[i-1,j]
else
a[i,j]:=a[i,j-1];//длина ноп находится в последнем элементе
end;
z:='';//получаем ноп
i:=length(x);
j:=length(y);
while (i>0) and (j>0) do
if x[i]=y[j] then
begin
z:=x[i]+z; i:=i-1; j:=j-1
end
else
if a[i-1,j]>=a[i,j-1] then
i:=i-1
else j:=j-1;
writeln('НОП----> ');
write(z);
end;
4.4 Результаты тестирования
Результат тестирования – Рисунок 7.
Рисунок
7 – Нахождение НОП двух последовательностей
Список использованных источников
Т. Кормен, Ч. Лейзер - Алгоритмы. Построение и анализ. - 318 с.
Окулов С. М. Программирование в алгоритмах, 2004