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

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

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

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

30.06.2016, 13:32. Просмотров 647. Ответов 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
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
30.06.2016, 15:23 #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
#include <algorithm>
#include <iostream>
 
int main()
{
    const int N = 4;
    int x[N] = { 1, 3, 2, 4 };
    int up[N];
 
    std::copy(x, x + N, up);
    std::sort(up, up + N);
 
    for(int i = 0; i < N; ++i)
    {
        int* t = std::find(up, up + N, x[i]);
        bool result = true;
        for(int a = 0, b = 0; a < N && b < N; ++a, ++b)
        {
            if(a == i) ++a;
            if(up + b == t)  ++b;
            if(x[a] != up[b])
            {
                result = false;
                break;
            }
        }
        if(result)
        {
            std::cout << "you can do that! throw away x[" << i << "]\n";
            for(int j = 0; j < N; ++j)
                if(j != i)
                    std::cout << x[j] << " ";
            std::cout << std::endl;
        }
    }
}
0
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
30.06.2016, 16:14  [ТС] #3
Babysitter, данный код работает только если массив неубывающий. Можете словесно объяснить алгоритм, чтобы я мог доделать код ? (не очень хорошо понимаю алгоритм из кода)
0
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
01.07.2016, 10:55 #4
Ka_ktus,

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

но если нужно тупо ответить на вопрос можно или не можно, то мой метод избыточный и некрасивый. я использую дополнительно памяти ~N, да и N-проходов, стыдно короче. а меня никто не проверяет, не помогает в общем вот за один проход, с константным расходом памяти. попытался хорошо написать. если под 98 нужно компилить, то вместо auto будет typename std::iterator_traits<Iter>::value_type, а вместо лямбд - обычные функции и передать указатели на них.

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
#include <iostream>
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1; ++it)
    {
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                continue;
            }
            else
                return false;
        temp = *(it + 1);
    }
    return true;
}
 
int main()
{
    typedef int Type;
    const Type N = 4;
    Type x[N] = { 1, 3, 2, 4 };
 
    std::cout << " - can i throw one an make it non-decreasing?\n";
    std::cout << " - " << (check(x, x + N, [](Type a, Type b) {return a <= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
    std::cout << " - can i throw one an make it non-increasing?\n";
    std::cout << " - " << (check(x, x + N, [](Type a, Type b) {return a >= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
 
    return 0;
}
http://rextester.com/MCKEB73164
0
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
01.07.2016, 13:09  [ТС] #5
Babysitter, К сожалению некорректно работает как минимум на примере 5, 1, 2, 3
1
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
01.07.2016, 15:53 #6
Ka_ktus, ага, очень хотелось не портить исходный массив, чтобы не пришлось копировать. хотелось меньше кода написать - не получилось, недостаточно продумал, стыдненько. кажется, что так неплохо:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1;)
    {
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                if (it != begin)
                {
                    temp = *(it - 1);
                    continue;
                }
            }
            else
                return false;
        temp = *(it + 1); ++it;
    }
    return true;
}
Добавлено через 9 минут
кстати, если first_miss установлен в true перед return true; из функции - это значит, что массив уже является отсортированым.
1
avgoor
915 / 550 / 119
Регистрация: 05.12.2015
Сообщений: 1,531
01.07.2016, 16:02 #7
Цитата Сообщение от Ka_ktus Посмотреть сообщение
Можете словесно объяснить алгоритм, чтобы я мог доделать код
Можно проще.
Рассматриваем разности соседних элментов. Каждая разность либо 0, либо положительная, либо отрицательная. Считаем количество. Если количество + и - больше 1 - ответ "нет". Иначе рассматриваем подмассив из четырех элементов, где в середине меняется знак. Если знак меняется на границе массива - ответ "да". Иначе (рассматриваем для ясности пример с одним "-" он, напомню между, [1] и [2]) если [0]<=[1]<=[3] или [0]<=[2]<=[3] ответ "да". Для случая единственного "+" - аналогично. Если и + и - встречаются 1 раз - рассмотреть нужно оба.
0
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
02.07.2016, 12:58  [ТС] #8
Babysitter, Вроде бы все работает, никаких контрпримеров я не нашел, но попытавшись переписать код для его работы с динамическими массивами столкнулся с некоторыми трудностями, не могли бы вы его переписать для динамических массивов, или целочисленных vector ?
(пробовал и с ссылками все оставить, и заменить ссылки на целые числа и работать просто с элементами массива, но программа начинает выдавать непредсказуемые результаты)

Добавлено через 17 часов 7 минут
Babysitter, Мне удалось самому вполне успешно переписать код для динамических массивов, но я опять нашел контрпример к вашему алгоритму. В этот раз это 5, 2, 2, 2, 2, 2, 2, 2, 1, 5 , который при удалении последнего элемента становится невозрастающим
1
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
02.07.2016, 19:01 #9
Ka_ktus, не было возможности раньше ответить. по поводу переписывания кода - это не требуется! функция принимает итераторы начала и конца(элемента после конца, если точнее). клиентский код для вектора приведу ниже. по поводу этого кейса - ты прав, краевые условия так и не рассмотрел все. вот очередная версия, возможно стоит посмотреть в сторону решения avgoor.

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 <iostream>
#include <vector>
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo)
{
    bool first_miss = true;
    auto temp = *begin;
    for(Iter it = begin; it != end - 1;)
    {
        if(it == end - 2 && first_miss)
            return true;
        if(!foo(temp, *(it + 1)))
            if(first_miss)
            {
                first_miss = false;
                if (it != begin)
                {
                    temp = *(it - 1);
                    continue;
                }
            }
            else
                return false;
        temp = *(it + 1); ++it;
    }
    return true;
}
 
int main()
{
    typedef int Type;
    std::vector<Type> x{5, 2, 2, 2, 2, 2, 2, 2, 1, 5};
     
    std::cout << " - can i throw one an make it non-decreasing?\n";
    std::cout << " - " << (check(x.begin(), x.end(), [](Type a, Type b) {return a <= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
    std::cout << " - can i throw one an make it non-increasing?\n";
    std::cout << " - " << (check(x.begin(), x.end(), [](Type a, Type b) {return a >= b;}) ? "yes, you can." : "no, you can not.") << "\n\n";
 
    return 0;
}
0
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
04.07.2016, 19:46  [ТС] #10
Babysitter, Хмм, забавно, ваш алгоритм почему-то не сработал на простом примере с 1, 2, 3, 4, 0, 5.
Хотя раньше вроде работало. странно.
1
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
05.07.2016, 15:23 #11
Ka_ktus, похоже у этого решения оказалась серьезная болезнь, но просто из принципа попробую довести его до конца. в момент, когда происходит мисс программа не может понять который из двух элементов плохой, кого нужно выбрасывать. кода стало больше, и я добавил тестов, а то это уже как-то печально становится... концепт плохой, будет работать везде, где есть произольный доступ.

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
#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <list>
 
 
template <class Iter, class Pred>
bool check(Iter begin, Iter end, Pred foo, bool hit = false)
{
    if (!hit && end - begin < 3)
        return true;
 
    for (Iter cur = begin + 1; cur < end; ++cur)
    {
        if (!foo(*(cur - 1), *cur))
        {
            if (hit)
                return false;
            else
            {
                hit = true;
                bool res = true;
                if (cur - 1 == begin)
                {
                    res = check(begin + 1, end, foo, hit);
                    if (res)
                        return true;
                    res = res || foo(*(cur - 1), *(cur + 1));
                }
                else if (cur + 1 == end)
                {
                    res = check(begin, cur, foo, hit);
                    if (res)
                        return true;
                    res = res || foo(*(cur - 2), *cur);
                }
                else
                    res = foo(*(cur - 2), *cur) || foo(*(cur - 1), *(cur + 1));
                if (!res)
                    return false;
            }
        }
    }
    return true;
}
 
typedef int Type;
 
template <class Iter>
void test_check(Iter begin, Iter end, bool r1, bool r2)
{
    assert(check(begin, end, [](Type a, Type b) { return a <= b; }) == r1);
    assert(check(begin, end, [](Type a, Type b) { return a >= b; }) == r2);
}
 
int main()
{
    std::vector<Type> x;
 
    // ** testing **
    // ** first element **
    x = {5, 1, 2, 3, 4};
    test_check(x.begin(), x.end(), true, false);    
    x = {0, 5, 4, 3, 2};
    test_check(x.begin(), x.end(), false, true);
    // \first element
    
    // ** last element **
    x = {1, 2, 3, 4, 0};
    test_check(x.begin(), x.end(), true, false);
    x = {5, 4, 3, 2, 7};
    test_check(x.begin(), x.end(), false, true);
    // \last element
    
    // ** one/two elements **
    x = { 1 };
    test_check(x.begin(), x.end(), true, true);
    x = {0, 1};
    test_check(x.begin(), x.end(), true, true);
    x = {1, 0};
    test_check(x.begin(), x.end(), true, true);
    // \one/two elements
    
    // ** regular cases **
    x = {5, 2, 2, 2, 2, 2, 2, 2, 1, 5};
    test_check(x.begin(), x.end(), false, true);    
    x = {1, 2, 3, 4, 0, 5};
    test_check(x.begin(), x.end(), true, false);   
    x = { 1, 5, 2, 3, 4 };
    test_check(x.begin(), x.end(), true, false);    
    x = { 5, 6, 1, 2, 3 };
    test_check(x.begin(), x.end(), false, false);
    // \regular cases
 
    return 0;
}
0
Ka_ktus
3 / 3 / 0
Регистрация: 26.06.2016
Сообщений: 9
05.07.2016, 21:55  [ТС] #12
Babysitter, Спасибо! Все работает!
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
06.07.2016, 08:57 #13
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
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
#include <deque>
///////////////////////////////////////////////////////////////////////////////
typedef std::deque  < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res     { 1, 2, 3, 4, 5, 6, 7 };
 
    if  (
            rand() % 2
        )
    {
        std::reverse
            (
                res.begin   (),
                res.end     ()
            );
    }//if
 
    int     anomalies_total     =   rand()  %   4;
 
    for( int  i{}; i < anomalies_total; ++i )
    {
        int     rand_ind    =       rand()
 
                                %   (
                                        res.size() - 1
                                    );
 
        std::swap
            (
                res[ rand_ind           ],
                res[ rand_ind   +   1   ]
            );
    }//for
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotonic_but_one_element( T_numbers    const   &   numbers )
{
    T_numbers   diff;
 
    std::adjacent_difference
        (
            numbers.begin       (),
            numbers.end         (),
            std::back_inserter  ( diff )
        );
 
    diff.pop_front();
 
    return          std::count_if
                        (
                            diff.begin  (),
                            diff.end    (),
                            []          ( auto  elem )
                            {
                                return  elem    <   0;
                            }
                        )
 
                ==  1
 
            ||      std::count_if
                        (
                            diff.begin  (),
                            diff.end    (),
                            []          ( auto  elem )
                            {
                                return  elem    >   0;
                            }
                        )
 
                ==  1;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers();
 
        std::copy
            (
                numbers.begin               (),
                numbers.end                 (),
                std::ostream_iterator<int>  ( std::cout,    "\t" )
            );
 
        std::cout   <<  std::boolalpha
                    <<  sequence_is_monotonic_but_one_element( numbers )
                    <<  std::endl;
 
        system("pause");
    }//for
}
0
Babysitter
81 / 108 / 35
Регистрация: 23.11.2015
Сообщений: 333
Завершенные тесты: 1
06.07.2016, 11:17 #14
упд. сразу не понял, что в этом варианте если последовательность уже упорядочена, то ответ false

Добавлено через 13 минут
в продакшн рановато. вопрос был можно ли удалив не более одного элемента. то есть если последовательность уже является упорядоченой, то ответ true. плюс частные случаи же
C++
1
2
3
{ 1 }   false
{ 1, 2 }   true
{ 1, 2, 3 }   false
Добавлено через 9 минут
Цитата Сообщение от Babysitter Посмотреть сообщение
частные случаи же
вопрос снят. не менее 4 целых чисел - устал я что-то.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
06.07.2016, 11:56 #15
Ну, если жалко памяти, то, с учетом
Цитата Сообщение от Babysitter Посмотреть сообщение
удалив не более одного элемента
см. ниже.
Кстати, условие
Цитата Сообщение от Babysitter Посмотреть сообщение
не менее 4 целых чисел
совершенно надуманное, моя программа считает для любой последовательности. (Пустую я принял монотонной.)
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
//На входе есть не менее 4 целых чисел, нужно определить, можно ли удалив
//не более одного элемента получить невозрастающий или неубывающий массив.
//Может кто-либо реализовать это, или дать описание наиболее быстрого способа?
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
///////////////////////////////////////////////////////////////////////////////
T_numbers   make_rand_numbers()
{
    T_numbers   res     { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
 
    if  (
            rand() % 2
        )
    {
        std::reverse
            (
                res.begin   (),
                res.end     ()
            );
    }//if
 
    int     anomalies_total     =   rand()  %   5;
 
    for( int  i{}; i < anomalies_total; ++i )
    {
        int     rand_ind    =       rand()
 
                                %   (
                                        res.size() - 1
                                    );
 
        std::swap
            (
                res[ rand_ind           ],
                res[ rand_ind   +   1   ]
            );
    }//for
 
    return  {
                res.begin(),
                res.begin()     +   rand()  %   res.size()
            };
}
///////////////////////////////////////////////////////////////////////////////
bool    sequence_is_monotone_except_may_be_one_element( T_numbers    const   &   numbers )
{
    bool    bool_res    =   numbers.size()  <=  2;
 
    if( !bool_res )
    {
        int     count_pos{};
        int     count_neg{};
 
        for( size_t  i{1}; i < numbers.size(); ++i )
        {
            auto    diff    =       numbers[i]
                                -   numbers[i - 1];
 
            if( !diff )
            {
                continue;
            }
 
            diff    >   0
                ?   ++count_pos
                :   ++count_neg;
 
            bool_res    =       std::min    (
                                                count_pos,
                                                count_neg
                                            )
                            <=  1;
 
            if( !bool_res )
            {
                return  bool_res;
            }
        }//for
    }//if
 
    return  bool_res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    numbers     =   make_rand_numbers();
 
        std::copy
            (
                numbers.begin               (),
                numbers.end                 (),
                std::ostream_iterator<int>  ( std::cout,    "\t" )
            );
 
        std::cout   <<  std::boolalpha
                    <<  sequence_is_monotone_except_may_be_one_element( numbers )
                    <<  std::endl;
 
        system("pause");
    }//for
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.07.2016, 11:56
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
06.07.2016, 11:56
Ответ Создать тему
Опции темы

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