Самостоятельная работа 14: стандартные алгоритмы I

Изучение элементов алгоритмизации и приёмов обобщённого программирования на основе библиотеки стандартных алгоритмов C++.

В данном задании свобода выбора алгоритма реализации намеренно ограничена.

Определения и примеры

Пример 1

Дана некая последовательность и предикат bound, определяющий значения-разделители. Требуется отсортировать куски последовательности, отделённые друг от друга значениями-разделителями. Использовать sort, find_if, find_if_not. Например, так можно отсортировать буквы в каждом слове в строке.

Решение запишем в виде функции sort_blocks, имеющей следующий заголовок:

Функция возвращает void, поскольку нет никаких “естественных” возвращаемых значений, которые было бы логично ожидать от такой функции (например, стандартная функция sort также возвращает void). В принципе, можно было бы возвращать количество отсортированных кусков, но так как в задании об этом ничего нет, то делать этого не будем.

Функция принимает пару итераторов, задающих исходную последовательность [from, to). Предполагается, что это итераторы произвольного доступа (об этом человеку, читающему код, сигнализирует имя RanIt), так как именно такие итераторы требуются стандартным алгоритмам сортировки.

Пример 2

Дан многоугольник, требуется удалить вершины, слишком близкие к вершинам, предыдущим при обходе границы многоугольника, включая подряд идущие дубликаты вершин. Использовать алгоритм unique.

Для простоты определим вершину и многоугольник следующим образом:

Чтобы лишний раз не брать квадратный корень, будем оперировать квадратом расстояния:

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

Итак, сама операция “прореживания” многоугольника может быть записана следующим образом:

/// Функция упрощения контура (удаления подряд идущих близких вершин).
template <class Coord>
void simplify(Polygon<Coord> &polygon, Coord min_len)
{
  min_len *= min_len; // сравниваем с квадратом.
  // Компаратор вершин: 
  // возвращает истину, если они ближе друг ко другу, чем на min_len единиц.
  const auto near = [=](const Vertex<Coord> &a, const Vertex<Coord> &b)
  {
    return squared_distance(a, b) <= min_len;
  };

  // Удалим лишние вершины прямым обходом контура как незамкнутой последовательности.
  polygon.erase(
    std::unique(polygon.begin(), polygon.end(), near),
    polygon.end());

  // Удалим вершины с конца, слишком близкие к первой вершине
  // (контур всё-таки замкнутая последовательность).
  while (3 < polygon.size() && near(polygon.front(), polygon.back()))
    polygon.pop_back();
}

Пример 3

Задача отчасти похожа на предыдущую, но реализуется другими средствами.

Пусть даны последовательность значений и компаратор, определяющий, является ли пара значений “близкой”.

Вывести в итератор вывода исходную последовательность, заменяя в ней все группы подряд идущих близких значений на их арифметические средние.

В цикле применять adjacent_find для поиска следующей пары близких значений (начало группы), find_if или find_if_not для поиска конца группы, accumulate для вычисления арифметического среднего.

Можно сразу написать “арифметическое среднее” через accumulate:

Критика данного решения: если итератор FwdIt не является итератором произвольного доступа, то происходит двойной обход последовательности: один раз в accumulate и один раз в distance, что, в частности, не позволяет использовать итератор ввода.

Обобщённый алгоритм вычисления среднего, лишённый этого недостатка, мог бы выглядеть так (C++14):

namespace implementation
{
  // Среднее для любых итераторов: нужно считать элементы.
  template <class It, class Init, class Compose, class Finalize, class AnyTag>
  auto _mean(It from, It to, Init init, Compose compose, Finalize finalize, AnyTag)
  {
    uint64_t count = 0;
    auto acc = init(from);
    for (; from != to; ++count, ++from)
      acc = compose(acc, *from);

    return finalize(acc, count);
  }

  // Среднее для итераторов произвольного доступа: не нужно считать элементы.
  template <class It, class Compose, class Finalize>
  auto _mean(It from, It to, Compose compose, Finalize finalize, std::random_access_iterator_tag)
  {
    const auto start = init(from);
    const auto count = to - from;
    return count? accumulate(from, to, start, compose) / count: start;
  }

  // Реализации Init.
  template <class It>
  using IVT = typename std::iterator_traits<It>::value_type;

  const struct Zero_init
  {
    template <class It>
    IVT<It> operator()(It) const { return IVT<It>(0); }
  } zero_init;

  const struct Unit_init
  {
    template <class It>
    IVT<It> operator()(It) const { return IVT<It>(1); }
  } unit_init;
}

// Обобщённое среднее.
template <class It, class Init, class Compose, class Finalize>
auto mean(It from, It to, Init init, Compose compose, Finalize finalize)
{
  typename std::iterator_traits<It>::iterator_category tag;
  return implementation::_mean(from, to, init, compose, finalize, tag);
}

// Арифметическое среднее.
template <class It>
auto arithmetic_mean(It from, It to)
{
  return mean(from, to, implementation::zero_init, std::plus<>{},
    [](auto &&val, auto count) { return val / count; });
}

// Геометрическое среднее.
template <class It>
auto geometric_mean(It from, It to)
{
  return mean(from, to, implementation::unit_init, std::multiplies<>{},
    [](auto &&val, auto count) { using std::pow; return pow(val, 1. / count); });
}

// Гармоническое среднее.
template <class It>
auto harmonic_mean(It from, It to)
{
  using IVT = implementation::IVT<It>;
  return mean(from, to, implementation::zero_init,
    [](auto a, auto b) { return a + IVT(1) / b; },
    [](auto &&val, auto count) { return count / val; });
}

C++, HTML

Решение на основе указанных алгоритмов может выглядеть так.

template <class FwdIt, class OutIt, class NearComp>
OutIt sequence_simplify(FwdIt from, FwdIt to, OutIt out, NearComp near)
{
  while (from != to)
  {
    // Найти начало усредняемой группы.
    auto group_begin = adjacent_find(from, to, near);
    // Скопировать все элементы от текущего значения from до начала группы в вывод.
    out = copy(from, group_begin, out);

    // Найти конец усредняемой группы.
    auto group_end = group_begin == to? to
      : find_if_not(group_begin, to,
          bind(near, cref(*group_begin), placeholders::_1));

    // Если группа не пуста, записать вместо неё в вывод арифметическое среднее
    // составляющих её элементов.
    if (group_begin != group_end)
      *out++ = arithmetic_mean(group_begin, group_end);

    // Переставить текущую позицию from за группу.
    from = group_end;
  }

  return out;
}

создаёт новый унарный предикат из бинарного предиката (компаратора) near, замещением первого параметра ссылкой (cref, обёртка const-ссылки) на элемент, на который указывает итератор group_begin (на элемент, открывающий усредняемую группу). Единственный аргумент (он же “первый” аргумент — placeholders::_1) нового предиката становится вторым аргументом компаратора near.

Из-за того что происходит разыменование group_begin, приходится проверять, указывает ли он на корректный элемент (т. е. не закончилась ли последовательность). В противном случае получим неопределённое поведение.

Варианты

Из последовательности, заданной парой итераторов ввода, не изменяя её, извлечь “лучшие” k (параметр функции) элементов и записать их в обратном порядке в заданную итератором вывода последовательность.

Применить partial_sort_copy во временный vector размера k, из которого выполнить reverse_copy в последовательность вывода.

Пусть k = 5, тогда в результате должна получиться последовательность:

Найти последнее вхождение заданной последовательности в другой последовательности и посчитать количество оставшихся элементов в этой другой последовательности, удовлетворяющих заданному предикату. Применить find_end и count_if.

Посчитать количество отрицательных элементов после последнего вхождения подпоследовательности { 1, 2, 3 }. Результат: 2.

Дана последовательность и два компаратора, выполняющие сравнение на “меньше” (“хуже”) по двух разным качествам. Требуется удалить из последовательности все элементы, для которых (среди оставленных) существует элемент, который “не хуже” по обоим качествам (т. е. оставить элементы, оптимальные по Парето).

Выполнить sort, используя первый компаратор. Затем обратить порядок (reverse) и выполнить unique, используя отрицание второго компаратора.

Если дан компаратор comp такой, что comp(a, b) мы считаем некоторым сравнением на “меньше”, то для получения нового компаратора, являющегося отрицанием comp:

при использовании C++14 следует применить к нему стандартную функцию not_fn из заголовочного файла functional;
если эта функция недоступна, то можно использовать устаревшую функцию not2 из того же заголовочного файла.

Компаратор 1: сравнение строк на меньше (лексикографическое), компаратор 2: сравнение длин строк на меньше. Таким образом, например, "zx" доминирует "qi", "rexx" доминирует "max". Результат:

Выполнить разбиение заданной последовательности по заданному предикату, затем отсортировать первую часть разбиения, используя один порядок (компаратор), а вторую часть — используя другой порядок. Применить partition и sort.

Предикат разбиения: чётность. Компаратор первой части: <, компаратор второй части: >. Результат:

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

Применить find и rotate к каждой строчке матрицы.

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

Применить transform и equal. Разрешается в целях оптимизации переставлять элементы (не изменяющиеся элементы переставлять в конец и больше не применять к ним отображение).

Результат после 364 итераций (найдены две из четырёх неподвижных точек, элементы не переставлялись):

Даны две последовательности. Построить пересечение данных последовательностей как множеств. Применить sort и unique к каждой из последовательностей, затем set_intersection.

Из заданного числа элементов (количество — параметр), наименьших в некотором смысле (компаратор — параметр), выбрать те, которых нет в заданной последовательности (предполагается, что данная последовательность заранее отсортирована в том же порядке). Применить partial_sort_copy в вектор и затем set_difference.

Задано количество: 5 и компаратор > (std::greater). Т. е. требуется выбрать пять наибольших элементов из исходной последовательности и выбросить из них те, что есть в заданном множестве. Результат

Для заданной размерности пространства N (параметр функции) заполнить последовательность N-мерных векторов (с которыми можно работать как с массивами размера N) псевдослучайными числами в диапазоне [–1, 1] таким образом, чтобы все они находились внутри N-мерного 1-шара (сумма квадратов координат меньше или равна единице). Использовать generate и remove_if.

Генератор псевдослучайных чисел (Number может быть float, double или что-нибудь аналогичное) равномерного на [–1, 1] распределения, реализованный средствами Стандартной библиотеки C++:

Применить к заданной последовательности заданное отображение и посчитать количество смен знака (включая зануление). Использовать transform и inner_product (аналогично Л14.).

Дано отображение f(x) = sin sin x. Применив это отображение к данной последовательности, получим:

Смен знака в смысле, указанном выше, здесь три: 0. → 0.745624, 0.140652 → –0.6866, –0.275794 → 0.610734.

Отсортировать в соответствии с переданным компаратором заданную последовательность и проверить, является ли она подмножеством другой (уже отсортированной) последовательности. Применить sort и includes.

Дана последовательность — “вероятное подмножество”:

и последовательность — “вероятное надмножество”, отсортированная по возрастанию:

Ответ в данном случае отрицательный: первая последовательность не является подмножеством второй. Следует составить тесты и для отрицательного и для положительного ответов.

Выбрать из исходной последовательности элементы в соответствии с заданным предикатом, заполнив ими vector. Выполнить устойчивую сортировку выбранных элементов и вернуть полученный объект vector. Применить copy_if и stable_sort.

Исходная последовательность пар (строка–число):

Выбираем все элементы со значением второго элемента больше или равным 200:

Сортируем устойчивой сортировкой по убыванию второго элемента пары, в итоге получаем:

Даны две последовательности a и b. Предполагается, что они имеют следующий вид: a = α γ β, b = α δ β, где α — общий префикс максимальной длины, β — общий суффикс максимальной длины, γ и δ — несовпадающие “средние” части (если a = b, то γ и δ пусты). Требуется написать функцию, которая будет извлекать (выводя в заданную последовательность вывода) часть γ. Применить mismatch (прямым и обратным итератором) и copy.

Тогда в результат должна пойти последовательность

Самостоятельная работа 14: стандартные алгоритмы I

Кувшинов Д.Р.

2016

Цели и критерии

Определения и примеры

Пример 1

Пример 2

Пример 3

Варианты

1

2

3

4

5

6

7

8

9

10

11

12

13