Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих (страница 9)
Применим тот же алгоритм снова. Если начать с участка 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.