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

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

Восстановить пароль Регистрация
 
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
26.11.2014, 07:17     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #1
Здравствуйте!!! У меня есть такое задание: дана последовательность целых чисел. Необходимо найти её самую длинную строго возрастающую подпоследовательность. Я знаю, что она должна решаться по аналогии с задачей о наибольшей общей подстроке, но как конкретно её решать не знаю. Подскажите хотя бы идею решения. За код буду отдельно очень признателен. Заранее спасибо!!!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2014, 07:17     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
Посмотрите здесь:

C++ Самая короткая и длинная фраза
Номер строки, в которой самая длинная серия одинаковых злементов C++
Найти номер строки, в которой находится самая длинная последовательность C++
динамическое программирование и длинная рафиметика(не получается прикрутить длинную арифметику). C++
Самая длинная последовательность не повторяющихся элементов в массиве C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Zedapp
 Аватар для Zedapp
29 / 29 / 12
Регистрация: 15.11.2014
Сообщений: 167
26.11.2014, 07:44     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #2
Цитата Сообщение от Boogerman Посмотреть сообщение
дана последовательность целых чисел. Необходимо найти её самую длинную строго возрастающую подпоследовательность.!
Подобная задачка есть в задачнике по алгоритмам мехмата МГУ и там есть условие, что нельзя использовать массивы. Уточните условие.

Можно ли использовать массивы? известен ли заранее размер последовательности?
Байт
 Аватар для Байт
13976 / 8807 / 1228
Регистрация: 24.12.2010
Сообщений: 15,959
26.11.2014, 09:44     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #3
Boogerman, необходимо уточнение, что считать за подпоследовательность. Должны ли ее элементы стоять рядом? Тогда это очень простая задача. Или имеется в виду подпоследовательность в математическом смысле? Тогда это несколько сложнее
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
26.11.2014, 09:53     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #4
Байт, не обязательно подряд должны идти элементы.
Boogerman
1 / 1 / 0
Регистрация: 22.09.2013
Сообщений: 22
27.11.2014, 11:23  [ТС]     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #5
Массивы использовать можно и элементы необязательно должны стоять подряд

Добавлено через 22 часа 34 минуты
Цитата Сообщение от Zedapp Посмотреть сообщение
известен ли заранее размер последовательности?
Размер произвольный, вводится с клавиатуры
Fallenworld
75 / 75 / 9
Регистрация: 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];
}
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
27.11.2014, 13:57     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #7
Fallenworld, последовательность такая например:

98, 99, 100, 1, 2, 3, ... , 97.
Байт
 Аватар для Байт
13976 / 8807 / 1228
Регистрация: 24.12.2010
Сообщений: 15,959
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;
}
Надеюсь на свежую голову эту штуку допилить, хотя прекрасно понимаю, что ни по эстетике программизма, ни по эффективности, это - не лучший вариант.

Не по теме:

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

Fallenworld
75 / 75 / 9
Регистрация: 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;
 
}
а так?
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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
Fallenworld
75 / 75 / 9
Регистрация: 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 подпос.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
02.12.2014, 10:21     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #12
Fallenworld, что значит 523 подпос?
Fallenworld
75 / 75 / 9
Регистрация: 14.04.2014
Сообщений: 408
02.12.2014, 10:23     Динамическое программирование: самая длинная строго возрастающая подпоследовательность #13
523 подпоследовательности, это от предидущего осталось, до оптимизации он выдавал 85тыс подпоследовательностей.
самая длинная 13 элементов.

П.С. если надо будут комментарии, для разъяснения кода, то напишу, а то мне лень было читабельный писать)
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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 выводит.
Fallenworld
75 / 75 / 9
Регистрация: 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 выводит.
ага, я понял, почему, но исправлять уже не буду.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2014, 09:04     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
Еще ссылки по теме:

Сформировать строки таким образов, что бы первой была самая короткая строка, а последней самая длинная C++
Строго возрастающая макс. подпоследовательность C++
Наибольшая возрастающая подпоследовательность за O(NlogN) C++

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

Или воспользуйтесь поиском по форуму:
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;
}
Yandex
Объявления
04.12.2014, 09:04     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
Ответ Создать тему
Опции темы

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