Об игре
Новости
Войти
Регистрация
Рейтинг
Форум
12:21
4390
 online
Требуется авторизация
Вы не авторизованы
   Форумы-->Форум для внеигровых тем-->
1|2|3

АвторС++
"10. Даны две последовательности A=(ai) , i=1..n, (n,<=10) и В=(bj), j=1..m, (m<=10) целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка n*k."
Ребят, подскажите, что они от меня хотят-то? Если эта подсказка будет на языке - спасибо будет еще больше. Но хоть вообще, в чём суть задачи-то? Оно имеет от меня ускользать.
Армия, я не твой...
k встречается впервые в конце условия. Вероятно, это было m.
Ребят, подскажите, что они от меня хотят-то?
Скажи конкретно, что тебе непонятно.
последовательности, являющейся подпоследовательностью обеих последовательностей.
Вот не могу (возможно в связи с поздним временем и выходными) понять, что это значит.
Да что там той армии. Служи солдат, как дед служил.

У нас был один паренек, домашний такой, из семьи с немецкой фамилией.
Сопромат не сдал в универе. Ну ничо, человеком стал. А после дембеля восстановился и закончил. Говорят, всю группу гонял там.
Последовательность x(k), k=1..t является подпоследовательностью a(i), если есть такое n, что x(k) = a(k+n) для всех k=1..t. Например, x(k) = (4, 6, 3, 1) является подпоследовательностью a(i) = (9, 2, 4, 6, 3, 1, 7), в качестве n следует взять 2. Постарался наиболее доступно. Собственно, длина последовательности будет t. Тебя просят найти для фиксированных a(i), b(j) максимальное t, что существует x(k), k=1..t, а х является подпоследовательностью a и подпоследовательностью b.
для Bartello_Aid:
"Гонялки" я уже нарастил в качалке. Стрелять умею, строем ходить не люблю. Так что, рассказывайте, что в задаче ввиду имеют. )
6
учитель, не?) так "завернул", теперь точно ТС без литра не разберется..)
Совпадения короче! Например в первой последовательности есть"... 2, 3..." и во второй те же "...2, 3...".
для Страус:
Спасибо.
a(i) = (9, 2, 4, 6, 3, 1, 7), в качестве n следует взять 2
Может быть, n=3? Или я пока не до конца понял?
для GINdog:
Суть - найти дли максимальной подпоследовательности :) Ну т.е. есть две последовательности:
1,7,3,4,5
5,3,4,5,8,1

Самая длинная подпоследовательность - 3,4,5. Её длина = 3
Надо решить задачу в общем случае.

При этом всём количество операций должно быть порядка n*k. Хз, как именно это отразится на решении задачи, лень считать число операций для решения "в лоб". Возможно, потребуется запользовать какой-нибудь умный алгоритм из интернета, благо нахождение общей подпоследовательности - задача хорошо изученная и описанная.
есть два множества, нужно найти их пересечение

"количество операций порядка n*k" предполагает тупой алгоритм типа
Prelude> let isect a b = filter (\x-> length(filter (==x) b) > 0 ) a
Prelude> isect [1,2,3] [1,3,5]
[1,3]
Спасибо, ребята. Кажется, просветлился. Завтра попробую написать. А теперь спааать.
12-й пост считать бредом... там подпоследовательность нужна, не пересечение
для GINdog:
Чё-та делать нечего было... :
http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_subsequence#C.2B.2 B

Готовое решение с полным перебором. Собственно, количество операций действительно этого порядка, динамического программирования вроде не требуется.
Решается чем-то вроде
max_length = 0;
tek_length = 0;
for(int i = 0 ; i < first_array_length ; i++)
{
for(int j = 0 ; j < second_array_length ; j++)
{
if(A[i] == B[j])
{
tek_length = 1;
next_i = i;
next_j = j;
BOOL matches = true;
while(next_i < first_array_length && next_j < second_array_length && matches)
{
next_i++; next_j++;
if(A[next_i] == B[next_j])
{
//vse norm, pribavlyaem dlinu
}
else
{
//fiksiruem tek dlinu i pishem v max_length esli bol'she
matches = false;
}
}
}
}
}
Ой, т.е. в посте 15 алгоритм поиска самой длинной общей подпоследовательности. Если нужна длина, то решение стоит немного подправить.
Эх, неформатированный получился( Можно красивее, через рекурсию, но за пару минут мне проще такой набросать)
Даже не в else фиксируем длину и сравниваем с max_length, а после while) да) вот так будет быстро и просто)
для alex_kocharin:
Prelude> let isect a b = filter (\x-> length(filter (==x) b) > 0 ) a
Prelude> isect [1,2,3] [1,3,5]
[1,3]

я тоже люблю хаскелль, но нужен С++)
1|2|3
К списку тем
2007-2025, онлайн игры HeroesWM