Представьте, что вы фермер, владеющий земельным участком.
Вы хотите равномерно разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно, так что ни одно из следующих решений не подойдет.
Как определить наибольший размер квадрата для участка? Воспользуйтесь стратегией «разделяй и властвуй»! Алгоритмы на базе этой стратегии являются рекурсивными.
Решение задачи методом «разделяй и властвуй» состоит из двух шагов:
1. Сначала определяется базовый случай. Это должен быть простейший случай из всех возможных.
2. Задача делится или сокращается до тех пор, пока не будет сведена к базовому случаю.
А теперь воспользуемся стратегией «разделяй и властвуй» для поиска решения этой задачи. Каков самый большой размер квадрата, который может использоваться?
Для начала нужно определить базовый случай. Самая простая ситуация — если длина одной стороны кратна длине другой стороны.
Предположим, длина одной стороны составляет 25 м, а длина другой 50 м. В этом случае размер самого большого участка составляет 25 м × 25 м, и надел после деления будет состоять из двух участков.
Теперь нужно вычислить рекурсивный случай. Здесь-то вам на помощь и приходит стратегия «разделяй и властвуй». В соответствии с ней при каждом рекурсивном вызове задача должна сокращаться. Как сократить эту задачу? Для начала разметим самые большие участки, которые можно использовать.
В исходном наделе можно разместить два участка 640 × 640, и еще останется место. Тут-то и наступает момент истины. Нераспределенный остаток — это тоже надел земли, который нужно разделить. Так почему бы не применить к нему тот же алгоритм?
Итак, мы начали с надела 1680 × 640, который необходимо разделить на участки. Но теперь разделить нужно меньший сегмент — 640 × 400. Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы. Мы только что сократили задачу с размера 1680 × 640 до 640 × 400!
Алгоритм Евклида
«Если вы найдете самый большой участок, подходящий для этого размера, это будет самый большой участок, подходящий для всей фермы». Если истинность этого утверждения для вас неочевидна, не огорчайтесь. Она действительно не очевидна. К сожалению, доказательство получится слишком длинным, чтобы его можно было бы привести в книге, поэтому вам придется просто поверить мне на слово. Если вас интересует доказательство, поищите «алгоритм Евклида». Хорошее объяснение содержится на сайте Khan Academy: https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm.
Применим тот же алгоритм снова. Если начать с участка 640 × 400, то размеры самого большого квадрата, который можно создать, составляют 400 × 400 м.
Остается меньший сегмент с размерами 400 × 240 м.
Отсекая поделенную часть, мы приходим к еще меньшему размеру сегмента, 240 × 160 м.
После очередного отсечения получается еще меньший сегмент.
Эге, да мы пришли к базовому случаю: 160 кратно 80. Если разбить этот сегмент на квадраты, ничего лишнего не останется!
Итак, для исходного надела земли самый большой размер участка будет равен 80 × 80 м.
Вспомните, как работает стратегия «разделяй и властвуй»:
1. Определите простейший случай как базовый.
2. Придумайте, как свести задачу к базовому случаю.
«Разделяй и властвуй» — не простой алгоритм, который можно применить для решения задачи. Скорее, это подход к решению задачи. Рассмотрим еще один пример.
Имеется массив чисел.
Нужно просуммировать все числа и вернуть сумму. Сделать это в цикле совсем не сложно:
def sum(arr):
total = 0
for x in arr:
total += x
return total
print sum([1, 2, 3, 4])
Но как сделать то же самое c использованием рекурсивной функции?
Шаг 1: определить базовый случай. Как выглядит самый простой массив, который вы можете получить? Подумайте, как должен выглядеть простейший случай, и продолжайте читать. Если у вас будет массив с 0 или 1 элементом, он суммируется достаточно просто.
Итак, с базовым случаем мы определились.
Шаг 2: каждый рекурсивный вызов должен приближать вас к пустому массиву. Как уменьшить размер задачи? Один из возможных способов:
В любом случае результат равен 12. Но во второй версии функции sum передается меньший массив. А это означает, что вы сократили размер своей задачи!
Функция sum может работать по следующей схеме:
А вот как это выглядит в действии.
Вспомните, что при рекурсии сохраняется состояние.
совет
Когда вы пишете рекурсивную функцию, в которой задействован массив, базовым случаем часто оказывается пустой массив или массив из одного элемента. Если вы не знаете, с чего начать, — начните с этого.
Пара слов о функциональном программировании
Зачем применять рекурсию, если задача легко решается с циклом? Вполне резонный вопрос. Что ж, пора познакомиться с функциональным программированием!
В языках функционального программирования, таких как Haskell, циклов нет, поэтому для написания подобных функций приходится применять рекурсию. Если вы хорошо понимаете рекурсию, вам будет проще изучать функциональные языки. Например, вот как выглядит функция sum на языке Haskell:
sum [] = 0 Базовый случай
sum (x:xs) = x + (sum xs) Рекурсивный случай
На первый взгляд кажется, что одна функция имеет два определения. Первое определение выполняется для базового случая, а второе — для рекурсивного случая. Функцию также можно записать на Haskell с использованием команды if:
sum arr = if arr == []
then 0
else (head arr) + (sum (tail arr))
Но первое определение проще читается. Так как рекурсия широко применяется в языке Haskell, в него включены всевозможные удобства для ее использования. Если вам нравится рекурсия или вы хотите изучить новый язык — присмотритесь к Haskell.
Упражнения
4.1 Напишите код для функции sum (см. выше).
4.2 Напишите рекурсивную функцию для подсчета элементов в списке.
4.3 Найдите наибольшее число в списке.
4.4 Помните бинарный поиск из главы 1? Он тоже относится к классу алгоритмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?
Быстрая сортировка
Быстрая сортировка относится к алгоритмам сортировки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Например, в стандартную библиотеку C входит функция с именем qsort, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии «разделяй и властвуй».
Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки (помните подсказку из предыдущего раздела)? Некоторые массивы вообще не нуждаются в сортировке.
Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде — сортировать ничего не нужно:
def quick sor t(array):
if len(array) < 2:
return array
Теперь перейдем к массивам большего размера. Массив из двух элементов тоже сортируется без особых проблем.
А как насчет массива из трех элементов?
Помните: мы используем стратегию «разделяй и властвуй». Следовательно, массив должен разделяться до тех пор, пока мы не придем к базовому случаю. Алгоритм быстрой сортировки работает так: сначала в массиве выбирается элемент, который называется опорным.
О том, как выбрать хороший опорный элемент, будет рассказано далее. А пока предположим, что опорным становится первый элемент массива.
Теперь мы находим элементы, меньшие опорного, и элементы, большие опорного.
Этот процесс называется разделением. Теперь у вас имеются:
• подмассив всех элементов, меньших опорного;
• опорный элемент;
• подмассив всех элементов, больших опорного.
Два подмассива не отсортированы — они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно.
Если бы подмассивы были отсортированы, то их можно было бы объединить в порядке «левый подмассив — опорный элемент — правый подмассив» и получить отсортированный массив. В нашем примере получается [10, 15] + [33] + [] = [10, 15, 33], то есть отсортированный массив.
Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!
quicksort([15, 10]) + [33] + quicksort([])
> [10, 15, 33] Отсортированный массив
Этот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.
Оба подмассива состоят из одного элемента, а вы уже умеете сортировать такие подмассивы. Получается, что вы умеете сортировать массивы из трех элементов. Это делается так:
1. Выбрать опорный элемент.
2. Разделить массив на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.
3. Рекурсивно применить быструю сортировку к двум подмассивам.
Как насчет массива из четырех элементов?
Предположим, опорным снова выбирается элемент 33.
Левый подмассив состоит из трех элементов. Вы уже знаете, как сортируется массив из трех элементов: нужно рекурсивно применить к нему быструю сортировку.
Следовательно, вы можете отсортировать массив из четырех элементов. А если вы можете отсортировать массив из четырех элементов, то вы также можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.