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

Строго возрастающая макс. подпоследовательность - C++

Восстановить пароль Регистрация
 
HenryDukart
 Аватар для HenryDukart
100 / 100 / 28
Регистрация: 05.10.2013
Сообщений: 400
Завершенные тесты: 2
05.10.2013, 18:50     Строго возрастающая макс. подпоследовательность #1
Долго ломал голову над задачей. Наконец-то нашел код (он правда, на паскале). Переделал, все хорошо. Но вот не задача: никак не могу добиться, чтобы программа все-таки правильно вывела эту подпоследовательность. Прошу помощи . (Кажется, что код большой. на самом деле там много оформления)
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
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
    setlocale(LC_ALL, "Russian");
    const int nummax(20);
    double mass1[nummax],mass2[nummax], t, p(1);
    int n, k, nmax(0), nmin(0);
    cout<<"Введите количество элементов массива (от 1 до 20)."<<endl;
    cin>>n;
    while ((n>nummax)||(n<=0))
    {
        cout<<"Число выходит за границы дозволенного. Введите другое число."<<endl;
        int n1;
        cin>>n1;
        n=n1;
    }
    char otvet='a';
    do
    {
        cout<<"Желаете ли вы использовать для ввода массива генератор случайных чисел? (y/n)\n";
        cin>>otvet;
        if ((otvet!='y')&&(otvet!='n'))
            cout<<"Ошибка! Ответ неверный. Повторите ввод.\n";
    }
    while ((otvet!='y')&&(otvet!='n'));
    if (otvet=='y')
    {
        cout<<"Введите границы чисел, которые выдаст генератор."<<endl;
        int a, b;
        cin>>a>>b;
        srand(time(NULL));
        for (int i=0; i<n; i++)
        {
            mass1[i]=(double)(rand())/RAND_MAX*(b-a)+a;
            mass2[i]=mass1[i];
        }
    }
    else
    {
        cout<<"Введите "<<n<<" чисел."<<endl;
        for (int i=0; i<n; i++)
        {
            cin>>mass1[i];
            mass2[i]=mass1[i];
        }
    }
    for (int i=0; i<n; i++)
        cout<<i<<") "<<mass1[i]<<endl;
    cout<<endl;
 
//1)
    int dl[nummax], pre[nummax];
    for (int i=0; i<n; i++)
    {
        dl[i]=1;
        pre[i]=-1;
    }
    for (int i=0; i<n-1; i++)
        for (int j=i+1; j<n; j++)
            if (mass1[j]>mass1[i])
                if (dl[i]+1>dl[j])
                {
                    dl[j]=dl[i]+1;
                    pre[j]=i;
                }
    int maxl(0);
    for (int i=0; i<n; i++)
        if (dl[maxl]<=dl[i])
            maxl=i;
    cout<<"Максимальная длина возрастаюзей подпоследовательности равна "<<dl[maxl]<<":"<<endl;
    return 0;
}
Код на Паскале взят с http://informatics.mccme.ru/moodle/m...iew.php?id=488 (способ 3).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2013, 18:50     Строго возрастающая макс. подпоследовательность
Посмотрите здесь:

на подпоследовательность C++
C++ массив и возрастающая последовательность
возрастающая последовательность C++
Возрастающая последовательность C++
Возрастающая последовательность C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TrueBit
 Аватар для TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
05.10.2013, 20:25     Строго возрастающая макс. подпоследовательность #2
Переведенный на c++, код паскаля(нумерацию не стал изменять).
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
#include <iostream>
using namespace std;
#ifdef _DEBUG
void MyDebugPrint(char * message,int * pointer, int size) {
    printf("%s: ",message);
    for(int i=1; i<size; i++)
        printf("%d ",pointer[i]);
    printf("\n");
}
#endif
int main() {
    setlocale(LC_ALL, "rus");
    int n=5;
    int a[] = { 0,1,6,2,3,5 }; // Продемонстрируем работу алгоритма для последовательности 1,6,2,3,5.
    int length[] = { 0,1,1,1,1,1 };      //Изначально length[i]=1 для всех i
    int predecessor[] = { 0,0,0,0,0,0 }; //predecessor[i]=0.
    for(int i = 1; i<=(n-1); i++) {              //for i := 1 to n-1 do
        for(int j=i+1; j<=n; j++) {              //for j := i+1 to n do
            if(a[j] > a[i])                      //if a[j] > a[i] then
                if(length[i] + 1 > length[j]) {  //if length[i] + 1 > length[j] then begin
                    length[j] = length[i] + 1;   //length[j] = length[i] + 1;
                    predecessor[j] = i;          //predecessor[j] = i; //предшественник a[j] в цепочке
                } //end;
        }
        #ifdef _DEBUG
        MyDebugPrint("length",length,sizeof(length)/sizeof(int));
        MyDebugPrint("predecessor",predecessor,sizeof(predecessor)/sizeof(int));
        #endif
    }
    getchar();
}
HenryDukart
 Аватар для HenryDukart
100 / 100 / 28
Регистрация: 05.10.2013
Сообщений: 400
Завершенные тесты: 2
05.10.2013, 20:48  [ТС]     Строго возрастающая макс. подпоследовательность #3
Спасибо. Но 1 курс еще не знает #ifdef _DEBUG. Можно ли без него как-нибудь?
TrueBit
 Аватар для TrueBit
95 / 95 / 12
Регистрация: 19.11.2012
Сообщений: 195
05.10.2013, 20:56     Строго возрастающая макс. подпоследовательность #4
Цитата Сообщение от HenryDukart Посмотреть сообщение
Спасибо. Но 1 курс еще не знает #ifdef _DEBUG. Можно ли без него как-нибудь?
Просто уберите строки #ifdef _DEBUG и #endif. Работает и без них.
HenryDukart
 Аватар для HenryDukart
100 / 100 / 28
Регистрация: 05.10.2013
Сообщений: 400
Завершенные тесты: 2
05.10.2013, 21:13  [ТС]     Строго возрастающая макс. подпоследовательность #5
Вы не поняли задачу. Мне нужно вывести не массивы, содержащие длинну подпоследовательности и стартовые элементы, а саму подпоследовательнось.
IrineK
Заблокирован
05.10.2013, 23:35     Строго возрастающая макс. подпоследовательность #6
Вообще-то подпоследовательностей найденной максимальной длины может быть несколько. Код ниже учитывает и эту возможность:

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
//найти максимальную строго возрастающую подпоследовательность 
 
#include <iostream>
#include <ctime>
using namespace std;
 
const int N = 20;
 
int main()
{   int A[N], post [N-1];
    int i, max = 0, maxPos = 0;
    srand((unsigned int) time(NULL));
 
    //задаем массив 
    cout<<"Initial sequence:\n";
    for(i=0; i<N; i++)
    {   A[i] = rand()%10;
        cout<<A[i]<<"  ";
    }
 
    //строим вспомогательный массив 
    for(i=0; i<N-1; i++)
        if(A[i]<A[i+1])
            post[i] = 1;
        else
            post[i] = 0;
 
    for(i = N-2; i>0; i--)
        if(post[i] && post[i-1])
        {   post[i-1] += post[i];
            post[i] = 0;
        }
    
    //находим максимальную длину
    for(i=0; i<N-1; i++)
        if(post[i]>max)
            max = post[i];
 
    //выводим все строго возрастающие подпоследовательности найденной максимальной длины
    cout<<"\n\nAll maximum strictly increasing subsequences, length = "<<max+1<<"\n";
    for(i=0; i<N-1; i++)
        if(post[i] == max)
        {   cout<<"\n\tStart at position "<<i<<"\n\t";
            maxPos = max+1;
            while(maxPos--)
                cout<<A[i++]<<"  ";
            i--;
            cout<<"\n";
        }
 
    cin.get();
    return 0;
}
Миниатюры
Строго возрастающая макс. подпоследовательность   Строго возрастающая макс. подпоследовательность  
HenryDukart
 Аватар для HenryDukart
100 / 100 / 28
Регистрация: 05.10.2013
Сообщений: 400
Завершенные тесты: 2
06.10.2013, 01:32  [ТС]     Строго возрастающая макс. подпоследовательность #7
Спасибо. Но ваша программа не находит подпоследовательность максимальной длинны. Для скриншота максимальная подпоследовтельность = 2, 3, 5, 6, 7. В ней 5 элементов.
IrineK
Заблокирован
07.10.2013, 03:50     Строго возрастающая макс. подпоследовательность #8
Простите, но где?
HenryDukart
 Аватар для HenryDukart
100 / 100 / 28
Регистрация: 05.10.2013
Сообщений: 400
Завершенные тесты: 2
07.10.2013, 14:59  [ТС]     Строго возрастающая макс. подпоследовательность #9
Цитата Сообщение от IrineK Посмотреть сообщение
Простите, но где?
На первом прикрепленном скриншоте. Для этой последовательности максимальной подпоследовательностью является 2, 3, 5, 6, 7, вкоторой 5 элементов, больше, чем смогла найти программа.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2013, 04:22     Строго возрастающая макс. подпоследовательность
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
IrineK
Заблокирован
16.10.2013, 04:22     Строго возрастающая макс. подпоследовательность #10
На первом скриншоте НЕТ подряд идущих 2, 3, 5, 6, 7.
ПО условию ищем подпоследовательность идущих подряд элементов.
Yandex
Объявления
16.10.2013, 04:22     Строго возрастающая макс. подпоследовательность
Ответ Создать тему
Опции темы

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