§ 58. Циклические алгоритмы

Определения и обозначения

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

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

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

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

Как это устроено

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

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

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

В цикле с параметром число повторений или последовательность значений параметра задаются заранее. На каждом шаге параметр принимает очередное значение, поэтому не нужно отдельно придумывать условие остановки для известного диапазона. Такой цикл удобен, например, для вывода чисел от 1 до 5 или обработки пяти элементов.

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

Сравнение видов циклов

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

Разбор задач

Вывести числа от 1 до 5

Количество значений известно заранее, поэтому здесь подходит цикл с параметром. Нужно перебрать целые числа от 1 до 5 включительно и выводить каждое текущее значение. Границы важны: верхняя должна включать число 5.

1. Зададим параметр i, который будет обозначать очередное число. Его первое значение — 1, а последнее — 5. Это задаёт пять шагов перебора.

2. На каждом шаге выведем i. После этого параметр увеличится на 1, чтобы перейти к следующему числу. Повторение закончится после обработки последнего значения.

3. Проверим результат: вывод начинается с 1, содержит все целые числа по порядку и заканчивается на 5. Если задать верхнюю границу 4, последнее число будет пропущено.

Ответ: алгоритм выводит 1, 2, 3, 4, 5.

Сумма чисел до ввода нуля

Пользователь вводит числа, пока не введёт 0; требуется найти сумму введённых чисел. Ноль здесь служит признаком остановки, а не слагаемым. Удобно проверять значение перед прибавлением, чтобы число-ограничитель не обрабатывалось как обычное число.

1. Сначала установим сумму в 0 и введём число. Начальное значение нужно, чтобы накопление начиналось с известного результата. После ввода проверим, равно ли число нулю.

2. Пока число не равно 0, прибавляем его к сумме и запрашиваем следующее. Каждая итерация обрабатывает одно ненулевое значение. Новый ввод позволяет условию измениться.

3. Когда введён ноль, цикл заканчивается, и алгоритм выводит сумму. Ноль не прибавляется, поскольку проверка выполняется до команды накопления. Если первым введён ноль, результатом останется начальная сумма.

Ответ: вывести сумму всех введённых ненулевых чисел до первого нуля.

Наименьшее n, для которого 1 + 2 + … + n > S

Нужно найти первый натуральный номер, при котором накопленная сумма превысит заданное S. Поскольку число шагов заранее неизвестно, подойдёт цикл с предусловием. До начала повторений сумма равна 0, а n — 0.

1. Пока сумма не больше S, увеличиваем n на 1. Затем прибавляем n к сумме. Так на каждом шаге строится очередная частичная сумма: сначала 1, затем 1 + 2 и так далее.

2. Когда сумма станет больше S, проверка условия остановит цикл. Значение n к этому моменту соответствует количеству слагаемых, а последняя прибавка как раз пересекла заданную границу.

3. Проверим минимальность: на предыдущем шаге сумма ещё не превышала S, иначе цикл завершился бы раньше. Значит, найденное n — первое подходящее значение.

Ответ: вывести n и полученную сумму.

Типичные ошибки

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

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

Неверная граница цикла с параметром приводит к пропуску первого или последнего значения. Ошибаются, когда не уточняют, включены ли границы диапазона. Для проверки выпишите значения параметра по порядку и сравните первое и последнее с требуемыми в задаче.

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

Связь с другими темами

Для записи циклов нужны переменные, присваивание и логические условия. Переменные хранят текущие значения, присваивание позволяет их изменять, а условие определяет, продолжать ли повторение. Без этих средств цикл не сможет управлять ходом выполнения.

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

Что запомнить

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