если даны два списка чисел и нужно найти наибольшую одинаковую последовательность чисел, например, если дано:
1 2 3 4 5 6
1 2 6 2 3 4
то должен вывести 234
подскажите пожалуйста, каким алгоритмом тут лучше воспользоваться?
попробовала написать программу для 2х массивов, которая выдаст длину наибольшей общей последовательности, но что-то не совсем получилось
.
var
a: array [1..10] of integer;
a1: array [1..10] of integer;
k,i,j,i1,j1,kmax: integer;
begin
for i:=1 to 10 do
read(a[i]);
for j:=1 to 10 do
read(a1[j]);
i:=1;
while i<= 10 do begin
for j:= 1 to 10 do begin
if a[i]=a1[j] then begin
i1:=i;
j1:=j;
while a[i1]=a1[j1] do begin
k:=k+1;
i1:=i1+1;
j1:=j1+1;
end;
if k>kmax then kmax:=k;
k:=0;
end;
end;
i:=i+1;
end;
writeln(kmax);
end.
Это задача о Наибольшей Общей Подпоследовательности. Динамическое программирование.
Как решать - можно посмотреть здесь: http://club.shelek.ru/viewart.php?id=131
> не подскажете где ошибка?
Ну, например, что происходит, когда i1 и j1 становятся больше 10? Впрочем,
> это вообще неудачная идея так решать данную задачу
Хоть такое решение первым приходит в голову, но в лоб решать задачу не стоит.
Надо делать, как по ссылке. Вот только там нет опечатки?
Вот в этом месте:
в другой книге написано в одной строчке по-другому немного:
else if c[i-1,j] >= c[i,j-1] then ...
> в другой книге написано в одной строчке по-другому немного:
А вот если там >= вместо =, то это уже ближе к истине.
Правда, время за O(m*n) всё равно странно. Там вроде можно за O(m+n). Или я это путаю с поиском подстроки...
> а если ввести ограничения, то все равно что-то не то
Ну ввёл.
while (i1<=10) and (j1<=10) and (a[i1]=a1[j1]) do begin
У меня всё работает. Надо граничные условия проверять до сравнения элементов. Чтобы в случае выхода за границы элементы не сравнивались. А вообще, этот алгоритм недостоин того, чтобы его отлаживать.
Добавлено через 11 мин.
Хотя не, то, что по ссылке, тоже неверно. Для abc и bac возвращает 2.
А потому, что если длина НОП для ab и ba равна 1 и следующий добавленный элемент и там и там c, то вовсе не значит, что длина НОП для abc и bac равна 2. С чего этому НОПу быть именно в конце у обоих?
все, в своем не совсем удачном алгоритме нашла еще ошибку, теперь и у меня работает! спасибо за помощь!
алгоритмы, которые я смотрела, считают, что, если заданы строки:
123 и 1523, то наибольшая общая подпоследовательность будет 123 (наверное, это из определения подпоследовательности),
а мне нужно было решить задачу, чтобы выводилось 23.
Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?(если дано: 123 и 1523, то выдает 123)
> Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?
Выходит, что так.
Всё, теперь я тоже врубился, почему такой результат. Ну да, тут-то надо подпоследовательность подряд идущих элементов, а тот алгоритм ищет и раскиданную подпоследовательность.
Но тут тоже надо подумать над оптимизацией. Пока что есть O(m*n*min(m,n)), короче кубическая сложность.
А, в википедии же есть аналогичный алгоритм, но как раз для подстрок, а не подпоследовательностей, ровно то, что тут надо: http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока
http://e-maxx.ru/algo/suffix_automata
Тут уже за o(m+n)
Я проверил, слово в слово переписал сишный алгоритм на паскаль, вроде работает.
Впрочем, вряд ли вам задавали суффиксные автоматы, это уже дебри пошли.
Спасибочки большое!!!)))
ну да, это уже все сложно, но ради интереса попробую разобраться)))
const
n=10;
var
a,b: array [1..n] of integer;
i,j,k,kmax: integer;
begin
for i:=1 to n do read(a[i]);
for j:=1 to n do read(b[j]);
kmax:=0;
for i:=1 to n do
for j:= 1 to n do begin
k:=0;
while a[i+k]=b[j+k] do Inc(k);
if k>kmax then kmax:=k
end;
writeln(kmax)
end.
while a[i+k]=b[j+k] do Inc(k);.
что-то совсем у меня со списками ничего не получается, пыталась изменить ваш алгоритм под свою задачу, но не выходит пока(
type
TWordStr = integer;
PTItem = ^TItem;
TItem = record
Data: TWordStr;
next: PTItem;
end;
TWordList = record
first, last, head: PTItem;
end;
var
kmax,k: integer;
L,L1: TWordList;
p, p1: PTItem;
...
begin
...
p:=L.first;
p1:=L1.first;
while p<>nil do begin
while p1<>nil do begin
k:=0;
while (p<> nil) and (p1<>nil) and (p^.Data = p1^.Data) do
begin
k:=k+1;
p:=p^.next;
p1:=p1^.next;
end;
if k>kmax then kmax:=k;
end;
end;
p:=p^.next; //до этого значение уже было изменено, и теперь тут не то, что нужно
p1:=p1^.next; //а как исправить?
end;
writeln(kmax);
end.
p := L.first;
while p <> nil do
begin
p1 := L1.first; { <--- Это по поводу начала внутреннего цикла }
while p1 <> nil do
begin
k := 0;
pp := p; pp1 := p1; { А это - доп. переменные }
while (pp <> nil) and (pp1 <> nil) and (pp^.Data = pp1^.Data) do
begin
inc(k);
pp := pp^.next;
pp1 := pp1^.next;
end;
if k > kmax then kmax := k;
p1 := p1^.next; { продолжаем внутренний цикл }
end;
p := p^.next; { Продолжаем цикл внешний }
end;
writeln(kmax);
Спасибо большое!!! теперь все стало гораздно понятнее))
p := L.first;
while p <> nil do
begin
p1 := L1.first; { <--- Это по поводу начала внутреннего цикла }
while p1 <> nil do
begin
k := 0;
pp := p; pp1 := p1; { А это - доп. переменные }
while (pp <> nil) and (pp1 <> nil) and (pp^.Data = pp1^.Data) do
begin
inc(k);
pp := pp^.next;
pp1 := pp1^.next;
end;
if k > kmax then kmax := k;
p1 := p1^.next; { продолжаем внутренний цикл }
end;
p := p^.next; { Продолжаем цикл внешний }
end;
writeln(kmax);
*оля*, тут возможны 2 варианта...
Первый (я буду удалять подпоследовательность из ПЕРВОГО списка, а не из второго):
{ Чуть-чуть изменяем цикл поиска (нам понадобится еще одна переменная)}
if k > kmax then
begin
kmax := k; p_del := p; { <--- Запоминаем, откуда начиналась самая длинная послед-ть }
end;
{ И после окончания циклов: }
p := p_del; { Запоминаем, где начиналась последовательность. Оно чуть ниже пригодится }
{ Удаляем обычным способом kmax элементов, начиная с запомненного }
for i := 1 to kmax do
begin
pp := p_del;
p_del := p_del^.next;
dispose(pp);
end;
{
А теперь проверяем, не равен ли L.first тому, запомненному адресу начала
последовательности. Если равен - значит наибольшая последовательность
была в самом начале списка, тогда все очень просто: началом списка будем
считать p_del, он теперь содержит адрес элемента, следующего за последним
удаленным...
А вот если последовательность начиналась не с начала списка - то чуть
сложнее, надо найти тот элемент, который _указывает_ на место, где раньше
была последовательность... То есть, тот, что находился ПЕРЕД ней. Найдем
его, и его NEXT поменяем на p_del...
}
if L.first = p then L.first := p_del
else begin
pp := L.first;
while pp^.next <> p do pp := pp^.next;
pp^.next := p_del;
end;
volvo, вы как всегда меня спасаете, спасибо большое!!!!
с первым вариантом разобралась,потом сделала так, чтобы удалялась последовательность из двух списков, а вот со вторым вариантом посложнее)
сейчас хочу сделать цикл:
repeat
- найти длину наибольшей общей подстроки;
-удалить найденную подстроку из списков;
- сложить все найденные длины наибольших общих подстрок;
(в общем все то, что вы мне уже помогли реализовать)
until kmax<=10; <--- но здесь наверняка не хватает чего-то? или вообще так нельзя будет организовать цикл?
А что будет делать этот цикл, расскажешь? Чего ты добиться хочешь?
Ну, так и будет, если не ошибаюсь:
sum := 0;
repeat
kmax : = { тут находишь kmax }
if kmax > 10 then begin
sum := sum + kmax;
{ Что там тебе еще надо было? Удалять подпоследовательности? Удаляем здесь }
end;
until kmax <= 10; { Как только kmax станет меньше 11, цикл закончится }
sum := 0;
repeat
kmax : = { тут находишь kmax }
if kmax > 10 then begin
sum := sum + kmax;
{ Что там тебе еще надо было? Удалять подпоследовательности? Удаляем здесь }
end;
until kmax <= 10; { Как только kmax станет меньше 11, цикл закончится }
Полный код (в виде PAS-файла) присоедини, посмотрим почему ошибка возникает...
*оля*, а причина - тривиальна, и Андрей уже говорил о ней: обнулить kmax надо. Если б ты это сделала в программе, то при оборачивании куска программы циклом, задумалась бы, а не надо ли инициализацию переменной делать внутри цикла. А так - нет и нет ее, и ничего не приходит в голову... Все просто:
{ Вот начало твоего цикла }
sum := 0;
repeat
kmax := 0; { <--- Фокус вот в этом !!! }
p := L.first;
{ ... }