алгоритмы поиска |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
алгоритмы поиска |
*оля* |
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
если даны два списка чисел и нужно найти наибольшую одинаковую последовательность чисел, например, если дано:
1 2 3 4 5 6 1 2 6 2 3 4 то должен вывести 234 подскажите пожалуйста, каким алгоритмом тут лучше воспользоваться? |
*оля* |
Сообщение
#2
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
попробовала написать программу для 2х массивов, которая выдаст длину наибольшей общей последовательности, но что-то не совсем получилось
. не подскажете где ошибка? или это вообще неудачная идея так решать данную задачу? Сообщение отредактировано: *оля* - |
volvo |
Сообщение
#3
|
Гость |
Это задача о Наибольшей Общей Подпоследовательности. Динамическое программирование.
Как решать - можно посмотреть здесь: Пример №2 |
TarasBer |
Сообщение
#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]; -------------------- |
*оля* |
Сообщение
#5
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
в другой книге написано в одной строчке по-другому немного:
else if c[i-1,j] >= c[i,j-1] then ... а я вообще не могу понять, где что делается( Добавлено через 5 мин. Ну, например, что происходит, когда i1 и j1 становятся больше 10? хм, да, не подумала... а если ввести ограничения, то все равно что-то не то, значит и еще есть ошибки, но я их не вижу Сообщение отредактировано: *оля* - |
TarasBer |
Сообщение
#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. С чего этому НОПу быть именно в конце у обоих? -------------------- |
*оля* |
Сообщение
#7
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
все, в своем не совсем удачном алгоритме нашла еще ошибку, теперь и у меня работает! спасибо за помощь!
алгоритмы, которые я смотрела, считают, что, если заданы строки: 123 и 1523, то наибольшая общая подпоследовательность будет 123 (наверное, это из определения подпоследовательности), а мне нужно было решить задачу, чтобы выводилось 23. Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?(если дано: 123 и 1523, то выдает 123) |
TarasBer |
Сообщение
#8
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> Поэтому не могу найти алгоритм, который подойдет, а в алгоритме по ссылке что-то разобраться до сих пор не могу, может он тоже ищет подпоследовательность, как в первом случае?
Выходит, что так. Всё, теперь я тоже врубился, почему такой результат. Ну да, тут-то надо подпоследовательность подряд идущих элементов, а тот алгоритм ищет и раскиданную подпоследовательность. Но тут тоже надо подумать над оптимизацией. Пока что есть O(m*n*min(m,n)), короче кубическая сложность. -------------------- |
*оля* |
Сообщение
#9
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
|
TarasBer |
Сообщение
#10
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
А, в википедии же есть аналогичный алгоритм, но как раз для подстрок, а не подпоследовательностей, ровно то, что тут надо: http://ru.wikipedia.org/wiki/Наибольшая_общая_подстрока
-------------------- |
TarasBer |
Сообщение
#11
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
http://e-maxx.ru/algo/suffix_automata
Тут уже за o(m+n) Я проверил, слово в слово переписал сишный алгоритм на паскаль, вроде работает. Впрочем, вряд ли вам задавали суффиксные автоматы, это уже дебри пошли. -------------------- |
*оля* |
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
Спасибочки большое!!!)))
ну да, это уже все сложно, но ради интереса попробую разобраться))) |
Lapp |
Сообщение
#13
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
это уже все сложно, но ради интереса попробую разобраться))) Ты обязательно попробуй, но сначала я бы советовал разобраться с тем, что ты сама сделала )). Можно дать несколько советов? Посмотри - это твой код, немного улучшенный: const Далее, в порядке "прихода в голову", а не в порядке важности: 1. Всегда старайся избегать явного указания чисел в программе, заводи константы (у меня - n). 2. Почему у тебя по i цикл while, а по j - for? 3. ВСЕ переменные перед использованием должны быть инициированы (у тебя не инициированы k и kmax). 4. Твои if и while внутри цикла выполняют выполняют одну и ту же функцию - объедини их )). 5. Избегай лишних переменных. 6. Не нужно дважды объявлять один тип там, где это _не_нужно_. Формально твои а и а1 принадлежат к разным типам. Тут это не важно, но в принципе может вызвать проблемы. 7. форматирование кода - не для красоты, оно имеет четкие правила, которых необходимо придерживаться - иначе утонешь в коде большем, чем одна страница.. Возьми за пример мой код, попробуй вывести правила из его формата. А вообще - +1 за то, что сама решаешь )). -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
*оля* |
Сообщение
#14
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
Можно дать несколько советов? Буду только благодарна!)) Посмотри - это твой код, немного улучшенный: while a[i+k]=b[j+k] do Inc(k);. не утверждаю, но возможно, тут не хватает еще одного условия? За алгоритм спасибо, он гораздо лучше моего) И за все советы спасибо, постараюсь исправиться. Правда я писала эту программу, чтобы просто попробовать сначала решить, а как дело дошло до самой задачи, то снова появились проблемы. Тут было написано для двух массивов, а в задаче 2 динамических списка. Можно ли данный алгоритм преобразовать к этой задаче или проще 2 списка изначально заменить двумя динамическими массивами? А вообще - +1 за то, что сама решаешь )). спасибо) Сообщение отредактировано: *оля* - |
*оля* |
Сообщение
#15
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
что-то совсем у меня со списками ничего не получается, пыталась изменить ваш алгоритм под свою задачу, но не выходит пока(
type не могли бы вы помочь разобраться? |
volvo |
Сообщение
#16
|
Гость |
Цитата до этого значение уже было изменено, и теперь тут не то, что нужно Естественно. Вот при работе со списками как раз нужны доп. переменные, потому что у тебя нет возможности обращаться к любому элементу списка напрямую, как в массиве. И не забывай, что при переходе на следующий элемент внешнего цикла, внутренний начинается с самого начала:p := L.first; |
*оля* |
Сообщение
#17
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
Спасибо большое!!! теперь все стало гораздно понятнее))
|
*оля* |
Сообщение
#18
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
p := L.first; А если после того, как нашли эту подстроку, нужно ее удалить, то как это сделать можно? Знаю, как удалить один элемент, а вот как удалить подстроку из списка не понимаю ( Подскажите пожалуйста как поступить, заранее спасибо!) |
volvo |
Сообщение
#19
|
Гость |
*оля*, тут возможны 2 варианта...
Первый (я буду удалять подпоследовательность из ПЕРВОГО списка, а не из второго): { Чуть-чуть изменяем цикл поиска (нам понадобится еще одна переменная)} Это все, можно теперь печатать список, найденая последовательность из него уже удалена... Это был первый способ. Второй похож, но немного отличается - не удалять элементы один за одним в цикле, а просто пропускать их (переходить к следующему). Как только дошли до конца нашей последовательности, "обрубаем" список NIL-ом и чуть-чуть подправляем указатели так, чтобы "вырезанный" кусок был отдельно, а то, что было ПЕРЕД и ПОСЛЕ него - склеиваем в одно. Это не так сложно, как кажется, достаточно нарисовать на бумажке список и посмотреть, куда какие связи надо установить... Если у тебя уже есть подпрограмма, удаляющая список, то я бы все-таки попробовал реализовать именно второй метод на твоем месте, потому что удалять тот, "вырезанный" кусок можно с помощью готовой подпрограммы (это ведь самостоятельный список, у нас есть адрес его начала, он заканчивается пустым указателем, как положено), а это всегда лучше, не будет дублирования кода... Вот у меня сейчас подпоследовательность удаляется в одном месте, а сами списки я буду удалять в другом, это приведет к копированию куска кода. Так что все-таки попробуй реализовать второй вариант, если что не получится - говори, подскажем |
*оля* |
Сообщение
#20
|
Пионер Группа: Пользователи Сообщений: 125 Пол: Женский Репутация: 1 |
volvo, вы как всегда меня спасаете, спасибо большое!!!!
с первым вариантом разобралась,потом сделала так, чтобы удалялась последовательность из двух списков, а вот со вторым вариантом посложнее) сейчас хочу сделать цикл:
если так и писать цикл, то делает один раз только все. И нужно ли писать в конце "пока kmax<=10 или количество компонентов списка1 или списка2 равно 0"? я запуталась, помогите пожалуйста) Сообщение отредактировано: *оля* - |
Текстовая версия | 15.05.2024 10:53 |