Теоретический минимум по Computer Science

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

как справляться с повторяющимися задачами посредством итераций;

как изящно выполнять итерации при помощи рекурсии;

как использовать полный перебор;

как выполнять проверку неподходящих вариантов и возвращаться на шаг назад;

как экономить время при помощи эвристических алгоритмов, помогающих найти разумный выход;

как применять принцип «Разделяй и властвуй» к самым неподатливыми противникам;

как динамически идентифицировать уже решенные задачи, чтобы снова не тратить на них энергию;

как ограничивать рамки задачи.

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

3.1. Итерация

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

Объединение списков рыб У вас есть списки морских и пресноводных рыб, оба упорядочены в алфавитном порядке. Как создать из них один общий список, тоже отсортированный по алфавиту?

Мы можем сравнивать в цикле верхние элементы двух списков (рис. 3.1).

Данный процесс можно записать в виде одного цикла с условием продолжения while loop:

function merge(sea, fresh)

····result ← List.new

····while not (sea.empty and fresh.empty)

········if sea.top_item > fresh.top_item

············fish ← sea.remove_top_item

·······else

···········fish ← fresh.remove_top_item

·····result.append(fish)

return result

Рис. 3.1. Объединение двух отсортированных списков в третий, тоже отсортированный

Он выполняет обход всех названий рыб из входных списков, совершая фиксированное число операций для каждого элемента[28]. Следовательно, алгоритм слияния merge имеет сложность O(n).

Вложенные циклы и степенные множества

В предыдущей главе мы увидели, как функция сортировки выбором selection_sort использует один цикл, вложенный в другой. Сейчас мы научимся использовать вложенный цикл для вычисления степенного множества. Если дана коллекция объектов S, то степенное множество S есть множество, содержащее все подмножества S[29].

Исследование запахов В парфюмерии цветочные ароматы изготавливают путем комбинирования запахов различных цветов. Если дано множество цветов F, то как посчитать все ароматы, которые можно изготовить из них?

Любой аромат состоит из подмножества F, потому его степенное множество содержит все возможные ароматы. Это степенное множество вычисляется итеративно. Для нулевого множества цветов есть всего один вариант — без запаха. В случае, когда мы берем очередной цветок, мы дублируем уже имеющиеся ароматы и добавляем его к ним (рис. 3.2).

Этот процесс можно описать при помощи циклов. Во внешнем цикле мы принимаем решение, какой цветок будем рассматривать следующим. Внутренний цикл дублирует ароматы и добавляет новый цветок к этим копиям.

function power_set(flowers)

····fragrances ← Set.new

····fragrances.add(Set.new)

····for each flower in flowers

········new_fragrances ← copy(fragrances)

········for each fragrance in new_fragrances

············fragrance.add(flower)