
Алгоритмы (теория/практика): Часть 2. Что такое алгоритм?
- Алгоритмы (теория/практика): Часть 1. Введение
- Алгоритмы (теория/практика): Часть 2. Что такое алгоритм?
- Алгоритмы (теория/практика): Часть 3. Сложность алгоритмов
- Алгоритмы (теория/практика): Часть 4. Начинаем анализировать
- Алгоритмы (теория/практика): Часть 5. Корректность алгоритмов
- Алгоритмы (теория/практика): Часть 6.1. "Разделяй и властвуй"
- Алгоритмы (теория/практика): Часть 6.2. «Разделяй и властвуй» (продолжение)
Я хочу сделать этот цикл статей максимально полным. Таким, чтобы у читателя не возникла необходимость дополнительно искать информацию. Всё новое, что вводится в каждой статье, будет дополняться определениями и комментариями. Если определение небольшое, то я буду выносить его в блок «примечание», всё остальное же буду описывать прямо в тексте статьи.
Первое, с чего мы начнем, это определение того самого понятия, с которым нам предстоит работать. Алгоритмом в информатике называют последовательность четко и однозначно определенных инструкций, следуя которым, исполнитель способен за конечное число шагов достичь результата решения задачи.
Если речь идёт о вычислительных алгоритмах, то определение можно записать в альтернативной форме: алгоритм — последовательность четко и однозначно определенных инструкций, следуя которым, исполнитель способен за конечное число шагов решить задачу по преобразованию входных данных в выходные.
Давайте посмотрим на пример из жизни.
Несмотря на то, что в наше время уже повсеместно распространена электронная почта, а также всевозможные мессенджеры, которые позволяют обмениваться сообщения, что называется, в режиме реального времени, некоторые люди до сих пор пишут настоящие «бумажные» письма и отправляют их самой обычной почтой. Кто-то считает, что такие письма, написанные от руки, более личные, чем их современные аналоги, более эмоциональные, кто-то просто хочет удивить своего собеседника таким необычным жестом. Это не так важно, но если вы задумали сделать это, то вот вам примерный план действий:
- Первым делом, вам нужно приобрести конверт.
- Дальше вам нужно взять чистый лист бумаги.
- После чего следует написать письмо.
- После этого вложите ваш лист с текстом в конверт.
- Далее напишите адрес на конверте и наклейте марки.
- В самом конце вам нужно дойти до почты и бросить письмо в урну, либо отдать его сотруднику почты.
Те действия, которые я сейчас написал, являются алгоритмом. Они достаточно четко объясняют вам, как исполнителю, что нужно сделать и какое действие нужно выполнить после очередного шага.
Конечно, у подобного алгоритма есть проблемы. Например, недостаточная точность инструкций: что именно писать, кому отправлять, где купить конверт, сколько марок нужно приклеить? Из-за того, что инструкции определены недостаточно точно, мы можем иметь бесконечное множество решений поставленной задачи. Разумеется, это не есть хорошо, так как исполнитель должен получить настолько точное описание задачи, насколько это возможно.
Я понимаю, что это пример уровня начальной школы. Во всяком случае, я показал сущность, которую с полной уверенностью можно назвать алгоритмом. Давайте теперь акцентируем внимание на основных свойствах алгоритмов:
- Дискретность. Большая задача разбивается на элементарные шаги, причём каждый последующий шаг начинается только после того, как были завершены все предыдущие.
- Определенность. При интерпретации каждой взятой инструкции, компьютер должен получить исчерпывающие сведения о своей задаче на данном этапе. Двусмысленность в информатике не приветствуется. Если вызвать один и тот же алгоритм для одних и тех же данных 1000 раз, мы должны 1000 раз получить один и тот же результат.
- Результативность. Исполнитель либо решает поставленную задачу за конечное число шагов, либо останавливается, если задачу решить невозможно.
- Универсальность (массовость). Массовость предполагает наличие целого класса входных данных, которые могут быть корректно преобразованы в выходные. Например, алгоритм, который возводит переданное ему число в квадрат должен работать со всеми числами. Не имеет смысла делать алгоритм, который возводит в квадрат только число 2.
Алгоритм, описанный выше — это пример линейного алгоритма. Линейный алгоритм, самый простой из всех, является простой последовательностью команд идущих друг за другом. Интуиция подсказывает, что при помощи линейных алгоритмов будет проблематично писать крупные программы, ибо для каждого изменения или нового типа входных данных нужно будет переписывать львиную часть логики.
Для того, чтобы определить то, как исполнителю нужно реагировать при определенных обстоятельствах, можно использовать ветвящийся алгоритм (или разветвленный алгоритм). Такой вид алгоритмов предполагает условие, которое может выполняться или нет и от которого будет зависеть дальнейший шаг исполнителя.
Представьте, что у вас в руках есть колода карт, причём некоторые карты в ней расположены рубашкой вверх, а некоторые наоборот. И вам нужно перебрать их всех и расположить карты так, чтобы все их них были расположены рубашкой вверх. В зависимости от расположения конкретной карты вы будете принимать решение — оставить её в том же виде, либо перевернуть.
При помощи комбинаций операторов ветвления можно создавать более сложные условия с большим количеством возможных исходов.
Если вам нужно повторить некоторую процедуру несколько раз, то вместо того, чтобы переписывать один и тот же код, можно воспользоваться циклическим алгоритмом. В некотором роде, циклический алгоритм очень похож на ветвящийся, так как он тоже предполагает некоторое условие, которое выполняется или нет. Единственное, что в циклическом алгоритме условие определяет не дальнейшие действия, а ту процедуру (или несколько), которые должны быть выполнены повторно.
Вернёмся к письмам. Допустим вы хотите написать ровно 10 писем своим родственникам и друзьям. Вместо того, чтобы прописывать алгоритм для каждого письма, лучше поставить условие и выполнять один и тот же алгоритм столько раз, сколько потребуется. Условием будет написание 10 писем. Тогда после завершения очередного, вы будете спрашивать себя: «Я написал(а) 10 писем?». Если нет — то выполнить пункты 2-5 еще раз, если же да — отложить ручку и выполнить пункт 6.
Самым распространенным видом алгоритмов, который не все выделяют в отдельный, является смешанный алгоритм. Смешанный алгоритм, как следует из названия, сочетает в себе все три типа алгоритмов и именно такие алгоритмы используются на практике чаще всего.
Внимательность: нужно понимать, что понятия алгоритм и программа неравнозначны. Алгоритм – это, грубо говоря, абстрактное описание того, что нужно сделать, не предназначенное для конкретного исполнителя. Алгоритм не учитывает конкретных особенностей исполнителя, а существует в некотором «вакууме», где железо бывает бесконечно быстрым, а память безгранична. Программа же – это совокупность алгоритмов и данных, написанная на определенном языке программирования и предназначенная уже для конкретного исполнителя.
В рамках данного цикла мы будем использовать формальную запись на языке C++. Тем не менее, если вы не знакомы с C++, то не стоит закрывать вкладку и уходить. Реализации многих алгоритмов (по крайней мере, на начальном этапе) довольно просты и у вас не возникнет сложностей в понимании сути того, что происходит. К тому же, я буду сопровождать код довольно подробными пояснениями (не комментариями). Однако я не ставлю своей задачей научить вас программировать и предполагаю, что вы понимаете базовые вещи, такие как переменные, операторы, функции и т.д.