Форумы-->Форум для внеигровых тем--> 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К списку тем
|