Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9

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

30.06.2016, 13:32. Показов 2017. Ответов 20

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

Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
Заранее спасибо!
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
30.06.2016, 13:32
Ответы с готовыми решениями:

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

Затруднение с удалением элемента и образованием нового размера статического массива
Здравствуйте, существует затруднение в программном формулировании удаления элементов из массива. Задача выглядит так: Есть массив...

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

20
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
07.07.2016, 18:25
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
07.07.2016, 18:25

Эффективный алгоритм сортировки одного массива по данным другого массива
Всем привет! Время сортировки массива с 2 млн. строк - 0,85 сек., Время сортировки массива индексов по данным этого же массива строк...

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

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

Поменять расположение элементов одного массива так же, как и в другом после сортировки
Сложновато вопрос сформулировать. Элементы массива y сортируются по возрастанию и меняется их расположение. Мне же нужно сделать, чтобы...

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


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

Или воспользуйтесь поиском по форуму:
21
Ответ Создать тему
Новые блоги и статьи
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно. • На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru