Домашнее задание (с замечаниями по STL)

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 3 мес., 1 неделя назад.

Просмотр 1 сообщения - с 1 по 1 (всего 1)
  • Автор
    Сообщения
  • #4535

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

    Задача взята с acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 27%):

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

    Входные данные:
    В первой строке входного файла INPUT.TXT записано единственное число N – количество элементов массива. Вторая строка содержит N целых чисел, представляющих заданный массив. Все элементы массива разделены пробелом. Каждое из чисел во входном файле не превышает 102 по абсолютной величине.

    Выходные данные:
    В единственную строку выходного файла OUTPUT.TXT нужно вывести два числа, разделенных пробелом: сумму положительных элементов и произведение чисел, расположенных между минимальным и максимальным элементами. Значения суммы и произведения не превышают по модулю 3*10^4.

    Пример 1:
    INPUT.TXT:

    5
    -7 5 -1 3 9

    OUTPUT.TXT : 17 -15

    Пример 2:
    INPUT.TXT:

    8
    3 14 -9 4 -5 1 -12 4

    OUTPUT.TXT : 26 180

    Пример 3:
    INPUT.TXT:

    10
    -5 1 2 3 4 5 6 7 8 -3

    OUTPUT.TXT : 36 5040

    Посчитать сумму положительных элементов массива — совсем простая задача, сделать это можно сразу при считывании данных с файла. Однако, чтобы найти произведение между минимальным и максимальным элементами надо сначала найти их индексы (обозначим imin и imax), а затем обработать элементы между этими индексами. При этом код типа такого:

    for (int i = imin; i < imax; ++i) 
      prod *= a[i];

    Не сработает по двум причинам. Во-первых imin может быть больше imax. Во-вторых, требуется обработать элементы между, т.е. значение минимального и максимального элементов не должны быть обработаны, у нас же минимальный участвовал при умножении, а максимальный — нет.

    Ниже приведен самый незатейливый код, который успешно решает задачу:

    #include <fstream>
    using namespace std;
    
    int main() {
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
      int a[100], n, 
          imax = 0, imin = 0, 
          sum = 0, prod = 1;
       
      ifst >> n;
      for (int i = 0; i < n; ++i) {
        ifst >> a[i];
        if (a[imax] < a[i]) imax = i;
        if (a[imin] > a[i]) imin = i;
        if (a[i] > 0) sum += a[i];
      }
      
      int from = imax, to = imin;
      if (from > to)
        swap(from, to);
    
      for (int i = from+1; i < to; ++i) 
        prod *= a[i];
      
      ofst << sum << " " << prod;
          
      ofst.close();
    }

    Видно, что индексы минимума и максимума ищутся также, как и сумма, при считывании элементов с файла. Переменные from и to хранят индексы массива, между которыми нужно найти произведение, если они стоят в «неправильном» порядке — переставляются (функция std::swap). За второй проход по массиву находим искомое произведение.

    В этой реализации, из стандартной библиотеки используются только функции для работы с файлом и std::swap, остальные алгоритмы написаны вручную, при этом код достаточно легко читается. Но вот проблема, на конференциях по С++ часто говорят о том, что не стоит писать свои велосипеды — надо брать проведенные в стандартной библиотеке. Попробуем сделать это и посмотрим что получится:

    Для начала, можно использовать вектор вместо массива. Чтобы не сильно упала эффективность — вектор не расширялся при каждом push_back, зададим размер вектора сразу, методом resize. Также для этого можно было использовать метод reserve.

    Поиск минимума и максимума также не стоит делать вручную. В стандартных алгоритмах есть функция minmax_element как раз для нашего случая. Для вычисления суммы и произведения элементов можем использовать std::accumulate. Перейдем к проблемам.

    Функция minmax_element есть (она находит минимум и максимум за один проход по массиву), но вот пользоваться ей не очень удобно — возвращает она пару (std::pair). Минимальный элемент можно получить как minmax.first, а максимальный — minmax.second. Читается не очень хорошо. Улучшить положение может новый синтаксис, называемый «структурным связыванием» из С++17:

    auto [it_min, it_max] = minmax_element();

    Однако, будет ли это выглядеть лучше, чем два последовательных вызова min_element и max_element? Будет ли это работать в компиляторе у вас на работе при том, что огромное количество кода до сих пор собирается только с С++98?

    Ну ладно, получили мы два итератора, алгоритм accumulate может посчитать сумму, произведение (или что-то еще) для элементов между ними. Однако, нам точно также как и для индексов необходимо найти тот, что «слева» и тот, что «справа». Сделать это эффективно (без лишнего прохода по контейнеру) можно только для структур данных, внутри которых находится массив (для std::list, std::deque работать не будет). Для вектора мы можем использовать min(it_min, it_max) и max(it_min, it_max), т.к. функции min и max могут работать с итераторами вектора. Однако, используя этот трюк мы потеряли ключевое преимущество итераторов — мы не можем теперь заменить один тип контейнера на другой. Однако, мучаемся с вот этими vec.begin(), vec.end(). Добавляет «красоты» в наш код функция next, которая вернет следующий за итератором итератор (то, что раньше записывалось как i = from+1). Итак, следующим фрагментом мы получили искомое произведение элементов:

    accumulate(
      next(min(minmax.first, minmax.second)), 
      max(minmax.first, minmax.second), 
      1, multiplies<int>()
    );

    Теперь надо получить сумму положительных чисел вектора. Что может быть проще? — опять используем accumulate. Очевидно, мы теперь не можем использовать готовую функцию (как выше использовали multiplies<int>()), но мы ведь можем написать свою функцию или лямбду и передать ее в accumulate, тут мы узнаем, что эта функция принимает не один аргумент, а два, узнаем почему:

    binary_op
    Binary operation taking an element of type T as first argument and an element in the range as second, and which returns a value that can be assigned to type T.

    Таким образом, accumulate работает скорее как foldl — такого рода функция есть в большинстве функциональных языков программирования. Эти детали очень важны, т.к. только понимая, что первый аргумент функции используется как «накопитель результата» (то, что было получено при обработке предыдущих элементов), а второй — текущий элемент контейнера, мы напишем корректную функцию для accumulate:

    accumulate(
      vec.begin(), vec.end(), 0, 
      [](const int &a, const int &b)->int {
        return b > 0 ? a + b : a;
    })

    Итак, исходный код программы целиком:

    #include <fstream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    int main() {
      ifstream ifst("input.txt");
      ofstream ofst("output.txt");
      int n;
      vector<int> vec;
      
      ifst >> n;
      vec.resize(n);
      for (int i = 0; i < n; ++i)
        ifst >> vec[i];
      
      auto minmax = minmax_element(vec.begin(), vec.end());
    
      ofst << accumulate(
          vec.begin(), vec.end(), 0, 
          [](const int &a, const int &b)->int {
            return b > 0 ? a + b : a;
          }) 
        << ' ' << accumulate(
          next(min(minmax.first, minmax.second)), 
          max(minmax.first, minmax.second), 
          1, multiplies<int>());
    }

    Стала ли она проще и понятней, чем первая? — думаю нет. При том, что эта задача просто идеально подходит для демонстрации стандартных алгоритмов.

Просмотр 1 сообщения - с 1 по 1 (всего 1)

Для ответа в этой теме необходимо авторизоваться.