Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ где ошибка ? https://www.cyberforum.ru/ cpp/ thread260525.html
помогите найти ошибку #include <stdio.h> main() { int n,i,j; double a,b; while(1) { printf ("/n Vvedite kol elem-ov n=") ; scanf ("d",&n) ;
Поиск слов и замена окончаний C++
потребуется программа которая бы в тексте искала слова с окончанием "ing" и заменяла бы эти окончания на "ed" я с цыклом не могу разобраться!!!
C++ Borland C++ Bouilder 6 или microsoft visual c++ https://www.cyberforum.ru/ cpp/ thread260305.html
Подскажите пожалуста какой редактор лучше выбрать Borland C++ Bouilder 6 или microsoft visual c++. Мне советовали visual c++ говорят в нем больше функций. Я сам только начинаю учиться C++ у меня уже...
C++ Нужно сделать программу работоспособной с малейшими изменениями. https://www.cyberforum.ru/ cpp/ thread260265.html
Я новичок в языке программирования. Помогите пожалуйста. Задание: Даны два файла. Найти в них несовпадающие слова, имеющие не менее 2 цифр. Вывести каждое такое слово в отдельную строку. За словом...
Как предать указатель через LPARAM C++
Хочу обойтись без глобальных объектов в приложении на Win32Api, в приложении из GUI только два диалога (за основное окно отдувается один из диалогов), можно как-нибудь передать указатель на объект...
C++ Обход элементов std::map в порядке их создания https://www.cyberforum.ru/ cpp/ thread260073.html
Имеется ассоциативный массив и его заполнение: std::map<unsigned,string> arr; arr = "abc"; arr = "def"; arr = "ghi"; Теперь если я буду обходить этот массив при помощи итераторов, то обход...
C++ WDK и Visual Studio 2008 https://www.cyberforum.ru/ cpp/ thread260057.html
Всем доброго времени суток. Скачал Windows DDK с майкрософта. Установил в C:\WinDDK\7600.16385.1 Включил в свойствах, (свойства конфигурации -> c\c++) Дополнительные каталоги включения:...
C++ Зацикливается при неверном вводе
есть такой кусочек while(true) { scanf("%d%c%d", &x, &zn, &y); switch (zn) { case '+': rez=x+y; break;
C++ Функции https://www.cyberforum.ru/ cpp/ thread259751.html
Составить процедуру, результатом работы которой является символ, заданный при обращении к этой процедуре, если этот символ не является буквой, и соответствующая строчная (малая) буква в противном. ...
C++ Работа с командной строкой https://www.cyberforum.ru/ cpp/ thread259691.html
Ситуация: у меня есть программа-интерпретатор другого языка. Работает через командную строку. Преподаватель попросил следующее: реализовать простейшие арифметические операции, которые при этом...
C++ Ошибка в программе
пишу задачу на классы в Си++,но не могу разобраться что за ошибка,помогите это очень важно #include<iostream.h> #include<conio.h> #include<math.h> #include<stdio.h> class Student { private:
C++ Симуляция нажатия кнопки https://www.cyberforum.ru/ cpp/ thread259267.html
ПОДСКАЖИТЕ как сделать симуляцию нажатия кнопки в заданое время. т.е. мне нужно что бы клавиша ENTER нажалась в определенное время без моего присутствия
1336 / 987 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
0

Наибольшая общая подпоследовательность с восстановлением ответа - C++ - Ответ 1467798

20.03.2011, 15:30. Показов 7758. Ответов 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;
}

Что неверно?

Вернуться к обсуждению:
Наибольшая общая подпоследовательность с восстановлением ответа C++
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.03.2011, 15:30
Помогаю со студенческими работами здесь

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

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

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

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

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

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

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