Раздел 2 — Алгоритм и его запись

Программа начинается не с кода. Между условием задачи и работающей программой — пять этапов, и ошибка на раннем этапе стоит дороже всего: неверно понятое условие не исправит никакой код.

Пример. Условие: «На экскурсию едут N учеников. В автобусе c мест. Сколько автобусов заказать?»

• Постановка. Учителя тоже едут? Сколько их? Пусть уточнили: едут только ученики. N и c — целые, N ≥ 1, c ≥ 1.
• Модель. Число автобусов K — наименьшее целое, при котором K · c ≥ N, то есть K = ⌈N / c⌉ — деление с округлением вверх. Для N = 50, c = 45: 50 / 45 ≈ 1,11, K = 2. Округление по правилам арифметики дало бы 1 автобус и 5 учеников без места.
• Алгоритм. Ввести N и c; проверить, что оба ≥ 1; K = (N + c − 1) / c в целых числах (раздел 4 объяснит, почему эта формула округляет вверх); вывести K.
• Тесты. N = 90, c = 45 → 2 (делится нацело); N = 91, c = 45 → 3; N = 1, c = 45 → 1; N = 0 → ошибка.

Решение учебной задачи заканчивается тестами. Программа, которой пользуются люди, живёт дальше. Жизненный цикл — всё время от идеи программы до отказа от неё:

  требования ──► проектирование ──► реализация ──► тестирование ──► внедрение ──► сопровождение ──► вывод из эксплуатации
       ▲                                                                                │
       └──────────────────── новые требования, найденные ошибки ◄───────────────────────┘

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

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

Программа решает задачу у автора. Программный продукт — программа, которой может пользоваться и которую может сопровождать кто-то другой: к коду добавляются установка, документация пользователя, техническая документация, обработка любых ошибок ввода, поддержка. По оценке Ф. Брукса («Мифический человеко-месяц»), продукт обходится примерно втрое дороже программы, решающей ту же задачу.

Эти характеристики перечислены в стандарте ГОСТ Р ИСО/МЭК 25010. В курсе каждая из них превращается в конкретное требование к практической работе: проверка ввода — надёжность, оценка числа действий — производительность, имена по смыслу — сопровождаемость, сборка без предупреждений по стандарту C11 — переносимость.

Алгоритм — конечная последовательность точных указаний исполнителю, которая по допустимым входным данным приводит к результату. Исполнитель — компьютер — не догадывается и не додумывает, поэтому к записи алгоритма есть требования:

Алгоритм Евклида — наибольший общий делитель (НОД) двух натуральных чисел. Он основан на свойстве: НОД(a, b) = НОД(b, a mod b), где a mod b — остаток от деления a на b; и НОД(a, 0) = a. Словесная запись:

1. Ввести натуральные a и b.
2. Пока b не равно 0, повторять:
   2.1. r = остаток от деления a на b.
   2.2. a = b.
   2.3. b = r.
3. Вывести a.

Конечность здесь надо доказать, а не предположить: остаток всегда меньше делителя, поэтому b на каждом шаге уменьшается хотя бы на 1, оставаясь неотрицательным, — значит, рано или поздно станет 0. Такое рассуждение — почему повторение закончится — требуется в курсе для каждого цикла.

Символы блок-схем в России установлены стандартом ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем». Для алгоритмов курса нужно семь символов. На страницах курса они нарисованы текстом упрощённо; соответствие — в последнем столбце.

Правила: поток идёт сверху вниз и слева направо — в этих направлениях стрелки можно не рисовать, в остальных стрелка обязательна. У схемы один вход и один выход. У ромба ровно два выхода, оба подписаны. Текст в символе — короткая формула или условие, а не абзац. Схема алгоритма Евклида:

               ( Начало )
                   │
              / Ввод a, b /
                   │
     ┌──────►< b ≠ 0 ? >─── нет ───┐
     │             │ да            │
     │      [ r = a mod b ]        │
     │             │               │
     │         [ a = b ]           │
     │             │               │
     │         [ b = r ]           │
     └─────────────┘               │
                            / Вывод a /
                                   │
                              ( Конец )

Любой алгоритм можно составить из трёх базовых структур, вкладывая их друг в друга (теорема Бёма — Якопини, 1966). Схемы и программы, построенные только из них, называют структурными: у каждой структуры один вход и один выход, и её можно читать как один большой шаг.

  Следование           Ветвление                     Цикл с предусловием     Цикл с постусловием

  [ действие 1 ]       < условие? >── нет ──┐        ┌──►< условие? >─ нет ─┐   ┌──►[ тело ]
        │                   │ да            │        │        │ да           │   │       │
  [ действие 2 ]       [ действие 1 ] [ действие 2 ] │     [ тело ]          │   └─ да ─< условие? >
        │                   │               │        └────────┘              │           │ нет
                            ├◄──────────────┘                     ┌◄─────────┘           │
                            │                                     │

Цикл с предусловием проверяет условие до тела — тело может не выполниться ни разу. Цикл с постусловием проверяет после — тело выполняется хотя бы раз. В C это циклы while и do while (раздел 6).

Псевдокод — запись алгоритма ключевыми словами на естественном языке. Строгого стандарта у него нет; в курсе используется такая форма:

ВВОД a, b
ЕСЛИ a ≤ 0 ИЛИ b ≤ 0 ТО
    ВЫВОД «нужны натуральные числа»
ИНАЧЕ
    ПОКА b ≠ 0 ВЫПОЛНЯТЬ
        r ← a mod b
        a ← b
        b ← r
    КОНЕЦ ПОКА
    ВЫВОД a
КОНЕЦ ЕСЛИ

Стрелка ← — присваивание: вычислить правую часть и записать результат в переменную слева. a ← b — не равенство, а действие: старое значение a пропадает. Поэтому порядок строк в теле цикла важен: если поменять местами a ← b и r ← a mod b, остаток будет считаться уже от нового a.

Трассировка — выполнение алгоритма вручную с записью значений переменных после каждого шага. Она показывает, что алгоритм делает на самом деле, а не что задумано. Алгоритм Евклида для a = 48, b = 18:

НОД(48, 18) = 6 — верно: 48 = 6 · 8, 18 = 6 · 3, и у 8 и 3 общих делителей нет. А если ввести a = 18, b = 48 — меньшее первым? Первый шаг даст r = 18 mod 48 = 18, a = 48, b = 18: числа просто поменялись местами, дальше — та же таблица. Алгоритм работает и так, это видно из трассировки, а не из догадки.

По трассировке составляются тестовые примеры — пары «входные данные → ожидаемый результат». Хороший набор тестов проверяет:

• обычный случай: 48, 18 → 6;
• особые значения: одно число делит другое (12, 4 → 4), равные числа (7, 7 → 7), взаимно простые (8, 15 → 1), единицу (1, 100 → 1);
• порядок аргументов: 18, 48 → 6;
• недопустимые данные: 0, −5 — сообщение об ошибке.

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

Сумма 1 + 2 + … + n. Алгоритм с циклом:

S ← 0
ДЛЯ i ОТ 1 ДО n
    S ← S + i
КОНЕЦ ДЛЯ

Сложений — n. Для n = 1 000 000 это миллион сложений. А по формуле суммы арифметической прогрессии S = n · (n + 1) / 2 — одно умножение, одно сложение и одно деление при любом n. Чем больше n, тем сильнее разница.

Поиск в списке. Есть ли фамилия в списке из n фамилий? Проверять подряд с первой: в лучшем случае — 1 сравнение (фамилия первая), в худшем — n (последняя или её нет). Если список упорядочен по алфавиту, можно открыть середину, сравнить и отбросить половину, в которой фамилии быть не может; затем — середину оставшейся половины, и так далее. Каждое сравнение уменьшает список вдвое:

Число делений пополам до одного элемента — это log₂ n с округлением вверх: 2¹⁰ = 1024 ≥ 1000, 2²⁰ ≈ миллион. Цена второго способа — список должен быть упорядочен заранее; сколько стоит упорядочить, разбирается в разделе 8 вместе с записью таких оценок в виде O(n), O(log n).