§ 3.6. Алгоритмическая конструкция «повторение». Циклические алгоритмы

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

Повторение и цикл

Повторение — алгоритмическая конструкция, в которой одна и та же группа команд исполняется несколько раз подряд. Алгоритм, где есть повторение, называют циклическим, а короче — циклом. Группу команд, которую цикл повторяет, называют телом цикла.

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

цикл ПОКА, он же цикл с заданным условием продолжения работы: тело повторяется, пока условие истинно; цикл ДО, он же цикл с заданным условием окончания работы: тело повторяется, пока условие не станет истинным; цикл с заданным числом повторений: сколько раз выполнить тело, сказано заранее; цикл ДЛЯ, он же цикл с переменной: особая величина сама отсчитывает проходы.

Разберём их по очереди.

Цикл ПОКА: проверка перед телом

Первый вид называют ещё циклом с предусловием: приставка «пред» значит «перед», и условие здесь проверяется перед телом. Работает он так. Исполнитель вычисляет условие. Если оно истинно, выполняется тело, после чего исполнитель возвращается к проверке. Если ложно, цикл закончен и выполняется команда, которая записана после него. На рисунке 1 слева такой цикл изображён блок-схемой: ромб с условием стоит сверху, выход «да» ведёт вниз к телу, а от тела линия поднимается обратно ко входу ромба. Выход «нет» уводит из цикла.

В школьном алгоритмическом языке цикл открывают служебными словами нц (начало цикла) и пока, а закрывают словом кц (конец цикла):

нц пока <условие продолжения> <команды, которые повторяются> кц

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

нц пока снизу свободно вниз закрасить кц

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

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

x := 4 нц пока x > 0 x := x + 2 кц

зациклится: x только растёт, и условие x > 0 остаётся истинным на каждой проверке.

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

нц пока в стопке есть тетради взять верхнюю тетрадь если работа выполнена верно то поставить отметку иначе вернуть на доработку все кц

Тело здесь состоит из двух команд: взять тетрадь и ветвление, которое выбирает одно из двух действий. Конструкции вкладываются друг в друга, как матрёшки.

Деление без деления

Дано: натуральные числа n = 46 и d = 8. Нужно найти неполное частное k и остаток r, не пользуясь операцией деления.

Решение. Деление можно заменить вычитанием. Будем отнимать делитель от того, что осталось, пока остаток не меньше делителя. Сколько раз удалось отнять, таково и неполное частное; что осталось в конце, то и остаток. Блок-схема этого алгоритма — на рисунке 2, а запись на алгоритмическом языке такая:

r := n k := 0 нц пока r >= d r := r - d k := k + 1 кц

Проследим выполнение. До цикла r = 46, k = 0. Дальше по проверкам:

46 >= 8 — да, после тела r = 38, k = 1; 38 >= 8 — да, после тела r = 30, k = 2; 30 >= 8 — да, после тела r = 22, k = 3; 22 >= 8 — да, после тела r = 14, k = 4; 14 >= 8 — да, после тела r = 6, k = 5; 6 >= 8 — нет, цикл закончен.