Практика: алгоритмы и стандартная библиотека C++

В последнее время тут редко появляются посты, так как мы пытаемся количество перевести в качество. В частности:

  1. из разрозненных материалов по С++ собираем что-то типа учебника для начинающих (сейчас готовы только первые 4 урока);
  2. учебник для продолжающих должен содержать наиболее актуальную информацию, но такая информация встречается только на конференциях. Собирая материалы мы пишем аннотации и краткие содержания к наиболее интересным докладам с конференций — пока что они выкладыюватся только в нашем сообществе ВКонтакте, но в будующем мы их причешем (структурируем) и выложим тут в виде статьи-учебника;
  3. учебник — это хорошо, но чтобы научиться программировать — нужно программировать (решать много задач). Мы взяли в качестве примеров олимпиадные задачи (сейчас по ссылке вы найдете ровно 100 разобранных задач). Эти задачи структурированы по темам и тегам. Однако, мы решили выбрать наиболее интересные (и полезные) задачи — о них и написано в этой статье.

Как олимпиадные задачи, так и наши решения к ним, обладают рядом особенностей:

  • суть олимпиадного программирования заключается в поиске и быстрой реализации оптимального решения к задаче. Критерии оптимальности — память и время. Поэтому чтобы в полной мере понять проблемы и решения — посмотрите хотя бы эту, а лучше еще и вот ту статью про анализ алгоритмов. Это важно, так как ко многим задачам мы приводим по 3-4 решения с различной вычислительной сложностью;
  • на олимпиадах надо быстро написать решение (ведь тикает таймер). Поэтому качество исходного кода у олимпиадников часто страдает (про это даже байки ходят). Однако, мы ведь пишем учебник и учим как делать хорошо. Часть наших решений отличается качеством кода, чтобы понять что это, загляните в статьи «Теория чистого кода«, «SOLID принципы«;
  • если мы пишем хороший код на С++ — значит стараемся не изобретать велосипеды и на полную катушку использовать стандартную библиотеку (STL), которая содержит не только контейнеры. Перед тем как смотреть решения мы рекомендуем попробовать пройти небольшие тесты: тест про std::vector, тест про std::list.

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

1 Практика для начинающих

  1. «Метро» — задача на логику, с нее хорошо начать свой путь в спортивном программировании. Для решения задачи вам нужно освоить тему «Ветвеление«, и уметь работать с файлами (хотя бы «по образцу»).
  2. «Сжимающий оператор» — простейшая задача на геометрию, а также прекрасный пример для иллюстрации проблемы потери точности при работе с дробными числами.
  3. «Загадка» — хорошая задача для первой практики в анализе сложности алгоритмов — приводятся три варианта решения с оценками сложности O(n*n), O(n) и O(1). Разбирая задачу — подумайте о том, какие максимальные значения можно подать на вход первого решения, второго и третьего.
  4. «Кругляши» — демонстрация улучшения кода за счет применения стандартных алгоритмов STL. Мы пишем меньше кода, а значит — допустим меньше ошибок. Один из простейших примеров использования алгоритмов с итераторами файловых потоков — это очень удобно, но студенты почему-то не пользуются, поэтому — акцентирую внимание.
  5. «Арбузы» — еще один пример рефакторинга и использования стандартных алгоритмов STL. Стоит заметить, что второй вариант решения более понятный, а третий — более эффективный. Проблема выбора между чистотой кода и эффективностью постоянно возникает при программировании, ее описывали Маерс и Саттер — чаще всего стоит выбирать наиболее простое решение, обратное часто называется «Преждевременной оптимизацией«.
  6. «Нули» — в этой задаче вы можете применить алгоритмы STL, однако решение от этого, скорее всего, станет более запутанным — это хороший пример неудачного рефакторинга.
  7. Для закрепления навыков работы с STL можно порешать ряд других несложных задач:
    1. «Домашнее задание» — vector, minmax_element, accumulate.
    2. «Линии Жизни» идиома Erase-remove, алгоритмы count и unique.
    3. «Азартный Шрэк«- vector, sort, accumulate.
    4. «Автобусная экскурсия» — алгоритм copy с итераторами файловых потоков, find_if и distance.
    5. «Перепись» — использование алгоритма copy для считывания структур (с перегрузкой оператора потокового ввода).

2 Анализ сложности и структры данных

  1. «Коммерческий калькулятор» — одна из наиболее интересных задач в этом обзоре — как с точки зрения алгоритма, так и разнообразия решений. В решениях используются vector и алгоритм partial_sort; multiset и специфический алгоритм вставки в multiset «with hint»; наиболее эффективный и неочевидный вариант с использованием std::map.
  2. «Волосатый бизнес» — как и в предыдущей задаче, тут надо найти и запрограммировать «оптимальную стратегию поведения». Из элементов станартной библиотеки в решениях используются: vector, max_element, distance; multiset; map.
  3. «Секретное сообщение» — в решении, помимо std::map и std::vector, описывается специфическая структура данных «битовая карта».
  4. «Сотовая связь в большом городе» — хорошая задача для понимания выгоды, которую можно извлечь из хранения данных в упорядоченном виде. В решении используется std::map, реализующий сбалансированное дерево поиска (в статье по ссылке описаны различные древовидные структуры). Кроме того, в решении используются алгоритмы distance и count_if.
  5. «Проверка орфографии — 2» — эту здаачу решит даже начинающий программист, освоивший тему «Строки», однако решение вряд ли будет «чистым». Из этой статьи можно узнать как элегантно заставить стандартный оператор >> игнорировать при вводе некоторые символы — делается это через конфигурацию локали. Также в этой задаче можно попрактиковаться со стандартной бибилотекой — в решении используются std::map, а также алгоритмы copy, replace_if, transform, идиома Erase-Remove.

3 Динамическое программирование

Задачи на тему динамического программирования часто имеют очень простое, но неэффективное решение. Техника динамического программирования позволяет сократить количество «перебираемых» вариантов решения за счет сохранения некоторых результатов, полученных на предыдущих шагах. Таким образом, это техника оптимизации.

Во всех приведенных ниже задачах, сначала описывается неэффективное решение и визуализируется «что именно вычисляется повторно», а затем — показывается как его оптимизировать:

  1. «Компьютерная игра» — помимо динамического программирования приведенные решения могут быть интересны как примеры рефакторинга и «преждевременной оптимизации».
  2. «Игра — 2» — целью является поиск оптимальной стратегии игры, однако игровые ситуации могут многократно повторяться.
  3. «Фермер» — чуть более сложная задача, применение динамики тут менее очевидно. Также, это хороший пример для анализа вычислительной сложности — первое предложенное решение можно оценить как O(n^5) по памяти, а наиболее эффективное — O(n^2).

Добавить комментарий

×