Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.89
Includenv
Сообщений: n/a
#1

Задача «Общая подпоследовательность» - C++

28.10.2011, 21:54. Просмотров 2734. Ответов 35
Метки нет (Все метки)

Добрый день. Имеется, с виду, тривиальная задача. Напрягает только то, что даны три последовательности.

Условие
Даны три последовательности целых чисел. Ваша задача — найти их наибольшую общую
подпоследовательность.

Формат входного файла
Входной файл содержит описание трех последовательностей. Каждая последовательность
задается двумя строчками. Первая строка содержит длину последовательности n (1 ≤ n ≤ 100),
а вторая — ее элементы (32-х битные целые числа).

Формат выходного файла
Первая строка выходного файла должна содержать длину максимальной общей
подпоследовательности. Саму подпоследовательность необходимо вывести во второй строке.
Если таких строк несколько, можно вывести любую из них.

Пример
Миниатюры
Задача «Общая подпоследовательность»  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.10.2011, 21:54     Задача «Общая подпоследовательность»
Посмотрите здесь:

Задача на массивы: Найти самый год, в котором общая сумма продаж фирмы была минимальной за период учета - C++
добрые люди помогите сделать код для программы. Разработать программу для ввода информации о продажах торговой фирмы за несколько...

Строго возрастающая макс. подпоследовательность - C++
Долго ломал голову над задачей. Наконец-то нашел код (он правда, на паскале). Переделал, все хорошо. Но вот не задача: никак не могу...

Найти ее максимальную возрастающую подпоследовательность - C++
Здравствуйте, помогите студентке, завтра надо сдать задачи, одна не получается Дана последовательность целых чисел. Найти ее максимальную...

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

Выделить подпоследовательность удовлетворяющую заданному условию - C++
В заданной последовательности целых чисел найти с помощью процедуры максимально длинную подпоследовательность чисел такую ,что каждый...

Найти наибольшую возрастающую подпоследовательность в массиве - C++
Здравствуйте. Требуется найти наибольшую возрастающую подпоследовательность в массиве (для 1 2 3 1 2 5 6 1 будет 1 2 5 6). Вот...

Максимальная возрастающая подпоследовательность алгоритмами STL - C++
Доброго времени суток, уважаемые форумчане. Есть задача, реализовать алгоритм вычисления максимальной возрастающей...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 17:25     Задача «Общая подпоследовательность» #16
Ты действительно не понял вопроса?
Я указал просто строки без их длины.
Входной файл будет выглядеть так:
Код
3
1 2 3
3
2 1 3
3
3 1 2
Петррр
5946 / 3383 / 336
Регистрация: 28.10.2010
Сообщений: 5,927
29.10.2011, 17:34     Задача «Общая подпоследовательность» #17
Код
3
1 2 3
Жду Вашего кода.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 17:34     Задача «Общая подпоследовательность» #18
Я надеюсь, ты осознаёшь, что это неправильный ответ?
Петррр
5946 / 3383 / 336
Регистрация: 28.10.2010
Сообщений: 5,927
29.10.2011, 17:39     Задача «Общая подпоследовательность» #19
Я просто жду Вашего кода.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 17:40     Задача «Общая подпоследовательность» #20
Отлично.
Теперь, будь любезен, дай мне спокойно помочь автору найти правильное решение.
Спасибо.
Петррр
29.10.2011, 17:42
  #21

Не по теме:

Просто я просил ко мне обращаться на Вы. Но Вы этого не видите или не хотите видеть, поэтому я себя сейчас веду не спокойной. И отзыв этот будет не последним.

Includenv
Сообщений: n/a
29.10.2011, 18:52     Задача «Общая подпоследовательность» #22
Ребят, может хватит всё же холиварить..
Сыроежка
Заблокирован
29.10.2011, 18:56     Задача «Общая подпоследовательность» #23
Цитата Сообщение от volovzi Посмотреть сообщение
Не знаю, как это возможно. В строке
C++
1
vector<int> result = _intersection(_intersection(lst1, lst2), lst3);
приличный компилятор должен выдавать ошибку, т.к. результат выполнение функции "_intersection" не может быть передан по ссылке.

А свой пример я покажу тогда, когда посчитаю нужным. Я сюда не хвастаться пришёл.
Почему результат выполнения не может быть передан по ссылке? То есть я имею в виду, что результат выполнения функции _intersection является временный объект, который можно передать конструктору копирования, который принимает константную ссылку.на этот временный объект.
Петррр
5946 / 3383 / 336
Регистрация: 28.10.2010
Сообщений: 5,927
29.10.2011, 19:15     Задача «Общая подпоследовательность» #24
Я, кстати, признаю свои ошибки, и переделываю код. Просто задание не понял. Я думал что нужно переписать числа, которые есть во всех трех последовательностях.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:34     Задача «Общая подпоследовательность» #25
Цитата Сообщение от Includenv Посмотреть сообщение
Ребят, может хватит всё же холиварить..
А ты собираешься решать задачу, или будешь ждать, пока всё сделают за тебя?

Цитата Сообщение от Сыроежка Посмотреть сообщение
Почему результат выполнения не может быть передан по ссылке? То есть я имею в виду, что результат выполнения функции _intersection является временный объект, который можно передать конструктору копирования, который принимает константную ссылку.на этот временный объект.
Где в программе, о которой идёт речь, ты видишь константную ссылку?
Петррр
5946 / 3383 / 336
Регистрация: 28.10.2010
Сообщений: 5,927
29.10.2011, 19:37     Задача «Общая подпоследовательность» #26
Каким образом в первом примере результат
Код
1 3
?
Сыроежка
Заблокирован
29.10.2011, 19:39     Задача «Общая подпоследовательность» #27
Цитата Сообщение от volovzi Посмотреть сообщение
А ты собираешься решать задачу, или будешь ждать, пока всё сделают за тебя?


Где в программе, о которой идёт речь, ты видишь константную ссылку?
Я имел в виду, что в следующем предложении
C++
1
 vector<int> result = _intersection(_intersection(lst1, lst2), lst3);
создается объект result с помощью конструктора копирования.
То есть я имел в виду возвращаемое значение функции. Но ежели в самой функции параметры описаны как просто ссылки, а не констатные ссылки, то конечно такой вызов _intersection(_intersection(lst1, lst2), lst3); должен у компилятора породить вопросы.
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:42     Задача «Общая подпоследовательность» #28
Петррр,
Почитай вот тут: http://ru.wikipedia.org/wiki/Наиболь...едовательность
или у Кормена.

Добавлено через 1 минуту
Сыроежка, о том и речь.
"_intersection" в качестве первого параметра принимает результат выполнения самой себя, при этом первым параметром является неконстантная ссылка.
Петррр
5946 / 3383 / 336
Регистрация: 28.10.2010
Сообщений: 5,927
29.10.2011, 19:46     Задача «Общая подпоследовательность» #29
Типа между элементами тоже могут быть элементы?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.10.2011, 19:48     Задача «Общая подпоследовательность»
Еще ссылки по теме:

Найти наибольшую общую подпоследовательность двух последовательностей - C++
Задача об отыскании наибольшей общей подпоследовательности (динамическое программирование). Даны две последовательности символов (строки),...

Найти максимальную возрастающую подпоследовательность в одномерном массиве - C++
Помогите найти максимальную возрастающую подпоследовательность в одномерном массиве.

Найти максимально длинную подпоследовательность чисел по условию - C++
В заданной последовательности целых чисел найти с помощью процедуры максимально длинную подпоследовательность чисел такую, что каждый...

В заданном числе найти максимальную по длине подпоследовательность - C++
В данном числе m найти максимальную по длине подпоследовательность так,чтобы элементы были в возрастающем порядке.... помогите плиз...

Выделить подпоследовательность, начиная с минимального элемента и до конца последовательности - C++
вот код программы : #include &lt;iostream&gt; using namespace std; int* entseq(int); int searchmin(int*); int output(int*,int); ...


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

Или воспользуйтесь поиском по форуму:
volovzi
267 / 169 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:48     Задача «Общая подпоследовательность» #30
Типа могут.
"Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое)."
Yandex
Объявления
29.10.2011, 19:48     Задача «Общая подпоследовательность»
Ответ Создать тему
Опции темы

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