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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.89
Includenv
Сообщений: n/a
28.10.2011, 21:54     Задача «Общая подпоследовательность» #1
Добрый день. Имеется, с виду, тривиальная задача. Напрягает только то, что даны три последовательности.

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

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

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

Пример
Миниатюры
Задача «Общая подпоследовательность»  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Петррр
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 является временный объект, который можно передать конструктору копирования, который принимает константную ссылку.на этот временный объект.
Петррр
 Аватар для Петррр
5914 / 3351 / 333
Регистрация: 28.10.2010
Сообщений: 5,926
29.10.2011, 19:15     Задача «Общая подпоследовательность» #24
Я, кстати, признаю свои ошибки, и переделываю код. Просто задание не понял. Я думал что нужно переписать числа, которые есть во всех трех последовательностях.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:34     Задача «Общая подпоследовательность» #25
Цитата Сообщение от Includenv Посмотреть сообщение
Ребят, может хватит всё же холиварить..
А ты собираешься решать задачу, или будешь ждать, пока всё сделают за тебя?

Цитата Сообщение от Сыроежка Посмотреть сообщение
Почему результат выполнения не может быть передан по ссылке? То есть я имею в виду, что результат выполнения функции _intersection является временный объект, который можно передать конструктору копирования, который принимает константную ссылку.на этот временный объект.
Где в программе, о которой идёт речь, ты видишь константную ссылку?
Петррр
 Аватар для Петррр
5914 / 3351 / 333
Регистрация: 28.10.2010
Сообщений: 5,926
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
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:42     Задача «Общая подпоследовательность» #28
Петррр,
Почитай вот тут: http://ru.wikipedia.org/wiki/Наиболь...едовательность
или у Кормена.

Добавлено через 1 минуту
Сыроежка, о том и речь.
"_intersection" в качестве первого параметра принимает результат выполнения самой себя, при этом первым параметром является неконстантная ссылка.
Петррр
 Аватар для Петррр
5914 / 3351 / 333
Регистрация: 28.10.2010
Сообщений: 5,926
29.10.2011, 19:46     Задача «Общая подпоследовательность» #29
Типа между элементами тоже могут быть элементы?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 19:48     Задача «Общая подпоследовательность» #30
Типа могут.
"Подпоследовательность можно получить из некоторой конечной последовательности, если удалить из последней некоторое множество её элементов (возможно пустое)."
Петррр
 Аватар для Петррр
5914 / 3351 / 333
Регистрация: 28.10.2010
Сообщений: 5,926
29.10.2011, 20:06     Задача «Общая подпоследовательность» #31
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <stdlib.h>
 
void read_array(FILE *file, int *arr, size_t count)
{
    int i;
    for(i = 0; i < count; i++)
        fscanf(file, "%d ", &arr[i]);
}
 
int find(int* arr, size_t size, int val)
{
    int i = 0;
    while (i != size && arr[i] != val)
        i++;
    return i;
}
 
void ghost(const char *filen_name_from, const char *file_name_to)
{
    int *arr1, *arr2, *arr3, *buffer;
    size_t arr1_size, arr2_size, arr3_size, buffer_size;
    size_t lst_length = 0, lst_pos = -1, i, lst_length_buffer;
    size_t fnd_arr2, fnd_arr3;
    
    FILE *file_from, *file_to;
    file_from = fopen(filen_name_from, "r");
    file_to = fopen(file_name_to, "w");
 
    /* Чтение первого массива */
    fscanf(file_from, "%d\n", &arr1_size);
    arr1 = (int*) malloc(sizeof(int) * arr1_size);
    read_array(file_from, arr1, arr1_size);
 
    /* Чтение второго массива  */
    fscanf(file_from, "\n%d\n", &arr2_size);
    arr2 = (int*) malloc(sizeof(int) * arr2_size);
    read_array(file_from, arr2, arr2_size);
 
    /* Чтение третьего массива */
    fscanf(file_from, "\n%d\n", &arr3_size);
    arr3 = (int*) malloc(sizeof(int) * arr3_size);
    read_array(file_from, arr3, arr3_size);
    /***************************/
 
    if (arr1_size > arr2_size)
    {
        buffer = arr2;
        arr2 = arr1;
        arr1 = buffer;
        buffer_size = arr2_size;
        arr2_size = arr1_size;
        arr1_size = buffer_size;
    }
    if (arr1_size > arr3_size)
    {
        buffer = arr3;
        arr3 = arr1;
        arr1 = buffer;
        buffer_size = arr3_size;
        arr3_size = arr1_size;
        arr1_size = buffer_size;
    }
 
    for(i = 0; i < arr1_size; i++)
    {
        fnd_arr2 = find(arr2, arr2_size, arr1[i]);
        fnd_arr3 = find(arr3, arr3_size, arr1[i]);
        lst_length_buffer = 0;
        if (fnd_arr2 != arr2_size && fnd_arr3 != arr3_size)
        {
            lst_length_buffer++;
            while (
                arr1[i + lst_length_buffer] == arr2[fnd_arr2 + lst_length_buffer] && 
                arr2[fnd_arr2 + lst_length_buffer] == arr3[fnd_arr3 + lst_length_buffer] &&
                (fnd_arr2 + lst_length_buffer) < arr2_size &&
                (fnd_arr3 + lst_length_buffer) < arr3_size)
                lst_length_buffer++;
            if (lst_length_buffer > lst_length)
            {
                lst_length = lst_length_buffer;
                lst_pos = i;
                i += lst_length;
            }
        }
    }
 
    for(i = 0; i < arr1_size; i++)
        printf("%d ", arr1[i]);
    printf("\n");
    for(i = 0; i < arr2_size; i++)
        printf("%d ", arr2[i]);
    printf("\n");
    for(i = 0; i < arr3_size; i++)
        printf("%d ", arr3[i]);
    printf("\n");
    /* Запись в файл длины последовательности */
    fprintf(file_to, "%d\n", lst_length);
    
    /* Если последовательность найдена, с указанного индекса записывается
       последовательность длиной lst_length с индекса lst_pos
      */
    if (lst_length > 0)
        for(i = lst_pos; i < lst_length; i++)
            fprintf(file_to, "%d ", arr1[i]);
 
    free(arr1);
    free(arr2);
    free(arr3);
    fclose(file_from);
    fclose(file_to);
}
 
int main(int argc, char **argv)
{
    const char *filen_name_from = "C:/input.txt";
    const char *file_name_to = "C:/output.txt";
    ghost(filen_name_from, file_name_to);
    system("pause");
    return EXIT_SUCCESS;
}
Код
3
1 3 3
4
2 1 3 3
6
0 1 3 3 1 2
Код
3
1 3 3
Сразу говорю нужно доработать.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
29.10.2011, 23:57     Задача «Общая подпоследовательность» #32
Интересно. Ты спрашиваешь, обязана ли быть подпоследовательность связной, получаешь отрицательный ответ, и тут же решаешь задачу, в которой подпоследовательность может быть только связной.
Попытка решить задачу самостоятельно, конечно, похвальна (чего, кстати, пока нельзя сказать об авторе темы), но городить огород не нужно, тем более, что я уже дал несколько полезных ссылок. Здесь применяется метод динамического программирования. Изучи уже, наконец, теорию. Не стесняйся, почитай учебники.
Includenv
Сообщений: n/a
30.10.2011, 00:35     Задача «Общая подпоследовательность» #33
Цитата Сообщение от volovzi Посмотреть сообщение
Интересно. Ты спрашиваешь, обязана ли быть подпоследовательность связной, получаешь отрицательный ответ, и тут же решаешь задачу, в которой подпоследовательность может быть только связной.
Попытка решить задачу самостоятельно, конечно, похвальна (чего, кстати, пока нельзя сказать об авторе темы), но городить огород не нужно, тем более, что я уже дал несколько полезных ссылок. Здесь применяется метод динамического программирования. Изучи уже, наконец, теорию. Не стесняйся, почитай учебники.
Автор не видит смысла выкладывать свои попытки. Есть алгоритм для двух последовательность, но опять же повторюсь, меня интересует для трех сразу. А не выполнять один и тот же алгоритм два раза.

Для двух - это тривиальная задача.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
30.10.2011, 01:03     Задача «Общая подпоследовательность» #34
Includenv, тривиальная — покажи.

Добавлено через 25 минут
Ладно.
Для затравки, вот функция для расчёта длины наибольшей подпоследовательности двух последовательностей (пока только длины, без самой последовательности).
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
#include <iostream>
#include <vector>
 
template <typename Value>
Value max (const Value & a, const Value & b, const Value & c)
{
    return std::max(std::max(a, b), c);
}
 
template <typename Sequence>
int largest_common_sequence (const Sequence & first, const Sequence & second)
{
    typedef std::vector<int> matrix_row_type;
    typedef std::vector<matrix_row_type> matrix_type;
    matrix_type matrix(first.size() + 1, matrix_row_type(second.size() + 1, 0));
    
    for (int i = 1; i <= first.size(); ++i)
    {
        for (int j = 1; j <= second.size(); ++j)
        {            
            matrix[i][j] = max
            (
                matrix[i - 1][j],
                matrix[i][j - 1],
                matrix[i - 1][j - 1] + static_cast<int>(first[i - 1] == second[j - 1])
            );
        }
    }
    
    return matrix.back().back();
}
 
int main ()
{    
    std::string s1, s2;
    std::cin >> s1 >> s2;
    
    std::cout << largest_common_sequence(s1, s2) << std::endl;
    
    return 0;
}
Попробуй сделать по аналогии случай с тремя последовательностями. Для начала тоже только расчёт длины без явного нахождения подпоследовательности.
Петррр
 Аватар для Петррр
5914 / 3351 / 333
Регистрация: 28.10.2010
Сообщений: 5,926
30.10.2011, 10:01     Задача «Общая подпоследовательность» #35
volovzi, а самому то слабо сделать. Понты колотишь только.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2011, 19:54     Задача «Общая подпоследовательность»
Еще ссылки по теме:

Наибольшая возрастающая подпоследовательность за O(NlogN) C++
Динамическое программирование: самая длинная строго возрастающая подпоследовательность C++
C++ Найти наибольшую возрастающую подпоследовательность в массиве

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

Или воспользуйтесь поиском по форуму:
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
30.10.2011, 19:54     Задача «Общая подпоследовательность» #36
Петррр, ну, ты пока что даже смысла задания не можешь понять, не говоря уже о том, чтобы реализовать простой случай с двумя строками. Так что это тебе слабо, а не мне.

Подсказка №2: в выложенной выше функции нужно добавить третий аргумент, увеличить размерность матрицы, добавить ещё один вложенный цикл и изменить вычисление максимума с трёх до... некоторого большего количества аргументов.

Добавлено через 3 часа 37 минут
Мда, вот так попытаешься помочь человеку, а он — обычный ленивый бездельник.
Да ещё и модератор нагадил по мелочи. Жаль потраченного времени.
Yandex
Объявления
30.10.2011, 19:54     Задача «Общая подпоследовательность»
Ответ Создать тему
Опции темы

Текущее время: 00:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru