Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
1

Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины

16.01.2011, 11:31. Показов 2367. Ответов 4
Метки нет (Все метки)

Привет вам, умный народ!
Вынужден обратиться к вам за помощью, ибо прижало!

Проблема у меня с динамическим программированием, а большинству из вас это плевое дело)


Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины. Если таких несколько, то из них нужно выбрать ту, у которой наибольшая сумма чисел.


Вход-выход - ерунда)
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.01.2011, 11:31
Ответы с готовыми решениями:

Найти самую длинную неубывающую подпоследовательность данной последовательности (с использованием списков)
Дана последовательность вещественных чисел a1,a2,...,an. Указать самую длинную неубывающую...

Найти самую длинную неубывающую подпоследовательность данной последовательности (с использованием списков)
Дана последовательность вещественных чисел a1,a2,...,an. Указать самую длинную неубывающую...

Найти самую длинную неубывающую подпоследовательность данной последовательности с использованием списков
Дана последовательность вещественных чисел a1,a2,...,an. Указать самую длинную неубывающую...

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

4
Эксперт С++
4710 / 2535 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 12:28 2
проверяйте:
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 <stdio.h>
 
int main()
{
    int **mas, N, i, j;
    printf("N= ");
    scanf("%d", &N);
    mas=new int*[3];
    for(i=0; i<3; i++)
        mas[i]=new int[N];
    for(i=0; i<N; i++)
        {
            printf("[%d]= ", i);
            scanf("%d", &mas[0][i]);
        }
    mas[1][N-1]=1; mas[2][N-1]=mas[0][N-1];
    for(i=N-2; i>=0; i--)
    {
        mas[1][i]=1; mas[2][i]=mas[0][i];
        for(j=i+1; j<N; j++)
            if(mas[0][i]<=mas[0][j] && mas[1][i]<=mas[1][j]+1)
            {
                if(mas[1][i]==mas[1][j]+1 && mas[2][i]<mas[2][j])
                    mas[2][i]=mas[2][j]+mas[0][i];
                if(mas[1][i]<=mas[1][j]+1)
                {
                    mas[2][i]=mas[2][j]+mas[0][i];
                    mas[1][i]=mas[1][j]+1;
                }
            }
    }
    int i_max=0;
    for(i=1; i<N; i++)
    {
        if(mas[1][i]==mas[1][i_max] && mas[2][i]>mas[2][i_max])
            i_max=i;
        if(mas[1][i]>mas[1][i_max])
            i_max=i;
    }
    int col=mas[1][i_max];
    while(col>0)
    {
        printf("%d ", mas[0][i_max]);
        for(i=i_max+1; i<N; i++)
            if(mas[0][i]>=mas[0][i_max] && mas[1][i]+1==mas[1][i_max] && mas[2][i_max]-mas[0][i_max]==mas[2][i])
            {
                i_max=i;
                break;
            }
            col--;      
    }   
    return 0;
}
1
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
16.01.2011, 13:29  [ТС] 3
valeriikozlov, спасибо большое!
Сейчас буду разбираться)
0
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
25.01.2011, 10:06  [ТС] 4
Код работает не верно.

Например

1 4 2 1 3

Добавлено через 1 час 13 минут
В строчке №25 должно быть < вместо <=
0
Эксперт С++
4710 / 2535 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 10:58 5
TonyKing,
Цитата Сообщение от TonyKing Посмотреть сообщение
В строчке №25 должно быть < вместо <=
Да правильно, и еще строку 23 заменить на:
C
1
                             if(mas[1][i]==mas[1][j]+1 && mas[2][i]<mas[2][j]+mas[0][i])
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
25.01.2011, 10:58

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

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

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

Выделить в массиве возрастающую подпоследовательность наибольшей длины
Задан массив размера N. Выделить возрастающую подпоследовательность элементов наибольшей длины.

Выделить знакопостоянную подпоследовательность наибольшей длины и упорядочить ее по убыванию
Дана последовательность a1,...,an (n&lt;=100) действительных чисел. выделить из нее знакопостоянную...


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

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

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