Что такое алгоритм

Способ нахождения наибольшего общего делителя из VII книги «Начал» Евклида, написанных около 2300 лет назад, до сих пор работает в компьютерах.

Метод, который всегда работает

Допустим, нужно найти наибольшее число, на которое делятся и 1071, и 462. Можно перебрать все числа от 462 до 1 и остановиться на первом, на которое делятся оба. Это сработает, но может понадобиться несколько сотен попыток. Есть путь короче. Раздели 1071 на 462 и запомни остаток, 147. Теперь раздели 462 на 147 и запомни остаток, 21. Раздели 147 на 21: остаток 0, значит, ответ 21. Три деления вместо нескольких сотен.

Этот короткий путь является алгоритмом: конечным списком точных шагов, который получает входные данные и выдаёт правильный результат. Это алгоритм Евклида для наибольшего общего делителя, он есть в VII книге «Начал», написанных около 300 г. до н. э. Евклид описывал его через повторное вычитание отрезков, а не деление, но идея та же, а вариантом с остатками программы пользуются сегодня.

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;   // остаток
    a = b;
    b = r;
  }
  return a;
}
console.log(gcd(1071, 462)); // 21

Что делает список шагов алгоритмом

Учебники, например книга Кормена, Лейзерсона, Ривеста и Штайна, описывают алгоритм как чётко определённую процедуру, которая превращает входные данные в выходные. В это описание уложены три свойства, и каждое важно, когда пишешь код.

• Точность. Каждый шаг значит одно. «Раздели a на b и запомни остаток» сказано точно; «как-нибудь уменьши числа» нет.
• Конечность. Алгоритм должен остановиться. В алгоритме Евклида остаток всегда меньше числа, на которое делили, поэтому он уменьшается каждый круг и обязательно дойдёт до 0.
• Правильность. Для любых допустимых входных данных результат верен, а не только для примеров, которые ты попробовал.

В качестве бытового примера часто приводят кулинарный рецепт, и это честный пример: продукты являются входными данными, блюдо является результатом, а шаги идут по порядку. Разница в том, сколько додумывает читатель. Повар сам решает, что значит «щепотка». Компьютер не решает ничего, поэтому алгоритмы для компьютеров записывают, проговаривая каждый шаг.

Одна задача, разные алгоритмы

У одной задачи обычно много правильных алгоритмов, и объём работы у них может отличаться огромно. Для наибольшего общего делителя 1071 и 462 перебор всех чисел от 462 вниз требует 442 попыток, прежде чем дойдёт до 21, а методу Евклида нужно 3 деления. Оба правильные. Быстрый только один. Большая часть этого курса посвящена второму вопросу: если метод правильный, сколько шагов он делает и как растёт это число, когда входные данные становятся больше?

Чтобы ответить, специалисты по информатике считают базовые шаги (сравнение, обмен, деление), а не секунды. Секунды зависят от машины. Число шагов зависит только от алгоритма и входных данных, поэтому позволяет честно сравнивать два метода. Лаборатория ниже считает сравнения за тебя, пока сортирует ряд столбиков. Попробуй один и тот же начальный порядок с двумя разными способами и следи за счётчиками.

Вход, выход и шаги между ними

Прежде чем писать алгоритм, точно запиши, что поступает на вход и что должно выйти. Для наибольшего общего делителя: на входе два целых положительных числа, на выходе одно целое число, на которое делятся оба, причём никакое большее число этого не делает. Такое описание подсказывает, как проверить результат, и часто намекает на шаги. Оно же выявляет крайние случаи: что, если одно из чисел 0? (Цикл выше возвращает другое число, и это правильный ответ.) Что, если числа равны? Если подумать о крайних случаях до запуска кода, многие ошибки ловятся заранее.