В предыдущих главах мы рассмотрели основные типы данных (классы), которые Python предоставляет программисту для работы. Теперь несколько слов отдельно скажем об алгоритмах.
Алгоритм – конечный набор шагов, который требуется для выполнения задачи, например, алгоритм заваривания чая или алгоритм похода в магазин. Каждая функция в программе и каждая программа – это реализация определенного алгоритма, написанного на языке программирования.
К примеру, нам необходимо найти позицию наименьшего элемента в следующем наборе данных: 809, 834, 477, 478, 307, 122, 96, 102, 324, 476.
Первым делом выбираем подходящий для хранения тип данных. Очевидно, что это будет список:
Усложним задачу и попытаемся найти позицию двух наименьших элементов в не отсортированном списке.
Какие возможны алгоритмы решения?
- Поиск, удаление, поиск. Поиск индекса минимального элемента в списке, удаление его, снова поиск минимального, возвращаем удаленный элемент в список.
- Сортировка, поиск минимальных, определение индексов.
Перебор всего списка. Сравниваем каждый элемент по порядку, получаем два наименьших значения, обновляем значения, если найдены наименьшие
Рассмотрим каждый из перечисленных алгоритмов.
- Поиск, удаление, поиск: поиск индекса минимального элемента в списке, удаление его, снова поиск минимального, возвращаем удаленный элемент в список.
Начнем:
Удаляем из списка найденный минимальный элемент. При этом индексы в обновленном списке смещаются:
Возвращаем удаленный (первый минимальный) элемент обратно в список:
Не забываем о смещении индексов после удаления первого минимального элемента: индекс второго минимального элемента равен индексу первого минимального элемента, поэтому увеличим индекс второго минимального на 1.
Функция, реализующая данный алгоритм имеет вид:
2 Сортировка, поиск минимальных, определение индексов
Реализация второго алгоритма интуитивно понятна, поэтому приведу только исходный текст функции:
3. Перебор всего списка: сравниваем каждый элемент по порядку, получаем два наименьших значения, обновляем значения, если найдены наименьшие.
Третий алгоритм наиболее сложный из перечисленных выше, поэтому остановимся
на нем подробнее.
В отличие от человека, который может охватить взглядом сразу весь список и моментально сказать, какой из элементов является минимальным, компьютер не обладает подобным интеллектом. Машина просматривает элементы по одному, последовательно перебирая и сравнивая элементы.
На первом шаге просматриваем первые два элемента списка:
Сравниваем 809 и 834 и определяем наименьший из них, чтобы задать начальные значения min1 и min2, где будут храниться индексы первого минимального и второго минимального элементов соответственно
Затем перебираем элементы, начиная со 2-ого индекса до окончания списка:
Определили, что 809 – первый минимальный, а 834 – второй минимальный элемент из двух первых встретившихся значений списка.
Просматриваем следующий элемент списка (477):
Элемент 477 оказался меньше всех (условно назовем это «первым вариантом»):
Поэтому обновляем содержимое переменных min1 и min2, т.к. нашли новый наименьший элемент:
Рассматриваем следующий элемент списка (478):
Он оказался между двумя минимальными элементами (условно назовем это «вторым вариантом»):
Снова обновляем минимальные элементы (теперь обновился только min2)
И т.д. пока не дойдем до конца списка:
Исходный текст функции, реализующий предложенный алгоритм:
