1.1   Алгоритмы повсюду¶

Говоря об алгоритмах, естественно вспомнить о математике. Однако на самом деле многие алгоритмы не связаны со сложной математикой, а больше полагаются на базовую логику, которая повсеместно встречается в нашей повседневной жизни.

Прежде чем углубиться в обсуждение алгоритмов, стоит упомянуть интересный факт: вы уже точно освоили множество алгоритмов и привыкли применять их в повседневной жизни. Далее приведем несколько конкретных примеров, чтобы подтвердить этот факт.

Пример 1: поиск в словаре. В словаре все слова упорядочены по алфавиту. Предположим, нам нужно найти слово, начинающееся на букву \(r\). Обычно это делают так, как показано на рисунке 1-1.

1. Откройте словарь примерно на половине страниц и посмотрите, какая буква является первой на этой странице. Предположим, это буква \(m\).
2. Поскольку в алфавите буква \(r\) идет после \(m\), исключаем первую половину словаря, и область поиска сужается до второй половины.
3. Продолжайте повторять шаги 1. и 2. , пока не найдете страницу, где первой буквой слов будет \(r\).

Рисунок 1-1   Этапы поиска в словаре

Навык поиска в словаре, которым владеет каждый школьник, на самом деле является известным алгоритмом двоичного поиска. С точки зрения структуры данных словарь можно рассматривать как отсортированный массив. С точки зрения алгоритма последовательность операций по поиску в словаре можно считать двоичным поиском.

Пример 2: упорядочивание карт. Во время игры в карты необходимо каждый раз упорядочивать карты в руке от меньшего к большему. Обычно это делают так, как показано на рисунке 1-2.

1. Разделите карты на упорядоченную и неупорядоченную части, предполагая, что изначально самая левая карта уже упорядочена.
2. Из неупорядоченной части извлеките одну карту и вставьте ее в правильное место в упорядоченной части. После этого две самые левые карты станут упорядоченными.
3. Повторяйте шаг 2. , каждый раз перемещая одну карту из неупорядоченной части в упорядоченную, пока все карты не станут упорядоченными.

Рисунок 1-2   Этапы упорядочивания карт

Метод упорядочивания карт по своей сути является алгоритмом сортировки вставками, который весьма эффективен при обработке небольших наборов данных. Многие функции сортировки в библиотеках программирования используют именно этот алгоритм.

Пример 3: сдача. Предположим, что в супермаркете мы купили товар стоимостью \(69\) руб. и дали кассиру купюру в \(100\) руб. Кассир должен вернуть нам \(31\) руб. Обычно он рассуждает так, как показано на рисунке 1-3.

1. Варианты выбора - это купюры номиналом меньше \(31\) руб. Пусть у нас имеются номиналы \(1\) , \(5\) , \(10\) и \(20\) руб.
2. Возьмем самую крупную доступную купюру в \(20\) руб. Остаток сдачи составит \(31 - 20 = 11\) руб.
3. Возьмем самую крупную из оставшихся купюр в \(10\) руб. Остаток составит \(11 - 10 = 1\) руб.
4. Возьмем самую крупную из оставшихся купюр в \(1\) руб. Остаток составит \(1 - 1 = 0\) руб.
5. Завершим выдачу сдачи, схема: \(20 + 10 + 1 = 31\) руб.

Рисунок 1-3   Этапы выдачи сдачи

В этих шагах мы на каждом этапе выбираем наилучший вариант, используя купюры наибольшего номинала, и в итоге получаем рабочую схему сдачи. С точки зрения структуры данных и алгоритмов этот метод по своей сути является жадным алгоритмом.

От приготовления блюда до межзвездных путешествий решение практически любой задачи неразрывно связано с алгоритмами. Появление компьютеров позволило нам с помощью программирования хранить структуры данных в памяти, а также писать код для вызовов к CPU и GPU для выполнения алгоритмов. Таким образом, мы можем переносить задачи из реальной жизни в компьютер и решать различные сложные проблемы более эффективно.

Оставляйте свои идеи, вопросы и предложения в комментариях