1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
1

Наибольшая общая подпоследовательность с восстановлением ответа

20.03.2011, 15:30. Показов 9330. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Условие
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

Формат входных данных

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

Формат выходных данных

Требуется вывести наибольшую общую подпоследовательность данных последовательностей, через пробел.

Решение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
 
using namespace std;
 
void lcs(vector<int> &a, vector<int> &b)
{
    int i, j, as = a.size(), bs = b.size(), c;
 
    vector<vector<int> > g(as+1, vector<int>(bs+1, 0));
 
    for (i = 0; i <= as; i++)
      for (j = 0; j <= bs; j++)
        g[i][j] = 0;
 
    for (i = 1; i <= as; i++)
      for (j = 1; j <= bs; j++)
        if (a[i-1] == b[j-1]) g[i][j] = g[i-1][j-1] + 1;
        else g[i][j] = max(g[i-1][j], g[i][j-1]);
 
    i = as; j = bs; c = g[as][bs];
    vector<int> res(c);
 
    while ((i != 0) & (j != 0) & (c != 0)) {
      while (g[i-1][j] == c) i--;
      while (g[i][j-1] == c) j--;
      res[c-1] = a[i-1];
      c--;
    }
 
    if (res.size()) cout << res[0];
    for (i = 1; i < res.size(); i++) cout << ' ' << res[i];
}
 
int main()
{
    int n, m, i, t;
 
    cin >> n;
    vector<int> a;
 
    for (i = 0; i < n; i++) {
      cin >> t;
      a.push_back(t);
    }
 
    cin >> m;
 
    vector<int> b;
 
    for (i = 0; i < m; i++) {
      cin >> t;
      b.push_back(t);
    }
 
    lcs(a, b);
 
    return 0;
}

Что неверно?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.03.2011, 15:30
Ответы с готовыми решениями:

наибольшая общая подпоследовательность с восстановлением ответа
#include &lt;bits/stdc++.h&gt; using namespace std; int main() { ...

Наибольшая возрастающая подпоследовательность за O(NlogN)
Здравствуйте! Вот тут написал код НВП за О(NlogN).Но на тестирующей системе он выдает на тесты...

Наибольшая общая подпоследовательность
Я правда не знаю в том ли разделе я создал. Надо определить наибольшую общую...

Наибольшая общая подпоследовательность
Здравствуйте, написал код для задачи Наибольшая общая подпоследовательность Задана...

2
Эксперт С++
476 / 444 / 34
Регистрация: 20.11.2009
Сообщений: 1,293
20.03.2011, 17:28 2
Цитата Сообщение от iama Посмотреть сообщение
for (i = 0; i <= as; i++)
for (j = 0; j <= bs; j++)
g[i][j] = 0;
Векторы сами нулями инициализируются.

Контртест:
Код
5
5 6 1 2 6
6
1 2 3 4 5 6
Дебажьте.
2
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
20.03.2011, 21:19  [ТС] 3
Хохол, гран-мерси
0
20.03.2011, 21:19
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.03.2011, 21:19
Помогаю со студенческими работами здесь

Наибольшая общая подпоследовательность
Здравствуйте, подскажите, пожалуйста, каким способом можно найти НОП для количества строк &gt;=2

Наибольшая возрастающая подпоследовательность
program true2; {$APPTYPE CONSOLE} uses SysUtils; const n=5; plusinf=88; ...

Наибольшая монотонная подпоследовательность
Пожалуйста, подскажите не готовый ответ, а идею. Хочется самой дойти. Дана конечная...

Наибольшая возрастающая подпоследовательность
Дна последовательность, нужно найти её наибольшую возрастающую подпоследовательность. Входные...

Наибольшая пилообразная подпоследовательность
добрый вечер. Кто нибудь может подсказать? Числовая последовательность называется пилообразной...

Наибольшая возрастающая подпоследовательность (LIS)
Доброго времени суток! Я не сильно разбираюсь в шарпе(совсем) и при выполнении одного задания...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru