Основные алгоритмические конструкции

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

Что такое алгоритмическая конструкция

Алгоритмическая конструкция — это тип организации команд в алгоритме. Любая программа или блок-схема может состоять из трёх базовых конструкций либо их комбинации: линейной, разветвляющейся и циклической. Чтобы правильно решить задачу, сначала определяют, какие команды выполняются всегда, где происходит проверка условия и какие действия повторяются.

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

Линейный алгоритм

В линейном алгоритме каждая команда выполняется ровно в тот момент, когда до неё доходит управление. Если команда присваивания записана как \(x := x + 3\), это означает: к текущему значению \(x\) прибавляют 3 и результат снова записывают в \(x\). Правая часть вычисляется до изменения переменной.

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

1a := 4
2b := 3*a - 2
3a := a + b
4output(a)

Ветвление: проверка условия

Ветвление начинается с логического условия, например \(x>0\), \(a=b\) или \(n\bmod 2=0\). Условие имеет значение «истина» или «ложь». В полной форме выполняется одна ветвь при истинном условии, а другая — при ложном. В неполной форме действия указаны только для одного результата, обычно для истинного.

Операция \(\bmod\) обозначает остаток от деления. Например, \(17\bmod5=2\), а проверка \(n\bmod2=0\) определяет, является ли число \(n\) чётным. При нескольких условиях учитывают скобки и порядок логических операций: сначала выполняется отрицание, затем «И», затем «ИЛИ», если порядок не задан скобками.

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

Циклы и тело цикла

Циклический алгоритм содержит повторение. Повторяемая последовательность команд называется телом цикла. Число повторений определяется условием или диапазоном изменения счётчика.

В цикле с параметром заранее известен набор значений счётчика. Например, при \(i\) от 1 до 5 тело обычно выполняется пять раз: для \(i=1,2,3,4,5\). В цикле с предусловием условие проверяется перед телом, поэтому тело может не выполниться ни разу. В цикле с постусловием тело выполняется хотя бы один раз, так как проверка происходит после него.

Эта формула описывает накопление суммы: на каждом шаге к текущему значению \(S\) прибавляется очередной элемент \(a_i\). Перед началом накопления обычно записывают \(S:=0\). Для произведения начальное значение, как правило, равно 1.

Разобранный пример: сумма и условие в цикле

Рассмотрим алгоритм. Нужно определить значение переменной \(s\) после выполнения команд.

1s := 0
2for i := 1 to 5 do
3    if i mod 2 = 0 then
4        s := s + i
5    else
6        s := s + 2*i
7output(s)

Такой разбор можно оформить в таблице состояний. В строках указывают номер шага, значение \(i\), выбранную ветвь и новое значение \(s\).

Как решать задания на исполнение алгоритма

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

1. Определите исходные значения переменных и условие окончания.
2. Разделите команды на последовательные, условные и повторяющиеся.
3. Для каждого шага запишите значения переменных в трассировке алгоритма.
4. Перед выполнением ветви вычислите условие и выберите только нужный путь.
5. В цикле отдельно посчитайте первое, промежуточное и последнее повторение.
6. Проверьте, сколько раз выполнилось тело и какое значение получилось после последней команды.

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

Как описывать алгоритм и проверять себя

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

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