Построение алгоритма
Построение алгоритма начинается не с записи команд, а с перевода условия задачи в модель: нужно определить входные данные, возможные состояния, допустимые команды и способ перебора вариантов. Затем алгоритм проверяют на граничных случаях и только после этого записывают в выбранном исполнителе или на языке программирования.
От условия к модели
Сначала прочитайте условие и ответьте на четыре вопроса: что дано, что требуется получить, какие действия разрешены и какие ограничения указаны. Алгоритм должен использовать только известные данные и команды, а его результат должен однозначно соответствовать требованию задачи.
Модель — упрощённое описание объекта или процесса, в котором оставлены только свойства, важные для решения. Например, клетчатое поле можно представить таблицей координат, число — набором цифр, а движение исполнителя — последовательностью состояний его положения и направления.
- Выделите входные данные: числа, строки, координаты, начальное состояние.
- Выделите результат: число, строку, положение исполнителя или факт выполнения условия.
- Опишите состояние: всё, что нужно знать перед следующим шагом.
- Определите ограничения: границы поля, диапазон чисел, число ходов, запрет на деление на ноль.
- Составьте последовательность действий и проверок.
Если задача связана с исполнителем, сначала изучите его систему команд и область допустимых действий. Исполнитель алгоритма не может выполнить команду, которой нет в системе, и не должен выходить за границы разрешённой области. Чтобы не потерять важную информацию, полезно явно записывать состояние алгоритма: например, координаты \((x,y)\), направление и число уже сделанных шагов.
Для каждой команды спросите: какие значения изменились, а какие остались прежними? Если это трудно определить, составьте таблицу: номер шага, команда, координаты, направление, дополнительные переменные.
Команды, проверки и порядок действий
Алгоритм обычно состоит из трёх типов действий: присваивания или изменения данных, проверок условий и повторений. Команды должны быть расположены так, чтобы перед использованием переменной она уже имела значение, а перед опасным действием выполнялась необходимая проверка.
Если действие разрешено только при условии \(P\), в алгоритме сначала проверяют \(P\), а затем выполняют действие. Например, перед делением на \(b\) необходимо проверить \(b\ne0\), а перед переходом исполнителя — что новая клетка принадлежит полю.
Проверка может быть полной или частичной. Полная проверка учитывает все ограничения задачи. Например, для точки \((x,y)\) внутри прямоугольника недостаточно проверить только \(x\ge a\): нужно также проверить верхнюю границу и ограничения по \(y\).
Условия объединяют логическими операциями: «и» означает одновременное выполнение всех требований, «или» — выполнение хотя бы одного, «не» — отрицание условия. Скобки помогают явно задать порядок вычисления сложного условия.
Какой порядок действий безопасен при подсчёте количества делителей числа \(n\)?
Удобно разделять алгоритм на этапы: ввод, подготовка переменных, основной цикл, проверка результата и вывод. Такое разбиение облегчает отладку алгоритма и помогает обнаружить место, где появилась ошибка.
Как выбрать способ перебора
Во многих экзаменационных задачах требуется проверить множество вариантов: числа, пары координат, маршруты, длины отрезков или последовательности команд. Способ перебора выбирают по структуре множества и ограничениям.
- Последовательный перебор: проверить значения \(1,2,3,\ldots,n\) по очереди.
- Перебор с шагом: рассматривать только чётные числа, клетки одного цвета или точки через заданный интервал.
- Вложенный перебор: для каждой пары \((x,y)\) проверить все допустимые значения двух параметров.
- Перебор с досрочной остановкой: прекратить поиск, как только найден подходящий вариант или доказано, что его нет.
- Перебор состояний: хранить текущее состояние и переходить к следующему по правилам задачи.
Линейный поиск — последовательная проверка элементов одного за другим до нахождения нужного элемента или окончания набора. В худшем случае проверяются все \(n\) элементов, поэтому число проверок имеет порядок \(n\).
Если перебираются все пары из \(n\) вариантов, число проверок может быть порядка \(n^2\). Поэтому важно не перебирать невозможные варианты и не выполнять внутри цикла лишние действия. Однако сначала нужно получить корректный алгоритм, а затем заниматься оптимизацией алгоритма.
Перебор даёт правильный ответ, если выполнены два условия: каждый допустимый вариант рассматривается хотя бы один раз, а недопустимый вариант не принимается за решение. Пропуск одного варианта может привести к неверному ответу.
Разобранный пример: поиск минимального подходящего числа
Задача: дано натуральное число \(N\). Найдите наименьшее число \(x\ge N\), которое делится на 7 и не делится на 5. Построим алгоритм по условию.
Состояние состоит из текущего кандидата \(x\). Начинаем с \(x=N\), проверяем два условия, а если хотя бы одно не выполнено, увеличиваем \(x\) на единицу. Как только оба условия выполнены, поиск можно остановить: все меньшие числа уже проверены.
1ввести N 2x := N 3пока не (x mod 7 = 0 и x mod 5 <> 0) делать 4 x := x + 1 5вывести x
Проверим пример \(N=34\). Числа 34, 35 и 36 не подходят: первое не делится на 7, второе делится на 5, третье не делится на 7. Число 37 также не подходит, а 42 делится на 7 и не делится на 5. Ответ — 42.
В каждой итерации \(x\) увеличивается на 1. Среди семи последовательных чисел обязательно есть число, кратное 7; при необходимости проверка продолжится ещё несколько шагов. Поэтому подходящий кандидат будет найден, а цикл завершится.
Проверка корректности и запись схемы
После построения нужно проверить не только обычный пример, но и крайние случаи: минимальный ввод, уже подходящий кандидат, отсутствие изменений, максимально возможное значение и ситуации на границе области. Для доказательства полезно описать, что сохраняется после каждого шага. Это называют инвариантом цикла.
Инвариант — утверждение, истинное перед началом каждой итерации и после её выполнения. В примере с числом \(x\) инвариант таков: перед проверкой текущего кандидата все числа от \(N\) до \(x-1\) уже проверены и не подходят.
При изображении алгоритма можно использовать схему алгоритма: овалами обозначают начало и конец, прямоугольниками — действия, ромбами — проверки. Любой переход должен вести к следующему определённому шагу; полезно отслеживать каждый шаг алгоритма. В задачах о процессах удобно также описывать переход между состояниями: какое состояние было до команды и каким стало после неё.
1. Проверять только одно из условий, забывая второе. 2. Начинать перебор с \(N+1\), хотя число \(N\) тоже может подходить. 3. Использовать цикл без изменения переменной: он становится бесконечным. 4. Увеличивать счётчик или принимать ответ до проверки условия. 5. Выходить за границы поля или массива. 6. Считать, что найденный вариант минимален, если перебор шёл не по возрастанию. 7. Путать «и» с «или»: условия \((A\land B)\) и \((A\lor B)\) дают разные множества решений.
Quick-test
Проверьте понимание
Главное
- Переводите условие в модель: вход, результат, состояние, команды и ограничения.
- Перед опасным действием сначала проверяйте условие его допустимости.
- Выбирайте полный перебор, линейный поиск или перебор состояний по структуре задачи.
- При переборе по возрастанию первый найденный подходящий вариант является минимальным.
- Проверяйте граничные случаи, инвариант цикла и завершение алгоритма.