Читать книгу Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию - Гейл Макдауэлл - Страница 25

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

Пять способов, приведенных далее, можно использовать по отдельности или вместе.

Попробуйте подход «Упростить и обобщить», а затем перейдите к «Сопоставлению с образцом».

Подход 1. Приводим пример

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

Пример: задано время, нужно рассчитать угол между часовой и минутной стрелками.

Давайте начнем, пусть исходное время – 3:27. Мы можем нарисовать циферблат, установить часовую стрелку на 3 часа, а минутную – на 27 минут.

Введем следующие обозначения: h – это часы, m – минуты. Предположим, что h может принимать значения в диапазоне от 0 до 23 включительно. Теперь можно сформулировать следующие правила:

• угол между минутной стрелкой и «полуднем»: 360 * m / 60;

• угол между часовой стрелкой и «полуднем»: 360 * (h % 12) / 12 + 360 * (m / 60) * (1 / 12);

• угол между часовой стрелкой и минутной: (угол часовой стрелки – угол минутной стрелки) % 360.

Окончательное выражение можно упростить до 30h – 5.5m.

Подход 2. Сопоставление с образцом

«Сопоставление с образцом» подразумевает, что мы сравниваем задачу с подобной и пытаемся приспособить алгоритм для нашего случая.

Пример. Отсортированный массив был циклически сдвинут так, что элементы оказались в следующем порядке: 3 4 5 6 7 1 2. Как найти минимальный элемент? Вы можете исходить только из предположения, что элементы в массиве не повторяются.

Существуют две задачи, которые можно рассматривать как аналог:

• Поиск минимального элемента в массиве.

• Поиск определенного элемента в сортированном массиве (бинарный поиск).

Поиск минимального элемента в массиве не самый интересный алгоритм – нужно пройтись по всем элементам. Вряд ли он будет полезен.

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

Если вы сравните средний и последний элементы (6 и 2), то узнаете, что точка сброса должна находиться между этими значениями (MID > RIGHT). Но это может произойти, только если массив сбрасывался между данными значениями.

Если MID меньше, чем RIGHT, значит, точка сброса находится в левой части массива, либо точки сброса не существует (массив отсортирован). Так или иначе, минимальный элемент находится там.

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

Подход 3. Упростить и обобщить

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

Пример. Требование о выкупе было склеено из вырезанных из газеты отдельных слов. Как проверить, что требование о выкупе (представленное в виде строки) было сделано с использованием конкретной газеты (строки)?

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

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

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

Подход 4. Базовый случай и сборка решения

Данный метод идеально подходит для решения целого ряда задач. Мы можем решить задачу для базового случая (n = 1). Это обычно означает запись корректного результата. Затем решить задачу для n=2, учитывая, что ответ для n=1 уже найден. Затем заняться случаем n=3, учитывая, что ответы для n=1 и n=2 известны.

В итоге мы можем построить решение, которое позволит найти результат для N, если известен правильный результат для N– 1. Каждый раз наше решение основывается на предыдущем результате.

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

Дана тестовая строка – abcdefg.

Случай "a" – > {"a"}

Случай "ab" – > {"ab", "ba"}

Случай "abc" – >?

Вот и первый «интересный» случай. Можем ли мы сгенерировать P("abc"), если у нас есть ответ P("ab")? Итак, у нас появляется дополнительная буква («c») и нам нужно вставить ее во все возможные позиции.

P("abc") = вставить "c" во все позиции для всех строк

P("ab") P("abc") = вставить "c" во все позиции для всех строк {"ab","ba"}

P("abc") = соединить ({"cab", "acb", "abc"}, {"cba", "bca", bac"})

P("abc") = {"cab", "acb", "abc", "cba", "bca", bac"}

Мы разобрались с шаблоном и можем разработать общий рекурсивный алгоритм. Сгенерируйте все перестановки строки s₁…s_n, удалив последний символ (для s₁…s_n-1).

Получив список всех перестановок s₁…s_n-1, последовательно пройдитесь по каждому элементу-строке списка, добавляя символ s_n в каждую позицию строки.

Данный подход позволяет создавать рекурсивные алгоритмы.

Подход 5. Мозговой штурм структур данных

Данный способ трудно назвать идеальным, но зачастую он срабатывает. Мы просто проходим по списку структур данных и пытаемся использовать каждую из них. Данный подход может оказаться полезным, поскольку в некоторых случаях решение задачи, что называется, «появится на поверхности», как только будет выбрана правильная структура данных (например, дерево).

Пример. Была сгенерирована и сохранена в массив последовательность случайных чисел. Как найти медиану?

Пытаемся устроить мозговой штурм и подобрать адекватную структуру данных:

• Связный список? Вероятно, нет. Связные списки плохо подходят для сортировки.

• Массив? Может быть, но у нас уже есть массив. Как хранить в нем отсортированные элементы? Это довольно сложно. Давайте отложим эту структуру данных и вернемся к ней при необходимости.

• Бинарное дерево? Вполне возможно, бинарные деревья подходят для задач сортировки. Мы можем попробовать усовершенствовать дерево бинарного поиска, а вершина будет медианой. Но будьте осторожны: число элементов может оказаться четным, а медиана окажется между двумя средними элементами. Два средних элемента не могут оказаться на вершине одновременно. Возможно, этот алгоритм подойдет, мы вернемся к нему позже.

• Куча? Куча – отличный способ для сортировки и отслеживания максимальных и минимальных значений. Это интересный выбор. Если у вас будет две кучи, можно следить за «большими» и «меньшими» частями элементов. «Большая» половина находится в min-куче, так что самый маленький элемент оказывается в вершине, а «меньшая» половина – в max-куче, так что в вершине – наибольший элемент. Такие структуры данных позволяют вам найти потенциальные медианы. Если размер куч изменился, можно повторно провести балансировку, выталкивая элементы из одной кучи в другую.

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