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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Исполнение функции-члена в отдельном потоке http://www.cyberforum.ru/cpp-beginners/thread1773562.html
Здравствуйте, форум! Вот такой вот пример: Имеется класс, в котором есть 3 перегрузки одной функции. class A { public: void func1();
C++ Обработка записей содержащих структуры "Студент" Задание для самостоятельного выполнения Составить программу, обеспечивающую формирование данных из задания 5 в виде списка. Реализовать следующие операции работы со списком в виде меню: Меню:... http://www.cyberforum.ru/cpp-beginners/thread1773559.html
Зеркально отразить элементы матрицы относительно горизонтальной оси симметрии C++
Дана квадратная матрица порядка . Зеркально отразить ее элементы относительно горизонтальной оси симметрии матрицы.
Динамически распределяемая память, удаление символов в строке C++
Нужна помощь в написании программы: Удаление символов Написать функцию, обеспечивающую ввод с клавиатуры строки неограниченной длины без редактирования. Написать функцию, которая удаляет символы,...
C++ Напечатать все слова последовательности, предварительно преобразовав каждое из них по правилу http://www.cyberforum.ru/cpp-beginners/thread1773508.html
Нужна помощь в написании программы: Дана последовательность, содержащая до 5 слов, в каждом из которых до 5 строчных латинских букв; между соседними словами — не менее одного пробела, за последним...
C++ Как нарисовать фигуру и двигать ее мышью? Как нарисовать геометрическую фигуру (треугольник, квадрат, многоугольник) в окне? И как сделать так чтобы они двигались мышью? подробнее

Показать сообщение отдельно
Babysitter
80 / 107 / 35
Регистрация: 23.11.2015
Сообщений: 332
Завершенные тесты: 1
01.07.2016, 10:55
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
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru