Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - [11]
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
Теперь на основе этой функции можно написать функцию сортировки выбором:
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
Шпаргалка
• Память компьютера напоминает огромный шкаф с ящиками.
• Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.
• В массиве все элементы хранятся в памяти рядом друг с другом.
• В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего элемента.
• Массивы обеспечивают быстрое чтение.
• Списки обеспечивают быструю вставку и выполнение.
• Все элементы массива должны быть однотипными (только целые числа, только вещественные числа и т.д.).
3. Рекурсия
В этой главе
• Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.
• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.
Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:
• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.
• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.
В этой главе также приводится большое количество псевдокода. Псевдокод представляет собой высокоуровневое описание решаемой задачи. Он записывается в форме, похожей на программный код, но в большей степени напоминает естественный язык.
Рекурсия
Допустим, вы разбираете чулан своей бабушки и натыкаетесь на загадочный запертый чемодан.
Бабушка говорит, что ключ к чемодану, скорее всего, лежит в коробке.
В коробке лежат другие коробки, а в них лежат маленькие коробочки. Ключ находится где-то там. Какой алгоритм поиска ключа предложите вы? Подумайте над алгоритмом, прежде чем продолжить чтение.
Одно из решений может выглядеть так:
1. Сложить все коробки в кучу.
2. Взять коробку и открыть.
3. Если внутри лежит коробка, добавить ее в кучу для последующего поиска.
4. Если внутри лежит ключ, поиск закончен!
5. Повторить.
Есть и альтернативное решение.
1. Просмотреть содержимое коробки.
2. Если вы найдете коробку, вернуться к шагу 1.
3. Если вы найдете ключ, поиск закончен!
Какое решение кажется вам более простым? Первое решение можно построить на цикле while. Пока куча коробок не пуста, взять очередную коробку и проверить ее содержимое:
def look_for_key(main_box):
pile = main_box.make_a_pile_to_look_through()
while pile is not empty:
box = pile.grab_a_box()
for item in box:
if item.is_a_box():
pile.append(item)
elif item.is_a_key():
print "found the key!"
Второй способ основан на рекурсии. Рекурсией называется вызов функцией самой себя. Второе решение на псевдокоде может выглядеть так:
def look_for_key(b ox):
for item in box:
if item.is_a_box():
look_for_key(item)
elif item.is_a_key():
print "found the key!"
Оба решения делают одно и то же, но второе решение кажется мне более понятным. Рекурсия применяется тогда, когда решение становится более понятным. Применение рекурсии не ускоряет работу программы: более того, решение с циклами иногда работает быстрее. Мне нравится одна цитата Ли Колдуэлла с сайта Stack Overlow: «Циклы могут ускорить работу программы. Рекурсия может ускорить работу программиста. Выбирайте, что важнее в вашей ситуации!»[2]
Рекурсия используется во многих нужных алгоритмах, поэтому важно понимать эту концепцию.
Базовый случай и рекурсивный случай
Так как рекурсивная функция вызывает сама себя, программисту легко ошибиться и написать функцию так, что возникнет бесконечный цикл. Предположим, вы хотите написать функцию для вывода обратного отсчета:
> 3...2...1
Ее можно записать в рекурсивном виде:
def countdown(i):
print i
countdow n(i-1)
Введите этот код и выполните его. И тут возникает проблема: эта функция выполняется бесконечно!
Бесконечный цикл
> 3...2...1...0...-1...-2...
Чтобы прервать выполнение сценария, нажмите Ctrl+C.
