Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - [14]
Итак, мы начали с надела 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, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии «разделяй и властвуй».
Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки (помните подсказку из предыдущего раздела)? Некоторые массивы вообще не нуждаются в сортировке.
Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде — сортировать ничего не нужно:
