Немного про алгоритмизацию и псевдокод
Алгоритмизация — очень важная штука в жизни программиста. Все владеют этим навыком на разном уровне, однако владеть базовыми вещами должен каждый.
Во многих книгах для алгоритмов используется особый язык — псевдокод.
Как мы видим, тут используются отступы, символ ∈ для перебора элементов множества и многое другое, что в обычных языках не увидишь. Однако если внимательно посмотреть, то многое станет понятным. Использовать псевдокод сегодня мы не будем, информация предоставлена для дополнительного понимания происходящего.
Что здесь будет происходить?
Существует куча алгоритмов, подходящих для определенной задачи. Сегодня мы посмотрим на три базовых алгоритма, о которых будет чуть позже.
Данная статья будет по такой схеме:
Задача
Основной принцип алгоритма
Реализация
Возможные улучшения
Надеюсь всё понятно, теперь поговорим о языке, который мы будем использовать.
Python
Для демонстрации работы таких алгоритмов в реальном языке программирования нам необходим очень понятный и интуитивно понятный синтаксис. Как вы уже поняли из названия, в качестве такого языка я выбрал Python. Объясню несколько вещей, которые могут быть непонятны тем, кто не работал с этим языком:
a, b = b, a — распаковка кортежа(в данном случае обмен значениями двух переменных).
for a in list: — перебор всех элементов массива(эквивалентно foreach в C#)
while a < b: — обычный цикл while(отличие в том, что условие может быть не скобках)
range(N) — все члены арифметической прогрессии с первым членом равным нулю, шагом равным единице и последним членом, равным N — 1.
a %= b — присваивание переменной a значения остатка при делении a / b.
Теперь к делу.
Алгоритм Евклида
Реализация
Задача: найти НОД(наибольший общий делитель) натуральных чисел a и b.
Ввод: a, b ∈ N.
Для этой задачи мы будем использовать алгоритм Евклида. Основная суть этого алгоритма:
НОД(a, b) = НОД(a % b, b)
Используем простой цикл с условием, что и a и b не равны нулю. Наибольшим делителем будет сумма a и b по окончанию цикла. Для грамотного оформления мы оформим алгоритм в виде функции для многоразового использования.
Т.к. b в определенный момент может стать больше a, при такой ситуации «свапаем» их значения.
Тестирование
Немного протестируем наш алгоритм. Для этого вручную создадим хэш-таблицу(dict) типа <a, b : НОД(a, b)>.
Выглядеть это всё дело будет примерно так:
Теперь оформим тестирование. Для этого воспользуемся форматированием строки.
Конструкция a, b = pair — распаковывает кортеж, присваивая переменной a значение pair[0], а переменной b — pair[1]. Далее подставляем все необходимые значения в строку и смотрим результат:
Все тесты наш алгоритм прошел, что не может не радовать. Теперь подумаем над улучшением нашего алгоритма.
Улучшение
Сейчас нам предстоит подумать над улучшением алгоритма. Мы можем убрать распаковку кортежа и просто через конструкцию if/else изменять числа. Выглядеть это будет так:
Заново протестируем наш алгоритм:
Результат всё тот же. Мы немного улучшили алгоритм и улучшили его читабельность(всё-таки распаковка кортежа может быть кому-то непонятна), при этом не повлияв на результат его работы.
Решето Эратосфена
Реализация
Задача: вывести все простые числа до натурального числа a(a > 2).
Ввод: a ∈ N
Для такой задачи возможно использование простого перебора, однако это будет неэффективно. Здесь мы будем использовать решето Эратосфена, подробное описание есть в Википедии(там даже есть интересная наглядная анимация работы этого алгоритма).
Для тех, кому лень читать, объясню кратко. Суть такова: мы создаем массив всех натуральных чисел от 2 до a по возрастанию. Затем мы берём каждый индекс i и приравниваем к нулю каждый элемент с индексом k*i(k = 1, 2, 3, …).
Здесь мы создаем маску, заполненную единицами(мы можем заменить 1 и 0 на True, False соответственно).
Далее работаем с индексами с помощью вложенного цикла. Здесь мы меняем значения в маске, а позже по маске осуществляем выбор элементов из массива. Для простоты пользуемся методом типа list — list.append().
Тестирование
По традиции, вручную создадим несколько тестов. Алгоритм довольно прост, потому нам понадобятся 3 наборa.
Также само тестируем алгоритм:
Получаем результат:
Улучшение
Если рассматривать пути улучшения, то можно убрать выбор по маске и воспользоваться возможностями языка в помощи очистки массива от полученных нулей. Получим нечто такое:
С помощью конструкции list(set()) мы очищаем массив от повторений. Затем удаляем лишний ноль и сортируем массив, из-за того, что set() не сохраняет порядок.
Однако такой метод мне не очень нравится, поскольку мы использовали слишком много особенных возможностей языка.
Бинарный поиск
Реализация
Задача: дан отсортированный массив натуральных чисел. Также дано число K. Установить номер позиции, куда необходимо вставить K, чтобы массив не перестал был отсортированным. Если в массиве встречаются числа, равные K, вставлять K следует перед ними.
Ввод: K ∈ N, arr : array;
Для этой задачи подойдёт и способ перебора, однако он имеет линейную сложность (O(N)), а бинарный поиск(тот самый алгоритм, который мы сейчас будем реализовывать) имеет логарифмическую сложность — O(log(N)).
Немного про О большое. Оценка сложности алгоритма служит для понимания, как будут увеличиваться затраты на вычисление в зависимости от изменения вводных данных. Например, если нам на ввод подается число N и для вычисления нам потребуется два цикла, один из которых вложенный, длиною N, то сложность алгоритма оценивается как O(N^2). Обычно константы в О-большом откидываются, ведь никак не влияют на результат(это только отчасти правда, иногда именно константы решают всё).
Именно поэтому существует запись log(N). Разложим log 2 (N) = log A (N) / log A (2), где A — любое число больше нуля и не равны единице. Т.к. log A (2) это константа, то её мы откидываем. Получаем log A (N). А так как A любое число, то мы просто пишем log(N).
Суть бинарного поиска — разделение массива на две части и путём сравнения откидывание одной из них.
Для нашей задачи алгоритм будет выглядеть примерно так:
Отбираем особый случай, когда массив пуст, а дальше ничего сложного.
Тестирование
Теперь мы случайно будем генерировать тестовые данные. Для этого воспользуемся генераторами(не будем вникать в тонкости их работы, просто расскажу, что делает фрагмент кода ниже).
Наш генератор принимает два параметра: N — кол-во возвращаемых массивов и l — их длину. Далее создаем массив с помощью спискового включения, и увеличиваем коэффициенты для следующего.
Теперь, по образцу, запускаем тестирование.
У меня вышло так:
Конечно же, у вас будут другие массивы, т.к. их мы генерируем с помощью random(не забудьте импортировать этот модуль в начале программы).
Насчет улучшения, то тут предоставлена стандартная реализация алгоритма, читабельная и понятная, потому пункт «Улучшение» мы пропустим.
Заключение
Сегодня мы реализовали три базовых алгоритма на языке Python. Вышло довольно неплохо, надеюсь полученные сегодня знания пригодятся вам в будущем. В этой статье переплетаются очень много тем, по которым можно написать отдельные материалы(например О-большое), так что можете попробовать найти интересную информацию об этом в интернете.
Весь код из статьи, разделенный по блокам, можете найти тут.
Также рекомендую прочитать статью Паттерн Декоратор (Decorator)
