Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
#1

Динамическое программирование: самая длинная строго возрастающая подпоследовательность - C++

26.11.2014, 07:17. Просмотров 1227. Ответов 15
Метки нет (Все метки)

Здравствуйте!!! У меня есть такое задание: дана последовательность целых чисел. Необходимо найти её самую длинную строго возрастающую подпоследовательность. Я знаю, что она должна решаться по аналогии с задачей о наибольшей общей подстроке, но как конкретно её решать не знаю. Подскажите хотя бы идею решения. За код буду отдельно очень признателен. Заранее спасибо!!!
http://www.cyberforum.ru/cpp-beginners/thread969685.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2014, 07:17
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Динамическое программирование: самая длинная строго возрастающая подпоследовательность (C++):

Динамическое программирование. Требуется идея для решения. Общая подпоследовательность
Заданы две строки длиной не больше 10000. Нужно найти самую хорошую...

динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику).
#include <stdio.h> int rekursia(int K,int N); int main() { int K,N;...

Сформировать строки таким образов, что бы первой была самая короткая строка, а последней самая длинная
задан строка. сформировать строки таким образов что бы первой была самая...

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

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

15
Zedapp
44 / 30 / 18
Регистрация: 15.11.2014
Сообщений: 169
26.11.2014, 07:44 #2
Цитата Сообщение от Boogerman Посмотреть сообщение
дана последовательность целых чисел. Необходимо найти её самую длинную строго возрастающую подпоследовательность.!
Подобная задачка есть в задачнике по алгоритмам мехмата МГУ и там есть условие, что нельзя использовать массивы. Уточните условие.

Можно ли использовать массивы? известен ли заранее размер последовательности?
0
Байт
Эксперт C
17764 / 11789 / 2449
Регистрация: 24.12.2010
Сообщений: 23,710
26.11.2014, 09:44 #3
Boogerman, необходимо уточнение, что считать за подпоследовательность. Должны ли ее элементы стоять рядом? Тогда это очень простая задача. Или имеется в виду подпоследовательность в математическом смысле? Тогда это несколько сложнее
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
26.11.2014, 09:53 #4
Байт, не обязательно подряд должны идти элементы.
0
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
27.11.2014, 11:23  [ТС] #5
Массивы использовать можно и элементы необязательно должны стоять подряд

Добавлено через 22 часа 34 минуты
Цитата Сообщение от Zedapp Посмотреть сообщение
известен ли заранее размер последовательности?
Размер произвольный, вводится с клавиатуры
0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
27.11.2014, 12:20 #6
C++
1
2
3
4
5
6
7
8
int temp = N[0];
vector<int> podposl;
for(int i=1; i<length; ++i){
  if(temp<N[i]){
 podposl.push_back(N[i]);
temp=N[i];
}
}
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
27.11.2014, 13:57 #7
Fallenworld, последовательность такая например:

98, 99, 100, 1, 2, 3, ... , 97.
0
Байт
Эксперт C
17764 / 11789 / 2449
Регистрация: 24.12.2010
Сообщений: 23,710
28.11.2014, 00:07 #8
Цитата Сообщение от Байт Посмотреть сообщение
Тогда это несколько сложнее
Вот, попытался решить... То работает, то нет (значит - не работает!) Тем не менее показываю код (неправильный!), если для кого-то это актуально, может быть попробует найти мою ошибку. Код находит правильные последовательности, если они начинаются с первого члена. Идея довольно проста. Создаешь приемлемую (возрастающую) последовательность, а потом двигаешь ее элементы в надежде найти лучшую. Так вот, первый элемент у меня двигаться не хочет!
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
#include <stdio.h>
#include <stdlib.h>
#define N 12
 
int main()
{ int i, a[N], nn[N], b[N], Mn, Mx, old;
 
 randomize();
 for(i=0; i<N; i++) {
   a[i] = rand()%N;
   printf("%d ", a[i]);
 }
 printf("\n");
 b[0] = nn[0] = 0;  //  Начальное заполнение
 for(i=0, Mx=1; i<N; i++) if (a[i] > a[nn[Mx-1]]) b[Mx] = nn[Mx++] = i;
 Mn = Mx;  // Mn - Длина текущей последовательности в nn,
           // Mx - Длина лучшей последовательности в b
           // в массивах nn, b храню не сами элементы, а их номера
 while (1) {
       //  for(i=0; i<Mn; i++) printf("%d ", nn[i]); printf("\n");
       //  for(i=0; i<Mn; i++) printf("%d ", a[nn[i]]);
       //  printf(" Mn=%d Mx=%d nn0=%d\n", Mn, Mx, nn[0]);
   if (nn[0] >= N-1) break;  // Дальше некуда
   if (Mn<=2) {
     nn[0]++;
     Mn = 1;
   }
   else Mn -= 1;
   old = Mn;
   for(i=nn[Mn]+1; i<N; i++) if (a[i] > a[nn[Mn-1]]) nn[Mn++] = i;
   if (Mn==old) {  // Ничего нового
     Mn--;
     continue;
   }
   if (Mn > Mx) {  // Нашли лучшую
     Mx = Mn;
     for(i=0; i<Mx; i++) b[i] = nn[i];  // Фиксируем ее
   }
 }
 for(i=0; i<Mx; i++) printf("%d ", a[b[i]]);
 printf("\nMx=%d\n", Mx);
 return 0;
}
Надеюсь на свежую голову эту штуку допилить, хотя прекрасно понимаю, что ни по эстетике программизма, ни по эффективности, это - не лучший вариант.

Не по теме:

Там была дырка глупая (как и все дырки) и вот она съела у меня всю энергию...

0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
29.11.2014, 13:30 #9
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Fallenworld, последовательность такая например:
98, 99, 100, 1, 2, 3, ... , 97.
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
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
 
using namespace std;
int main(){
int N[11]{97,98,99,95,96,34,35,36,37,38,100};
 
 
vector<vector<int> > podposlovatelnosti(1);
(podposlovatelnosti.back()).push_back(N[0]);
bool newPodposl(true);
for(int i=1; i<11; ++i){
 
    for(int j=0; j < podposlovatelnosti.size(); ++j)
        if(N[i]>podposlovatelnosti[j].back()){
                podposlovatelnosti[j].push_back(N[i]);
                newPodposl  = false;
                }
    if(newPodposl) podposlovatelnosti.push_back(vector<int>{N[i]});
    newPodposl = true;
 
 
}
int max(0), num(0);
for(int i=0; i<podposlovatelnosti.size(); ++i)
    if(max<podposlovatelnosti[i].size()){
        max = podposlovatelnosti[i].size();
        num = i;
        }
for(int i=0; i<podposlovatelnosti[num].size(); ++i) cout<<(podposlovatelnosti[num])[i]<<"  ";
return 0;
 
}
а так?
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
29.11.2014, 21:05 #10
Fallenworld,
10
1 9 8 10 2 3 4 6 5 7

ответ == 6


50
12 24 42 43 36 3 40 29 7 34 10 13 28 9 35 23 25 21 19 4 20 18 11 38 41 48 6 46 33 17 31 37 2 30 32 44 45 5 47 49 16 15 50 27 26 14 39 22 1 8

ответ == 13
0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
02.12.2014, 10:19 #11
SlavaSSU, да, не учел, что куски последовательностей могут быть общими.

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
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
 
using namespace std;
template<typename T>
bool find_podposled(const T& arg, vector< vector<T> > &posled){
    bool newPodposl(false);
    for(unsigned int j=0; j < posled.size(); ++j) //есть ли подпос-ть для arg?
        if(arg>(posled[j]).back()){
            (posled[j]).push_back(arg);
            newPodposl  = true;
        }
    return newPodposl;
}
 
 
int main(){
 
    const int n=50;
    int N[n]{12, 24, 42, 43, 36, 3, 40, 29, 7, 34, 10, 13, 28, 9,
        35, 23, 25, 21, 19, 4, 20, 18, 11, 38, 41, 48, 6, 46, 33,
        17, 31, 37, 2, 30, 32, 44, 45, 5, 47, 49, 16, 15, 50, 27, 26, 14, 39, 22, 1, 8};
 
 
 
 
    vector<vector<int> > podposlovatelnosti(1);
    (podposlovatelnosti.back()).push_back(N[0]);
 
    for(int i=1; i<n; ++i){
 
        if(!find_podposled(N[i],podposlovatelnosti)){
            //надо делать новую. Найдем самую длинную из новых
            //хотя нет, создадим все варианты
            vector<int> podposl;
            bool newpodposl(false);
            unsigned int size = podposlovatelnosti.size();
            for(unsigned int j=0, k=0; j < size; ++j,k=0){
 
                while((podposlovatelnosti[j])[k] < N[i])
                    podposl.push_back((podposlovatelnosti[j])[k++]);
 
                if(podposl.size()) {
                    podposl.push_back(N[i]);
                    //if(podposl!=podposlovatelnosti.back()){
                    if(podposlovatelnosti.size()>size){
                        k=size;
                        while(k<podposlovatelnosti.size()){
                            if(podposlovatelnosti[k]==podposl){
                                podposl.clear();
                                break;
                            }
 
                            ++k;
                        }
                         if(!podposl.size()) continue;
                    }
                    podposlovatelnosti.push_back(podposl);
                    newpodposl = true;
                    podposl.clear();
                }
 
            }
            if(!newpodposl){
                podposl.push_back(N[i]);
                podposlovatelnosti.push_back(podposl);
            }
        }
    }
 
    unsigned int max(0), num(0);
    for(unsigned int i=0; i<podposlovatelnosti.size(); ++i)
        if(max<podposlovatelnosti[i].size()){
            max = podposlovatelnosti[i].size();
            num = i;
        }
    for(unsigned int i=0; i<podposlovatelnosti[num].size(); ++i) cout<<(podposlovatelnosti[num])[i]<<"  ";
    return 0;
 
}
523 подпос.
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
02.12.2014, 10:21 #12
Fallenworld, что значит 523 подпос?
0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
02.12.2014, 10:23 #13
523 подпоследовательности, это от предидущего осталось, до оптимизации он выдавал 85тыс подпоследовательностей.
самая длинная 13 элементов.

П.С. если надо будут комментарии, для разъяснения кода, то напишу, а то мне лень было читабельный писать)
0
SlavaSSU
217 / 162 / 47
Регистрация: 17.07.2012
Сообщений: 587
02.12.2014, 10:52 #14
C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
const int N = 1000;
 
int a[N];
int dp[N];
int n;
 
int main(){
 
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i], dp[i] = 1;
 
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
            if(a[j] > a[i])
                dp[j] = max(dp[j], dp[i] + 1);
    }
 
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
 
    cout << ans << endl;
 
    return 0;
}
Добавлено через 19 минут
Fallenworld,

50
411 915 930 547 328 51 446 45 281 631 703 953 129 188 689 386 901 129 317 156 42 339 255 2 541 0 937 584 657 205 423 58 924 687 409 723 586 430 772 246 961 518 65 705 451 413 893 533 376 471


ответ == 12.

у тебя 11 выводит.
0
Fallenworld
76 / 76 / 32
Регистрация: 14.04.2014
Сообщений: 408
03.12.2014, 11:28 #15
Цитата Сообщение от SlavaSSU Посмотреть сообщение
for(int j = i + 1; j < n; j++)
* * * * * * if(a[j] > a[i])
* * * * * * * * dp[j] = max(dp[j], dp[i] + 1);
что ж я не допер в обратном порядке проверить(

Добавлено через 30 секунд
Цитата Сообщение от SlavaSSU Посмотреть сообщение
у тебя 11 выводит.
ага, я понял, почему, но исправлять уже не буду.
0
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
04.12.2014, 09:04  [ТС] #16
Спасибо всем за обсуждения!!! Но вот до чего сам додумался, не без помощи инета, конечно
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
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <vector>
#include <Windows.h>
#include <iostream>
 
#define N 100
 
using namespace std;
using namespace System;
 
int main(array<System::String ^> ^args)
{
    int len;
    Console::WriteLine(L"Введите размер исходной последовательности:");
    scanf("%d",&len);
    int posl[N];
    vector<int> podposl;
    Console::WriteLine(L"Введите элементы последовательности:");
    for(int i=0;i<len;i++)
        scanf("%d",&posl[i]);
    system("cls");
    Console::WriteLine(L"Исходная числовая последовательность:");
    for(int i=0;i<len;i++)
        printf("%d ",posl[i]);
    printf("\n");
    int d[N],p[N];
    for(int i=0;i<len;++i)
    {
        d[i]=0; p[i]=-1;
        for(int j=0;j<i;++j)
            if(posl[j]<posl[i])
                if(1+d[j]>d[i])
                {
                    d[i]=1+d[j];
                    p[i]=j;
                }
    }
    int ans=d[0], pos=0;
    for(int i=0;i<len;++i)
        if(d[i]>ans)
        {
            ans=d[i];
            pos=i;
        }
    //printf("%d\n",ans);
    while(pos!=-1)
    {
        podposl.push_back(pos);
        pos=p[pos];
    }
    reverse(podposl.begin(),podposl.end());
    /*for(int i=0;i<(int)podposl.size();++i)
        printf("%d ",podposl[i]);
    printf("\n\n");*/
    for(int i=0;i<(int)podposl.size();++i)
        printf("%d ",posl[podposl[i]]);
    printf("\n");
    system("pause");
    return 0;
}
0
04.12.2014, 09:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2014, 09:04
Привет! Вот еще темы с решениями:

Самая длинная общая подпоследовательность строк/ НОП строк (Динамическое программирование)
Доброго времени суток. Помогите пожалуйста разобраться с алгоритмом НОП строк....

Самая длинная последовательность
Вводится последовательность цифр, 0 – конец ввода. Определить самый длинный ряд...

Самая короткая и длинная фраза
Задача такая. Есть текстовый файл test1.txt,содержащий последовательность фраз...

Самая длинная последовательность не повторяющихся элементов в массиве
Помогите!! нужно написать программу,которая выводит на экран самую длинную...


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

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

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