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

Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) - C++

Восстановить пароль Регистрация
 
SokolovVolody
0 / 0 / 0
Регистрация: 30.08.2015
Сообщений: 11
26.02.2016, 16:45     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #1
Написать программу, которая использует метод динамического программирования. Даны N
целых чисел X1,X2, . . . ,XN (1 <= N <= 10000, 1 <= Xi <= 60000). Требуется вычеркнуть из них
минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
Пример.
Ввод: 2 5 3 4 6 1
Вывод: 2 3 4 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
#include "stdafx.h"
#include <locale>
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
 
using namespace std;
 
int main()
{
    //const int c = 6;
    int a[6] = { 2, 5, 3, 4, 6, 1, };
    int b[10];
    int k = 0;
    memset(b, 0, sizeof(b)); //обнуление массива
 
    for (int i = 0; i < 6; i++)
    {
        printf(" a[%d]: %d\n", i + 1, a[i]);
        //scanf_s("%d", &a[i]);
    }
    for (int i = 0; i < 6; i++)
    if (a[i + 1] - a[i]>0)
    {
        b[k] = a[i];
        k++;
    }
    else
    {
        b[k] = a[i + 1];
        k++;
        i++;
    }
    printf("\n");
    for (int k = 0; k < 6; k++)
    {
        printf(" b[%d]: %d\n", k + 1, b[k]);
    }
    system("pause");
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.02.2016, 16:45     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование)
Посмотрите здесь:

Требуется вычеркнуть минимально возможное количество чисел так, чтобы оставшиеся числа шли в порядке возрастания C++
Вывести массив так, чтобы элементы стояли в порядке возрастания C++
C++ Из массива удалить минимальное число элементов так, чтобы оставшиеся шли по возрастанию
Переписать компоненты файла f в файл g так, чтобы в файле g числа шли в следующем порядке: C++
Переписать компоненты файла f в файл g так, чтобы в файле g числа шли в следующем порядке: C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
26.02.2016, 17:37     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #2
SokolovVolody, Создаешь двухмерный массив для длин последовательностей (реально нужен только треугольник над главной диагональю). Начинаешь его заполнять:
На главной диагонали - единицы (последовательность из одного элемента - удовлетворяет требованию).
Далее идем от главной диагонали вверх. Если первое число (arr[номер строки]) больше второго(от номера столбца) то на этом месте 0 (1-й больше последнего).
Иначе анализируем столбец снизу вверх и строку слева направо. Нам здесь нужна максимальная сумма из соответствующих элементов при этом оба ненулевые. запоминаем в матрице max+1.
Так доходим до правого верхнего угла.
Искомая посл-ть соответствует максимальному элементу матрицы.
Восстанавливаем ее.
Все.

Добавлено через 5 минут
Наврал. не max+1 а max.
SokolovVolody
0 / 0 / 0
Регистрация: 30.08.2015
Сообщений: 11
26.02.2016, 17:57  [ТС]     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #3
avgoor, Спасибо за ответ, а что за диагональ?и треугольник?Я так понимаю массив не прямоугольник, у него уменьшается длина строк(столбцов).
Выглядит примерно так?:
111111111
11111111
1111111
111111
11111
1111
111
11
1
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
26.02.2016, 20:37     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #4
SokolovVolody,
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
int main()
{
 
    int globIndex = 0, globMax = 1;
    std::vector<int> in = { 2, 5, 3, 4, 6, 1 };
 
    if (in.size() < 2) return 1;
 
    std::vector<std::vector<int>> m(in.size() - 1);
    for (int i = 0; i < m.size(); i++)
        m[i].resize(m.size() - i);
 
    for (int i = 0; i < m.size(); i++)
        for (int j = 0; j < m.size() - i; j++) {
            if (in[j] > in[i + j + 1]) {
                m[j][i] = 0;
            }
            else {
                int max = 2;
                for (int k = 0; k < i; k++) {
                    int row = m[j][k];
                    int col = m[j + k + 1][i - k - 1];
                    if (col && row && max < col + row)
                        max = col + row - 1;
                }
                m[j][i] = max;
                if (globMax < max) {
                    globMax = max;
                    globIndex = j;
                }
            }
        }
 
    std::vector<int> result(globMax);
    auto mpos = m[globIndex].rbegin();
    for (int seq = globMax; seq > 1; seq--) {
        mpos = std::find(mpos, m[globIndex].rend(), seq);
        result[seq - 1] = *(in.rbegin() + std::distance(m[globIndex].rbegin(), mpos));
    }
    result[0] = in[globIndex];
 
    std::copy(result.begin(), result.end(), std::ostream_iterator<int>(std::cout, " "));
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2796 / 1572 / 246
Регистрация: 03.05.2010
Сообщений: 3,649
27.02.2016, 07:58     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #5
Вариант без двумерного массива:
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//Написать программу, которая использует метод динамического программирования. Даны N
//целых чисел X1,X2, . . . ,XN (1 <= N <= 10000, 1 <= Xi <= 60000). Требуется вычеркнуть
//из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
//Пример.
//Ввод: 2 5 3 4 6 1
//Вывод: 2 3 4 6
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <iterator>
///////////////////////////////////////////////////////////////////////////////
typedef std::deque  < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
template< typename  TT_cont >
void    print_cont( TT_cont     const   &   cont )
{
    std::copy
        (
            cont.begin                                              (),
            cont.end                                                (),
            std::ostream_iterator< typename TT_cont::value_type >   ( std::cout, "\t" )
        );
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
void    set_longest_increasing_subsequence
    (
        T_numbers   const   &   numbers,
        T_numbers           &   subsequence
    )
{
    int         numbers_size    =   numbers.size();
    T_numbers   seq_lens            ( numbers_size, 1 );
    T_numbers   prev_indexes        ( numbers_size );
    int         seq_len_max         {1};
    int         last_ind            {};
 
    for( int  i{1}; i < numbers_size; ++i )
    {
        for( int  j{}; j < i; ++j )
        {
            if  (
                            numbers[j]
                        <   numbers[i]
 
                    &&      seq_lens[j] + 1
                        >   seq_lens[i]
                )
            {
                seq_lens        [i]     =   seq_lens[j] + 1;
                prev_indexes    [i]     =   j;
 
                if  (
                            seq_lens[i]
                        >   seq_len_max
                    )
                {
                    seq_len_max     =   seq_lens[i];
                    last_ind        =   i;
                }
            }//if
        }//for j
    }//for i
 
    while   (
                    int(    subsequence.size()  )
                <   seq_len_max
            )
    {
        subsequence.push_front
            (
                numbers[ last_ind ]
            );
 
        last_ind   =   prev_indexes[ last_ind ];
    }
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        int         num_size    =   rand() % 10 + 1;
        T_numbers   numbers;
 
        for( int  i = 0; i < num_size; ++i )
        {
            numbers.push_back( rand() % 10 + 1 );
        }
 
        print_cont  ( numbers );
        T_numbers   subsequence;
 
        set_longest_increasing_subsequence
            (
                numbers,
                subsequence
            );
 
        print_cont( subsequence );
        system("pause");
    }//for
}
MrKaban4ik
0 / 0 / 0
Регистрация: 29.02.2016
Сообщений: 3
29.02.2016, 14:56     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #6
avgoor, а разве динамическое программирование не подразумевает использование динамического массива массива?Я новичок ,может что то не так понял, можешь объяснить детальней или хотя бы код с комментариями написать.
Заранее спасибо.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
29.02.2016, 15:05     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #7
MrKaban4ik, Динамическое программирование подразумевает сведение большой задачи к множеству мелких. Как это достигается - не важно.
MrKaban4ik
0 / 0 / 0
Регистрация: 29.02.2016
Сообщений: 3
29.02.2016, 15:16     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #8
avgoor, спасибо за разъяснение

Добавлено через 5 минут
avgoor, Можем лично пообщаться?на форуме
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
29.02.2016, 15:47     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #9
MrKaban4ik, А что мы по вашему делаем?
MrKaban4ik
0 / 0 / 0
Регистрация: 29.02.2016
Сообщений: 3
29.02.2016, 17:06     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #10
avgoor, я хочу предложить работу, точней для тебя это будет скорее халтура.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.02.2016, 19:16     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование)
Еще ссылки по теме:

Нужно ввести любые три числа и чтобы они расположились в порядке возрастания C++
C++ Переписать файл целых чисел так, чтобы сначала шли положительные, а потом - отрицательные
C++ Из массива удалить минимальное число элементов так, чтобы оставшиеся шли по возрастанию

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

Или воспользуйтесь поиском по форуму:
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
29.02.2016, 19:16     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) #11
MrKaban4ik, На этом форуме для этого есть специальный раздел (фриланс). Создайте там тему.
Yandex
Объявления
29.02.2016, 19:16     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование)
Ответ Создать тему
Опции темы

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