Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
#1

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

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

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

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


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


Вход-выход - ерунда)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 11:31
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины (C++):

Выделить подпоследовательность, начиная с минимального элемента и до конца последовательности - C++
вот код программы : #include <iostream> using namespace std; int* entseq(int); int searchmin(int*); int output(int*,int); ...

В заданной последовательности найти подпоследовательность согласно условию, а в ней - минимальное значение - C++

Значение минимального положительного члена числовой последовательности заданной соотношением - C++
Используя оператор цикла, составить программу, в которой находится значение минимального положительного члена числовой последовательности...

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

В заданной последовательности чисел найти убывающую последовательность максимальной длины - C++
Даны N целых чисел. В заданной последовательности чисел найти убывающую последовательность максимальной длины. Формат входных данных Во...

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

4
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 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
TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
16.01.2011, 13:29  [ТС] #3
valeriikozlov, спасибо большое!
Сейчас буду разбираться)
0
TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
25.01.2011, 10:06  [ТС] #4
Код работает не верно.

Например

1 4 2 1 3

Добавлено через 1 час 13 минут
В строчке №25 должно быть < вместо <=
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 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
25.01.2011, 10:58
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2011, 10:58
Привет! Вот еще темы с ответами:

Найти все варианты возможной замены проводов с заданной точностью подбора - C++
Проверить код и указать ошибки Доброго всем времени суток!Пожалуйста,кому не трудно.посмотрите мой код и подскажите,что я не так или...

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

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

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


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

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

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