Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/12: Рейтинг темы: голосов - 12, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 25.07.2019
Сообщений: 1
1

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

25.07.2019, 17:47. Просмотров 2272. Ответов 1
Метки нет (Все метки)


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
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    int n, m;
    cin >> n;
    vector <int> a (1001, 0);
    for (int i = 1; i <= n; i++)
        cin >> a.at(i);
 
    cin >> m;
    vector <int> b (1001, 0);
    for (int i = 1; i <= m; i++)
        cin >> b.at(i);
 
    vector <vector <int> > matrix (1001, vector <int> (1001));
    //создание матрицы
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a.at(i) == b.at(j))
                matrix.at(i).at(j) = matrix.at(i - 1).at(j - 1) + 1;
            else
                matrix[i][j] = max(matrix.at(i - 1).at(j), matrix.at(i).at(j - 1));
/*
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << matrix.at(i).at(j) << " ";
        cout << endl;
    }
    cout << endl;
*/
    int i = n;
    int j = m;
    int temp = matrix.at(i).at(j);
    vector <int> result;
 
    while (i >= 1 && j >= 1 && c >= 1)
    {
        while (matrix.at(i - 1).at(j) == temp)
            i--;
        while (matrix.at(j).at(i) == temp)
            j--;
        result.at(c - 1).push_back(a.at(i - 1));
        c--;
    }
 
    for (int i = 0; i < result.size(); i++)
        cout << result.at(i) << " ";
    return 0;
}
↑код
Задача:
Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.
В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

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

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

Помогите пожалуйста
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.07.2019, 17:47
Ответы с готовыми решениями:

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

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

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

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

__________________
Помогаю в написании студенческих работ здесь.
Записывайтесь на профессиональные курсы C++ разработчиков
1
806 / 495 / 209
Регистрация: 19.01.2019
Сообщений: 1,194
27.07.2019, 13:01 2
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
#include <iostream>
#include <algorithm>
#include <vector>
 
std::vector<int> LCS(std::vector<int>& seq1, std::vector<int>& seq2) {
    size_t width = seq1.size() + 1;
    size_t height = seq2.size() + 1;
    std::vector<size_t> mx(width * height);
    std::fill(mx.begin(), mx.end(), 0);
    for (size_t i = 1; i < width; ++i) {
        for (size_t j = 1; j < height; ++j) {
            if (seq1[i - 1] == seq2[j - 1]) {
                mx[i * height + j] = mx[(i - 1) * height + j - 1] + 1;
            }
            else {
                mx[i * height + j] = std::max(mx[(i - 1) * height + j], mx[i * height + j - 1]);
            }
        }
    }
    ///backtrack
    std::vector<int> ret;
    size_t i = seq1.size();
    size_t j = seq2.size();
 
    while (i != 0 && j != 0) {
        if (seq1[i - 1] == seq2[j - 1]) {
            ret.push_back(seq1[i - 1]);
            --i; --j;
        }
        else if (mx[i * (seq2.size() + 1) + j - 1] > mx[(i - 1) * (seq2.size() + 1) + j]) {
            --j;
        }
        else {
            --i;
        }
    }
    std::reverse(ret.begin(), ret.end());
    return ret;
}
 
void show(std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << (char)vec[i] << ' ';   //as char
    }
    std::cout << '\n';
}
test

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main()
{
    {
        std::vector<int> s1 = { 'g', 'a', 'c' };
        std::vector<int> s2 = { 'a', 'g', 'c', 'a', 't' };
        std::vector<int> lcs = LCS(s1, s2);
        show(lcs);
    }
    {
        std::vector<int> s1 = { 'x', 'm', 'j', 'y', 'a', 'u', 'z' };
        std::vector<int> s2 = { 'm', 'z', 'j', 'a', 'w', 'x', 'u' };
        std::vector<int> lcs = LCS(s1, s2);
        show(lcs);
    }
    {
        std::vector<int> s1;
        std::vector<int> s2;
        std::vector<int> lcs = LCS(s1, s2);
        show(lcs);
    }
 
    return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.07.2019, 13:01

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

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.