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

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

Войти
Регистрация
Восстановить пароль
 
 
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
#1

Определение возможности сортировки массива удалением одного элемента - C++

30.06.2016, 13:32. Просмотров 664. Ответов 20

На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив не более одного элемента получить невозрастающий или неубывающий массив.

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

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

Определение первого из столбцов, не содержащих ни одного отрицательного элемента - C++
Здравствуйте, помогите, пожалуйста, с заданиями... 1. Консольный ввод/вывод целочисленного массива размером 6*4. 2. Упорядочение строк...

Из массива A удалить те цепочки нечетных элементов, в которых нет ни одного элемента из массива B - C++
Пожалуйста помогите! Из массива A удалить те цепочки нечетных элементов, в которых нет ни одного элемента из массива B. Пример: ...

Определение 3го по величине элемента массива - C++
В соревнованиях по бегу принимают участие N спортсменов (3 ≤ N ≤ 1000). Результаты забега занесены в массив по порядку номеров участников....

Определение первого максимального элемента массива - C++
Одномерный массив А длиной N<=20 заполнить случайными числами из диапазона . Составить программу определения: • первого максимального...

Определение минимального элемента одномерного массива - C++
Разработать и испытать функцию min(X) для определения минимального элемента одномерного массива X, введя вспомогательную рекурсивную...

20
avgoor
915 / 550 / 119
Регистрация: 05.12.2015
Сообщений: 1,531
06.07.2016, 13:34 #16
Mr.X, Последовательность: {1, 1, 0, 0, 1, 1} пройдет ваш тест, а не должна. Выше писал, что еще нужно проверять.

Добавлено через 15 минут
UPD: минимальная последовательность, воспроизводящая проблему: {3, 4, 1, 2}
1
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
06.07.2016, 16:19 #17
Цитата Сообщение от avgoor Посмотреть сообщение
Mr.X, Последовательность: {1, 1, 0, 0, 1, 1} пройдет ваш тест, а не должна. Выше писал, что еще нужно проверять.
Добавлено через 15 минут
UPD: минимальная последовательность, воспроизводящая проблему: {3, 4, 1, 2}
А, да, замечание справедливое.
0
notAll
418 / 139 / 30
Регистрация: 27.05.2016
Сообщений: 364
Завершенные тесты: 2
06.07.2016, 17:35 #18
Как то так:
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
#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <cassert>
 
template <typename It>
bool check(It first, It last)
{
    auto length = std::distance(first, last);
    assert(length >= 4);
 
    using value_type = typename std::iterator_traits<It>::value_type;
    auto final_check = [](auto f, auto l) { return std::is_sorted(f, l) ||
                std::is_sorted(f, l, std::greater<value_type>());
    };
 
    if (final_check(first, last)) return true;
    else
    {
        for (int i = 0; i < length; ++i)
        {
            std::vector<value_type> v{first, last};
            v.erase(v.begin() + i);
            if (final_check(v.begin(), v.end()))
                return true;
        }
    }
    return false;
}
 
int main()
{
    int arr[] = {1, 2, 3, 4, 0, 5};
    std::cout << std::boolalpha;
    std::cout << check(std::begin(arr), std::end(arr));
}
0
avgoor
915 / 550 / 119
Регистрация: 05.12.2015
Сообщений: 1,531
06.07.2016, 18:07 #19
notAll, А ничего, что вы задачу, решаемую за линейное время решаете за квадратичное? Измените main вот так:
C++
1
2
3
4
5
6
7
8
9
int main()
{
    const int size = 1000000;
    int arr[size];
    std::iota(arr, std::end(arr) - 1, 0);
    arr[size - 1] = -1;
    std::cout << std::boolalpha;
    std::cout << check(std::begin(arr), std::end(arr));
}
0
notAll
418 / 139 / 30
Регистрация: 27.05.2016
Сообщений: 364
Завершенные тесты: 2
07.07.2016, 11:22 #20
Тогда так:
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
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
 
template <typename It>
bool check(It first, It last)
{
    auto it = std::is_sorted_until(first, last);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (*--prev < *++next)
            return std::is_sorted_until(next, last) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && *----prev < *it)
            return std::is_sorted_until(next, last) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
Добавлено через 11 минут
И с проверкой на обратную сортировку:
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
#include <iostream>
#include <vector>
#include <functional>
#include <iterator>
#include <algorithm>
 
template <typename It, typename Comparator =
          std::less<typename std::iterator_traits<It>::value_type>>
bool check_impl(It first, It last, Comparator comp = Comparator())
{
    auto it = std::is_sorted_until(first, last, comp);
    if (it != last)
    {
        //1 - delete first broken element
        It prev, next;
        prev = next = it;
        if (comp(*--prev, *++next))
            return std::is_sorted_until(next, last, comp) == last;
 
        //2 - delete prev element before broken
        prev = it;
        if ((prev - first) > 1 && comp(*----prev, *it))
            return std::is_sorted_until(next, last, comp) == last;
        else if ((prev - first) == 1)
            return std::is_sorted_until(it, last, comp) == last;
 
        return false;
    }
 
    return true;
}
 
template <typename It>
bool check(It first, It last)
{
    if (!check_impl(first, last))
        return check_impl(first, last,
                          std::greater<typename std::iterator_traits<It>::value_type>());
    return true;
}
 
template <typename T>
void print(const std::vector<T> &v)
{
    for (const auto &i : v)
        std::cout << i << ", ";
}
 
int main()
{
    std::vector<std::vector<int>> vec {
        {1,2,3,4,5}, //true
        {1,2,3,4,5,0}, //true
        {1,2,3,4,0,5}, //true
        {42,1,2,3,4,5}, //true
        {1,42,2,3,4,5}, //true
        {42,1,2,3,4,5,0}, //false
        {1,42,2,3,4,42,5}, //false
        {1,1,0,0,1,1}, //false
        {3,4,1,2} //false
    };
 
    std::cout << std::boolalpha;
    for (auto &v : vec) {
        print(v);
        std::cout << " - " << check(std::begin(v), std::end(v)) << "\n";
    }
}
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.07.2016, 18:25 #21
Цитата Сообщение от avgoor Посмотреть сообщение
Иначе рассматриваем подмассив из четырех элементов, где в середине меняется знак. Если знак меняется на границе массива - ответ "да". Иначе (рассматриваем для ясности пример с одним "-" он, напомню между, [1] и [2]) если [0]<=[1]<=[3] или [0]<=[2]<=[3] ответ "да". Для случая единственного "+" - аналогично. Если и + и - встречаются 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
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
///////////////////////////////////////////////////////////////////////////////
//8.
///////////////////////////////////////////////////////////////////////////////
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res{ 1, 2, 3, 4 };
 
    std::random_shuffle
        (
            res.begin   (),
            res.end     ()
        );
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotone_except_may_be_one_element( T_numbers    const   &   numbers )
{
    bool    bool_res    =   numbers.size()  <=  3;
 
    if( bool_res )
    {
        return  bool_res;
    }
 
    int     diff_prev           {};
    int     diff                {};
 
    int     count_pos           {};
    int     count_neg           {};
    int     count_min           {};
 
    int     pos_pos             {};
    int     pos_neg             {};
 
    int     bad_pos_adj_count   {};
    int     bad_neg_adj_count   {};
 
    for( size_t  i{1}; i < numbers.size(); ++i )
    {
        diff    =   numbers[i]
                -   numbers[i - 1];
 
        if  (
                    i                   ==  pos_pos     +   1
                &&  count_pos           ==  1
                &&  abs( diff_prev )    >   abs( diff )
            )
        {
            ++bad_pos_adj_count;
 
            if( bad_pos_adj_count   ==  2 )
            {
                ++count_pos;
            }
        }//if
 
        if  (
                    i                   ==  pos_neg     +   1
                &&  count_neg           ==  1
                &&  abs( diff_prev )    >   abs( diff )
            )
        {
            ++bad_neg_adj_count;
 
            if( bad_neg_adj_count   ==  2 )
            {
                ++count_neg;
            }
        }//if
 
        if( !diff )
        {
            continue;
        }
 
        if( diff    >   0 )
        {
            if( ++count_pos ==  1 )
            {
                pos_pos     =   i;
 
                if  (
                            i   >   1
 
                        &&      abs( diff       )
                            >   abs( diff_prev  )
                    )
                {
                    ++bad_pos_adj_count;
                }
            }//if
        }
        else
        {
            if( ++count_neg ==  1 )
            {
                pos_neg     =   i;
 
                if  (
                            i   >   1
 
                        &&      abs( diff       )
                            >   abs( diff_prev  )
                    )
                {
                    ++bad_neg_adj_count;
                }
            }//if
        }//else
 
        count_min   =   std::min    (
                                        count_pos,
                                        count_neg
                                    );
 
        bool_res    =       count_min
                        <=  1;
 
        if( !bool_res )
        {
            break;
        }
 
        diff_prev   =   diff;
    }//for
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers                               ();
        bool    bool_res    =   sequence_is_monotone_except_may_be_one_element  ( numbers );
 
        if( !bool_res )
        {
            std::copy
                (
                    numbers.begin               (),
                    numbers.end                 (),
                    std::ostream_iterator<int>  ( std::cout,    "\t" )
                );
 
            std::cout   <<  std::boolalpha
                        <<  bool_res
                        <<  std::endl;
 
            system("pause");
        }//if
    }//for
}
0
07.07.2016, 18:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2016, 18:25
Привет! Вот еще темы с ответами:

Определение минимального элемента одномерного массива - C++
Разработать и испытать функцию min(X) для определения минимального элемента одномерного массива X, введя вспомогательную рекурсивную...

Динамическое выделение массива и удаление одного элемента - C++
Нужно динамически выделить массив из 10 элементов(через new) и при определённом условии удалить(delete) определённый элемент.

Определение индекса элемента массива, имеющего максимальное значение (функция) - C++
Написать функцию для определения индекса элемента массива, имеющего максимальное значение.

Циклический буфер. Проблема с удалением элемента. - C++
В общем, у меня такая проблема.. Не могу исправить ошибку в процедуре удаления... Элемент удаляет, но при выводе буфера программа...


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

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

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