Step 2 (S-37917)

From Stepik Wiki
Jump to: navigation, search

Step on Stepik: https://stepik.org/lesson/13030/step/2

Сегодня мы будем изучать разные алгоритмы, которые есть в стандартной библиотеке C++. Они помогают быстрее писать программы. В основном мы будем использовать библиотеку algorithm.

Сортировка

Начнём с сортировки данных. Мы уже умеем делать её вручную, с помощью сортировки выбором, а также структуры multiset. Сегодня мы освоим ещё один, более быстрый и простой метод.

Итак, возьмём последовательность чисел, которую нужно считать, упорядочить и вывести. Вот как решается эта задача:


#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {    int n;    cin >> n;    vector <int> a(n);    for (int i = 0; i < n; i++) {        cin >> a[i];    }    sort(a.begin(), a.end());    for (auto now : a) {        cout << now << " ";    }    return 0;}

В этой программе есть новая функция sort. Она принимает на вход два параметра: начало и конец сортируемой области. В нашем случае это начало вектора (begin) и его конец (end).Функцию sort можно применять для векторов, которые состоят из сравнимых величин: целых и вещественных чисел, строк и чего-угодно другого, для чего можно ввести операцию «меньше».

Сортировка пар

Очень часто требуется отсортировать пары элементов. Мы уже столкнулись с парами во время изучения словарей, а сейчас остановимся на них подробнее. Для их использования нужно подключить библиотеку utility.

Например, мы хотим отсортировать пары «число — номер в исходной последовательности». В качестве ответа нужно вывести позиции отсортированных элементов в исходном массиве.


#include <iostream>#include <vector>#include <algorithm>#include <utility>using namespace std;int main() {    int n;    cin >> n;    vector <pair <int, int>> a(n);    for (int i = 0; i < n; i++) {        int temp;        cin >> temp;        a[i] = {temp, i}; // создание пары значение - номер    }    sort(a.begin(), a.end());    for (auto now : a) {        cout << now.second << " ";    }    return 0;}

Чтобы создать пару, пишем ключевое слово pair, затем в треугольных скобках указываем через запятую два типа (для полей first и second соответственно). Ещё один интересный трюк — это создание пары из двух значений. Достаточно в фигурных скобках написать оба значения через запятую, чтобы получилась. Отличие от предыдущей задачи состоит в том, что мы выводим только поля second — номера элементов в исходной последовательности.

При сравнении двух пар сначала сравниваются первые элементы, а если они равны — то вторые. Как время: сначала по часам, затем по минутам.

Сортировка по убыванию

Сортировать по убыванию очень просто — нужно сначала выстроить массив по возрастанию, а потом его развернуть. Для этого используется функция reverse. В ней задаются те же параметры, что и у sort — начало и конец области.

Структуры

Не все сложные объекты можно описать с помощью пар. Чтобы описывать объекты, которые характеризуются несколькими разными значениями, нужны структуры. Фактически, структура — это новый тип переменных. Сначала нужно описать структуру, а после этого можно создавать переменные, вектора и прочие элементы такого типа. Описание структуры должно следовать сразу после using namespace std и находиться вне функций. Например, мы хотим описать человека при помощи двух характеристик: рост и имя. Структура создается так:


struct man {    int height;    string name;};

Сначала пишем ключевое слово struct, затем — название структуры, а в фигурных скобках перечислим поля структуры вместе с указанием типа каждого поля. Обратите внимание на точку с запятой после фигурной скобки — она обязательно нужна.

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


#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;struct man {    int height;    string name;};bool cmp(man a, man b) {    return a.height < b.height;}int main() {    int n;    cin >> n;    vector <man> a(n);    for (int i = 0; i < n; i++) {        int temp;        string s_temp;        cin >> temp >> s_temp;        man struct_temp; // временная структура        struct_temp.height = temp;        struct_temp.name = s_temp;        a[i] = struct_temp; // создание пары значение - номер    }    sort(a.begin(), a.end(), cmp);    for (auto now : a) {        cout << now.name << endl;    }    return 0;}


В этой программе, во-первых, мы научились создавать переменные для описания людей, а также вектор из таких переменных. Во-вторых, теперь мы можем обращаться к отдельным полям структуры. Как и в парах, это делается через точку, то есть first и second в паре — это тоже поля структуры. И, наконец, мы научились сортировать структуры. Для этого в программе используется функция sort с тремя параметрами. Первые два из них обозначают начало и конец сортируемой области, а третий — имя функции для сравнения. В нашем случае это функция cmp, которая принимает на вход две наших структуры и возаращает истину, если первая «меньше» второй, или ложь в обратном случае. Этой функции достаточно для сортировки. Если заменить в ней знак «меньше» на «больше», то массив будет отсортирован по убыванию.

Устойчивая сортировка

Сортировка называется устойчивой, если она сохраняет взаимный порядок одинаковых элементов. Если Вася и Петя одного роста, но в исходной последовательности Вася стоял раньше Пети, то после устойчивой сортировки Вася также должен идти перед Петей.

При использовании sort взаимный порядок одинаковых элементов может нарушиться (Петя окажется перед Васей). Чтобы этого не произошло, нужно использовать функцию устойчивой сортировки stable_sort. Она принимает те же параметры, что и sort, но работает немного медленнее.

Медиана

В статистике широко используется понятие «среднее значение». Например, есть три человека с зарплатами 3 миллиона, 300 рублей и 0 рублей. Средняя зарплата получится в 1 миллион 100 рублей. Ещё одна характеристика, которая полезна для оценки значений в последовательности, называется «медиана». Это значение элемента, который стоит на среднем месте в упорядоченной последовательности. В нашем примере с зарплатой медиана равна 300 рублям. Если количество элементов чётное, то медиан получается две.

Чтобы найти медианное значение, нужно отсортировать массив и взять элемент, стоящий в середине. Существуют и другие, более быстрые способы поиска медианы.

Перестановки

Необходимость получить все перестановки в последовательности и выбрать среди них наилучшую возникает очень часто. В C++ есть встроенная функция, которая позволяет из последовательности, содержащей перестановку чисел, получить следующую перестановку. Например, за перестановкой 1, 2, 3 идёт перестановка 1, 3, 2, затем 2, 1, 3 и так далее. Функция называется next_permutation и принимает на вход два параметра: начало и конец последовательности, содержащей перестановку. Next_permutation изменяет порядок значений в последовательности, а также возвращает логическое значение. Обычно это истина — кроме случая, когда все элементы уже стоят в убывающем порядке, и следующей перестановки просто нет. Тогда функция переставляет элементы в возрастающем порядке и возвращает ложь.

Например, такая программа сначала заполняет последовательность из N чисел числами от 1 до N по возрастанию, а затем генерирует все возможные перестановки и выводит их:


#include <iostream>#include <vector>#include <algorithm>using namespace std;void print(vector <int> a) { // функция вывода вектора    for (auto now : a) {        cout << now << " ";    }    cout << endl;}int main() {    int n;    cin >> n;    vector <int> a(n);    for (int i = 1; i <= n; i++) {        a[i – 1] = i;    }    while (next_permutation(a.begin(), a.end()) {        print(a);    }    return 0;}

Вместо заключения

На этом наш курс заканчивается — я надеюсь, вам понравилось. С тем практическим опытом, который вы получили, будет намного легче двигаться дальше, продолжая своё обучение в университете, на курсах или самостоятельно. Спасибо за совместную работу!