Разбор олимпиадной задачи — Нули

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 недели, 3 дня назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6403
      @admin

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

      Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц.

      Входные данные

      В единственной строке входного файла INPUT.TXT записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр от 1 до 100.

      Выходные данные

      В единственную строку выходного файла OUTPUT.TXT нужно вывести искомую длину цепочки нулей.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 00101110000110 4

      Разбор решения задачи

      Это простейшая задача на работу с файлами. Наиболее очевидный алгоритм ее решения:
      1. Считываем очередной символ — если это ‘0’ — увеличиваем счетчик, иначе — обнуляем счетчик.
      2. На каждой итерации сравниваем текущее значение счетчика с максимальным (при необходимости — обновляем максимальное).

      Реализация такого подхода:

      #include <fstream>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int maxLength = 0;
        int currentLength = 0;
      
        while (false == ifst.eof()) {
          if (ifst.get() == '0') {
            ++currentLength;
          }
          else {
            currentLength = 0;
          }
      
          if (currentLength > maxLength)
            maxLength = currentLength;
        }
      
        ofst << maxLength;
      }

      Что тут можно попробовать улучшить?:
      1) Минимизировать количество сравнений и присваиваний при вычислении максимума — можно поместить его либо в одну ветку условного оператора, либо в другую. В какую лучше — сильно зависит от входных данных, но чтобы минимизировать количество присваиваний — сравнение лучше делать пир достижении конца последовательности из нулей (ветка else).

      2) Можно улучшить код — применить std::max.

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

      #include <fstream>
      #include <algorithm>
      #include <string>
      
      using namespace std;
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string value;
        ifst >> value;
      
        long maxLength = 0;
      
        auto current_it = value.begin();
      
        while (current_it != value.end()) {
          current_it = find_if(current_it, value.end(), [](char c) { return c == '0'; });
          auto end_it = find_if(current_it, value.end(), [](char c) { return c != '0'; });
      
          auto currentLength = distance(current_it, end_it);
      
          maxLength = max(currentLength, maxLength);
      
          current_it = end_it;
        }
      
        ofst << maxLength;
      }
      

      Стало ли лучше? — не очевидно.

      4) Можно попробовать применить файловые итераторы — практика полезная, но особого резульата это не даст, так как к istream_iterator нельзя применить алгоритм distance, а значит — для определения длины последовательности из нулей придется определять текущую позицию в файле (функцией istream.tellg()). Код точно станет менее понятным.

      Это редкий пример задачи, где лучшее (наиболее хорошо читаемое) решение получается с минимальным использованием стандартной библиотеки.

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