Как решать алгоритмические задачи

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

В этом уроке вы узнаете основы этого процесса, без которых сложно освоить остальные темы курса.

Часто можно встретить мнение: «Я прочитаю условие задачи, потом посмотрю каноничное решение и запомню его». Увы, так не работает. В поведенческой экономике есть такое понятие, как «Эффект Икеа». Люди ценят больше то, к созданию чего приложили руку и много усилий. То же самое и с алгоритмическими задачами — мы ценим и лучше запоминаем те, которые придумали, а иногда выстрадали сами. Время, проведённое за решением, поможет в дальнейшем легче находить паттерны в новых задачах. Воспринимайте сложности в процессе решения задач как вызов, который сделает вас ощутимо сильнее.

Есть ещё одна ловушка, в которую часто попадают разработчики.

«Да что тут сложного, всё понятно, пойду сразу запрограммирую». Дальше происходит ситуация, знакомая многим. Разработчик пишет код, запускает, а он выдаёт ошибку. Ошибка простая и понятная. Он её исправляет. Затем вылезает новая, которую исправить не так просто. Через несколько итераций код превращается в чудовище Франкенштейна, где некоторые части исправлены только потому, что а вдруг ошибка именно тут.

Изначально на всю задачу разработчик выделял 20 минут. Фактически ушло 4 часа. Злость и разочарование. Вроде осталось совсем чуть-чуть поправить, чтобы заработало. Впрочем, то же самое было и 3,5 часа назад.

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

Последовательность решения алгоритмических задач

1. Внимательно прочитайте условие задачи:

• зафиксируйте, что нужно найти;
• отметьте все особенности входных данных;
• ознакомьтесь с лимитами по времени и памяти.

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

2. Придумайте примеры входных данных и зарисуйте, если это возможно. В задачах нашего курса всегда будет пара примеров для понимания условия. Допишите ещё и ответьте на вопрос: «Достаточно ли примеров получилось?» О том, как придумывать хорошие тесты, поговорим подробнее в одном из следующих уроков.
3. На примерах разберите, как вы находили бы ответ на заданный вопрос, если бы вам потом не надо было писать код. Подумайте, какой результат работы своей программы вы ожидаете при обработке каждого набора входных данных. Запишите, как именно находите ответ, какие формулы используете для промежуточных вычислений. Возможно, вы делите входные данные друг на друга, сортируете массив или вычисляете какие-то вспомогательные данные?

Правильный результат на этом этапе — решение, которое легко объяснить школьнику. В нём не встречаются сложные слова и высокоуровневые абстракции.

Алгоритм, который первым приходит на ум, называется наивным. Во многих случаях он будет неоптимальным. Не пропускайте формулирование наивного алгоритма, даже если вы понимаете, что он работает очень медленно. Подумайте, чем конкретно плох алгоритм. Он работает медленно? Ему требуется много дополнительной памяти?

Часто бывает так, что придумать алгоритм не получилось. На этот случай есть 5 советов, как подступиться к задаче:

• Предположите, какие дополнительные ограничения бы вам помогли. Если в задаче дана последовательность произвольных чисел, попробуйте решить задачу, например, для последовательности только из целых чисел, а потом переходите к вещественным числам.
• Попробуйте решить задачу для входных данных небольшого размера. Например, 3 числа в последовательности вместо 200.
• Подумайте, можете ли вы разбить задачу на подзадачи меньшего размера. Например, если у вас есть массив длины n и требуется найти максимальный элемент, что будет, если поделить массив на две равные части? Зная ответ для каждой половины, можно ли получить ответ для целого массива? А если просто убрать один элемент? Аналогично можно работать и с числами, и со строками, обрезать и делить их, находить решение для меньшей задачи, после чего пытаться перейти от решения на меньшем объёме входных данных к решению на большем объёме.
• Предположите, какие из известных вам алгоритмов и структур данных могут помочь в решении задачи. Пока мы будем учиться, задачи будут соответствовать темам из спринта. Чтобы после обучения было удобно пользоваться этим методом, заведите список пройденных тем. Собственный конспект — лучшая подсказка.
• Возьмите какое-то решение, пусть даже вы не уверены в его правильности. Проверьте его на примерах, которые вы придумали. В каких ситуациях ваш алгоритм даст неправильные ответы? Проанализировав неправильное решение, можно найти и исправить ошибки.

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

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

4. Оцените сложность, с которой работает ваш наивный алгоритм. Проверьте, это достаточно хорошая сложность с учётом известных ограничений на входные данные или лимиты не покорятся? Попробуйте обосновать, какая асимптотика вашего алгоритма.
5. Оптимизируйте! Подумайте, как можно улучшить свой алгоритм. Есть несколько способов:

• Bottleneck или Бутылочные горлышко. Как мы уже говорили, так называют самое узкое место программы. Это та часть, которая работает дольше всего. Если у вас есть часть кода, которая работает за квадратичное время, а весь остальной код — за линейное, ищите, можно ли ускорить квадратичную часть. Ведь небольшие изменения в линейной части не дадут асимптотических преимуществ и в большинстве случаев ускорят программу незначительно.

• Повторяющаяся работа. Например, вам надо ответить на один и тот же вопрос для 10 разных элементов массива. Вы знаете, что ответ можно быстро найти на отсортированном массиве. Лучше отсортировать массив один раз в начале, чем делать это каждый раз для каждого из 10 элементов. Чтобы заметить повторяющиеся действия, ищите одинаковые куски кода и внимательно посмотрите все инструкции, которые выполняются в теле каждого цикла вашей программы. Может быть, некоторые инструкции стоит вынести за пределы цикла.
• Ненужные действия. Иногда сортировать не нужно. Например, программе на вход подаются числа и надо найти наименьшее число. Можно массив отсортировать и выдать первый элемент, а можно в процессе считывания перевыбирать минимум. Или вам надо сложить числа в двоичной системе счисления — тогда ни к чему переводить числа в десятичную систему счисления, а потом сумму обратно в двоичную. Проверьте, нет ли у вас лишних действий.
• Оптимальные структуры данных. Ответьте на вопрос, какие операции с данными предстоит осуществлять? Какая структура данных позволит сделать это быстро, без лишних издержек? Может быть, вы хотите быстро узнавать, есть ли элемент в вашем наборе данных, но используете для этого массив?
• Подумайте, всю ли информацию из условия задачи вы уже применили. Может, есть ограничение, которое вы проигнорировали в наивном решении. Перечитайте условие ещё раз.
• Ищите компромисс между памятью и временем. В задачах контеста у вас будет два типа ограничений: на дополнительную память и на время выполнения программы. Иногда мы можем ускорить программу, сохранив промежуточную информацию. В других случаях, как в задаче про счастливые билеты, лучше сэкономить память.

6. Напишите аккуратный код.

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

Часто так пишут рецепты:

Почистите картофель и морковку
Картофель нарежьте кубиками
Морковку нарежьте кружочками
Пробланшируйте овощи
Выложите овощи на тарелку

Первые три пункта понятны, вы можете выполнить их и без подсказок. Но если вы раньше не увлекались готовкой, возможно, нужно уточнить, что означает слово «пробланшировать». В роли уточнения выступает реализация функции, в которой описывается детальная последовательность действий. Если же на кухне вы как рыба в воде, то рецепт понятен по этим пяти строчкам. Вы можете не читать вспомогательный текст. Такая понятность достигается благодаря качественному подбору слов для сокращённого рецепта. Так же и с программой — должна быть возможность прочитать «короткий рецепт» для профи и уточнить реализацию сложных мест.

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

7. Внимательно перечитайте написанный код. Особое внимание уделите:

• условным выражениям; иногда можно перепутать знаки < и > или неаккуратно объединить несколько логических условий, забыв о порядке применения отрицания, логического И и ИЛИ.
• условиям выхода из циклов или функций; правильно ли обрабатывается первый и последний элемент? Есть ли ситуации, когда мы выходим из цикла досрочно?
• константам; Вы точно помните, зачем каждая из них нужна? Всегда ли это значение одинаковое?

8. Протестируйте свой код.