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

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

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

Итеративная стратегия состоит в использовании циклов (например, 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, потому его степенное множество содержит все возможные ароматы. Это степенное множество вычисляется итеративно. Для нулевого множества цветов есть всего один вариант — без запаха. В случае, когда мы берем очередной цветок, мы дублируем уже имеющиеся ароматы и добавляем его к ним (рис. 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)