IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> алгоритмы поиска
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


если даны два списка чисел и нужно найти наибольшую одинаковую последовательность чисел, например, если дано:
1 2 3 4 5 6
1 2 6 2 3 4
то должен вывести 234
подскажите пожалуйста, каким алгоритмом тут лучше воспользоваться?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


попробовала написать программу для 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.


.

не подскажете где ошибка? или это вообще неудачная идея так решать данную задачу?

Сообщение отредактировано: *оля* -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Это задача о Наибольшей Общей Подпоследовательности. Динамическое программирование.

Как решать - можно посмотреть здесь: Пример №2
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


> не подскажете где ошибка?

Ну, например, что происходит, когда i1 и j1 становятся больше 10? Впрочем,

> это вообще неудачная идея так решать данную задачу

Хоть такое решение первым приходит в голову, но в лоб решать задачу не стоит.

Надо делать, как по ссылке. Вот только там нет опечатки?
Вот в этом месте:
Код


if x[i]=y[j] then
    c[i, j]:=c[i-1, j-1] + 1
else
    if c[i-1, j]=c[i, j-1] then
        c[i, j]:=c[i-1, j]
    else
        c[i, j]:=c[i, j-1];



--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


в другой книге написано в одной строчке по-другому немного:
 else if c[i-1,j] >= c[i,j-1] then ...

а я вообще не могу понять, где что делается(

Добавлено через 5 мин.
Цитата(TarasBer @ 17.05.2010 13:49) *

Ну, например, что происходит, когда i1 и j1 становятся больше 10?


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

Сообщение отредактировано: *оля* -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


> в другой книге написано в одной строчке по-другому немного:

А вот если там >= вместо =, то это уже ближе к истине.
Правда, время за 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. С чего этому НОПу быть именно в конце у обоих?


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


все, в своем не совсем удачном алгоритме нашла еще ошибку, теперь и у меня работает! спасибо за помощь!

алгоритмы, которые я смотрела, считают, что, если заданы строки:
123 и 1523, то наибольшая общая подпоследовательность будет 123 (наверное, это из определения подпоследовательности),
а мне нужно было решить задачу, чтобы выводилось 23.
Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?(если дано: 123 и 1523, то выдает 123)

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


> Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?

Выходит, что так.
Всё, теперь я тоже врубился, почему такой результат. Ну да, тут-то надо подпоследовательность подряд идущих элементов, а тот алгоритм ищет и раскиданную подпоследовательность.
Но тут тоже надо подумать над оптимизацией. Пока что есть O(m*n*min(m,n)), короче кубическая сложность.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


Цитата(TarasBer @ 19.05.2010 12:44) *

Пока что есть O(m*n*min(m,n)), короче кубическая сложность.

мда, надо подумать, как исправить, так оставлять не хочется.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


А, в википедии же есть аналогичный алгоритм, но как раз для подстрок, а не подпоследовательностей, ровно то, что тут надо: http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


http://e-maxx.ru/algo/suffix_automata

Тут уже за o(m+n)
Я проверил, слово в слово переписал сишный алгоритм на паскаль, вроде работает.
Впрочем, вряд ли вам задавали суффиксные автоматы, это уже дебри пошли.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


Спасибочки большое!!!)))
ну да, это уже все сложно, но ради интереса попробую разобраться)))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(*оля* @ 21.05.2010 20:57) *
это уже все сложно, но ради интереса попробую разобраться)))
Ты обязательно попробуй, но сначала я бы советовал разобраться с тем, что ты сама сделала )). Можно дать несколько советов?

Посмотри - это твой код, немного улучшенный:
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.

Далее, в порядке "прихода в голову", а не в порядке важности:

1. Всегда старайся избегать явного указания чисел в программе, заводи константы (у меня - n).

2. Почему у тебя по i цикл while, а по j - for?

3. ВСЕ переменные перед использованием должны быть инициированы (у тебя не инициированы k и kmax).

4. Твои if и while внутри цикла выполняют выполняют одну и ту же функцию - объедини их )).

5. Избегай лишних переменных.

6. Не нужно дважды объявлять один тип там, где это _не_нужно_. Формально твои а и а1 принадлежат к разным типам. Тут это не важно, но в принципе может вызвать проблемы.

7. форматирование кода - не для красоты, оно имеет четкие правила, которых необходимо придерживаться - иначе утонешь в коде большем, чем одна страница.. Возьми за пример мой код, попробуй вывести правила из его формата.

А вообще - +1 за то, что сама решаешь )).


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


Цитата(Lapp @ 22.05.2010 4:21) *

Можно дать несколько советов?

Буду только благодарна!))
Цитата(Lapp @ 22.05.2010 4:21) *


Посмотри - это твой код, немного улучшенный:

 while a[i+k]=b[j+k] do Inc(k);

.
не утверждаю, но возможно, тут не хватает еще одного условия?
За алгоритм спасибо, он гораздо лучше моего)


И за все советы спасибо, постараюсь исправиться. Правда я писала эту программу, чтобы просто попробовать сначала решить, а как дело дошло до самой задачи, то снова появились проблемы.

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

Цитата(Lapp @ 22.05.2010 4:21) *

А вообще - +1 за то, что сама решаешь )).

спасибо)

Сообщение отредактировано: *оля* -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


что-то совсем у меня со списками ничего не получается, пыталась изменить ваш алгоритм под свою задачу, но не выходит пока(

 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.


не могли бы вы помочь разобраться?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






Цитата
до этого значение уже было изменено, и теперь тут не то, что нужно
Естественно. Вот при работе со списками как раз нужны доп. переменные, потому что у тебя нет возможности обращаться к любому элементу списка напрямую, как в массиве. И не забывай, что при переходе на следующий элемент внешнего цикла, внутренний начинается с самого начала:

  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);

 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


Спасибо большое!!! теперь все стало гораздно понятнее))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


Цитата(volvo @ 23.05.2010 16:09) *

  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);




А если после того, как нашли эту подстроку, нужно ее удалить, то как это сделать можно? Знаю, как удалить один элемент, а вот как удалить подстроку из списка не понимаю (
Подскажите пожалуйста как поступить, заранее спасибо!)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






*оля*, тут возможны 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;


Это все, можно теперь печатать список, найденая последовательность из него уже удалена...

Это был первый способ. Второй похож, но немного отличается - не удалять элементы один за одним в цикле, а просто пропускать их (переходить к следующему). Как только дошли до конца нашей последовательности, "обрубаем" список NIL-ом и чуть-чуть подправляем указатели так, чтобы "вырезанный" кусок был отдельно, а то, что было ПЕРЕД и ПОСЛЕ него - склеиваем в одно. Это не так сложно, как кажется, достаточно нарисовать на бумажке список и посмотреть, куда какие связи надо установить...

Если у тебя уже есть подпрограмма, удаляющая список, то я бы все-таки попробовал реализовать именно второй метод на твоем месте, потому что удалять тот, "вырезанный" кусок можно с помощью готовой подпрограммы (это ведь самостоятельный список, у нас есть адрес его начала, он заканчивается пустым указателем, как положено), а это всегда лучше, не будет дублирования кода... Вот у меня сейчас подпоследовательность удаляется в одном месте, а сами списки я буду удалять в другом, это приведет к копированию куска кода.

Так что все-таки попробуй реализовать второй вариант, если что не получится - говори, подскажем smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Пионер
**

Группа: Пользователи
Сообщений: 125
Пол: Женский

Репутация: -  1  +


volvo, вы как всегда меня спасаете, спасибо большое!!!! smile.gif

с первым вариантом разобралась,потом сделала так, чтобы удалялась последовательность из двух списков, а вот со вторым вариантом посложнее)

сейчас хочу сделать цикл:


repeat

- найти длину наибольшей общей подстроки;
-удалить найденную подстроку из списков;
- сложить все найденные длины наибольших общих подстрок;
(в общем все то, что вы мне уже помогли реализовать)

until kmax<=10; <--- но здесь наверняка не хватает чего-то? или вообще так нельзя будет организовать цикл?





если так и писать цикл, то делает один раз только все.
И нужно ли писать в конце "пока kmax<=10 или количество компонентов списка1 или списка2 равно 0"? я запуталась, помогите пожалуйста)

Сообщение отредактировано: *оля* -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 17:43
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name