§ 1. Алгоритм и его свойства

Сначала определяют задачу: что дано, что нужно получить и какие значения допустимы. Затем выбирают исполнителя и его систему команд. Команда «сделай красиво» не задаёт однозначного действия; команда «выведи сумму a и b» точна, если известны значения и правила сложения.

В школьной детерминированной модели алгоритм — точное предписание выполнить последовательность действий для решения задачи. Разные входные данные могут вести по разным ветвям. Например, алгоритм Евклида получает два положительных целых числа и находит их наибольший общий делитель. Значения 48 и 18 — один набор данных, а не отдельный способ решения.

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

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

При следовании команды идут одна за другой. Ветвление выбирает действие по условию. Цикл повторяет блок, пока выполняется условие или пока не выполнено заданное число повторений. Подпрограмма выделяет действие, которое удобно назвать и использовать несколько раз.

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

Трассировка фиксирует значения после каждого шага. В алгоритме Евклида сохраняют остаток r = a mod b, затем присваивают a := b и b := r. Пока b не равно нулю, процесс повторяется. Для 48 и 18 пары равны (48,18), (18,12), (12,6), (6,0); ответ 6.

Решето Эратосфена оставляет простые числа от 2 до N. У каждого ещё не вычеркнутого p вычёркивают кратные начиная с p²; достаточно p² ≤ N. Число 1 не простое. Проверяют малые N, повторяющиеся значения, границы и случаи, когда тело цикла не выполняется. Несколько успешных тестов полезны, но не заменяют рассуждение о правильности для всех допустимых данных.

var a, b, r: integer;
begin
  Readln(a, b); { a > 0, b > 0 }
  while b <> 0 do
  begin
    r := a mod b;
    a := b;
    b := r;
  end;
  Writeln(a);
end.