Блок-схема циклического алгоритма: примеры с нулём
Блок-схема циклического алгоритма: примеры суммы, ввода и счётчика. Показываю стрелки возврата, ноль повторений и проверку границ на конкретных значениях.
Андрей
Преподаватель, научный редактор
8 мин чтения
Ноль повторений — тоже правильный результат. Я оставил на занятии задачу о сумме чисел от 1 до n и предложил взять n = 0. Одна схема сразу закончила работу, другая зачем-то прибавила единицу. Так блок-схема циклического алгоритма и примеры к ней перестали быть упражнением на красивые стрелки. Ниже собраны три варианта: проверка перед действием, проверка после него и повторение со счётчиком. По каждому можно пройти карандашом и получить определённый результат.
Мне удобнее начинать именно с маршрута выполнения. Где появилось первое значение? Какой блок меняет его? Куда вернулась стрелка? Пока эти вопросы не решены, ромб можно нарисовать очень аккуратно и всё равно получить неправильную сумму.
Блок-схема циклического алгоритма: примеры читаем по стрелкам
В текстовых схемах ниже я называю блоки словами. При переносе в графический редактор используй принятые в задании обозначения. Обычно начало и конец оформляют отдельными терминаторами, вычисление помещают в прямоугольник, ввод и вывод в параллелограмм, условие в ромб. Здесь расположение и подписи важнее оформления рамки.
У каждого ромба должны быть понятные выходы. «Да» означает, что записанное условие истинно. «Нет» означает обратное. Эти подписи относятся к вопросу внутри блока, а не к общему желанию продолжать работу.
Я держу рядом короткую памятку:
`s := 0` означает присвоить переменной s значение 0.
`s := s + i` означает вычислить новое значение по старым s и i.
Стрелка возврата ведёт к конкретному блоку; пересечение линий само по себе не означает соединения.
Если схемы рисуются с помощью чата, сначала стоит согласовать именно эти подписи. В статье о работе с блок-схемой разобрана подготовка такого описания. Здесь я уже беру определённые задачи и прохожу их до выхода.
Сумма от 1 до n: условие проверяется раньше сложения
Задача: найти сумму всех целых чисел от 1 до n включительно. Входное n — целое неотрицательное число. Для n = 0 договариваемся получить 0: складывать нечего. Отрицательные значения не входят в условия этой задачи.
Нужны две переменные. s хранит накопленную сумму, i указывает следующее слагаемое. Перед первым проходом s равно нулю, i равно единице.
```text
Начало → Ввод n → s := 0; i := 1
↓
[i ≤ n?] ── Нет → Вывод s → Конец
│ Да
↓
s := s + i
↓
i := i + 1
│
└── возврат к [i ≤ n?]
```
Это цикл с предусловием: решение о выполнении тела принимается до входа в него. Тело здесь состоит из сложения и увеличения счётчика. Один проход добавляет ровно одно очередное число.
Я собрал трассировку для n = 4. В таблице показаны значения непосредственно перед каждой проверкой, поэтому последняя строка нужна тоже:
Проверка · i · s перед проверкой · Условие i ≤ 4 · Следующее действие
Первая — 1 — 0 — Да — Прибавить 1
Вторая — 2 — 1 — Да — Прибавить 2
Третья — 3 — 3 — Да — Прибавить 3
Четвёртая — 4 — 6 — Да — Прибавить 4
Пятая — 5 — 10 — Нет — Вывести 10
Пять проверок, четыре сложения. Я специально проговариваю это различие. Число посещений ромба может быть на единицу больше числа выполнений тела, и это не лишний проход.
При n = 0 первая проверка `1 ≤ 0` сразу даёт «Нет». Сумма остаётся нулевой. При n = 1 тело выполняется однажды и выводится 1. Обе проверки помогают убедиться, что инициализация и граница работают вместе.
Блок-схема циклического алгоритма: примеры при другом порядке действий
Есть правка, после которой все нужные блоки остаются на месте, а сумма портится. Достаточно поменять местами два действия в теле: сначала увеличить i, потом прибавить его к s. Обратная стрелка по-прежнему приходит к условию. На первый взгляд рисунок почти не изменился.
Проверим первую итерацию. Условие смотрит на i = 1 и разрешает вход. Но внутри i сразу становится равным 2. Поэтому сумма начинается с двойки, а единица пропускается. На последнем проходе условие ещё видит четвёрку, затем счётчик становится пятёркой и именно пятёрка попадает в сумму. Получается `2 + 3 + 4 + 5 = 14` вместо 10.
Я предлагаю найти здесь две разные границы. В ромбе проверялось одно значение, а при сложении использовалось уже другое. Само условие `i ≤ n` не ошибочно. Ошибка возникла из-за того, что изменилось значение переменной между разрешением на вход и её использованием.
При n = 0 испорченная версия всё равно вернёт правильный ноль. Одного удобного испытания оказалось мало. При n = 1 она сразу выдаст 2 вместо 1, и причину можно увидеть за один проход. Поэтому я не прошу ученика прогонять десятки чисел: сначала нужны случаи, в которых видно назначение каждого действия.
Починить рисунок можно, вернув сложение перед увеличением счётчика. Если очень хочется оставить другой порядок, придётся заново согласовать начальное значение и условие. Это уже другой вариант алгоритма, который нужно пройти целиком. Перестановка прямоугольников меняет вычисления, даже когда набор подписей совпадает.
Ввод положительного числа: сначала действие, затем вопрос
Теперь другая задача. Нужно получить положительное целое число, повторяя ввод, пока пользователь не введёт подходящее. В этом примере считаем, что целое число уже прочитано; ошибки вроде букв вместо числа требуют отдельного разбора ввода.
Здесь нельзя проверять x раньше первого ввода: значения ещё нет. Поэтому условие стоит после действия.
```text
Начало
↓
Ввод целого x ←──────────────────┐
↓ │
[x > 0?] ── Нет ─────────────────┘
│ Да
↓
Вывод x → Конец
```
Это вариант цикла с постусловием. Он выполняет тело хотя бы один раз. Если последовательно вводятся −3, 0 и 5, первые два значения возвращают нас к вводу. Пятёрка ведёт к выходу. Всего будет три ввода и один окончательный вывод.
Я попробовал заменить вопрос на `x ≤ 0?`. Задача осталась той же, но подписи переходов пришлось поменять: теперь «Да» возвращает к вводу, «Нет» завершает цикл. Механически перенести старые подписи нельзя.
У такого алгоритма нет обещания закончиться за определённое число попыток. Если каждый раз вводить отрицательное значение, повторение продолжится. Завершение зависит от появления положительного числа. Это свойство условий, а не ошибка нарисованной стрелки.
Счётчик: три карточки требуют трёх номеров
Третий пример я беру из подготовки учебных карточек. Нужно вывести номера от 1 до m включительно, где m — целое неотрицательное число. В моей пачке было 3 карточки: ожидаем номера 1, 2, 3. Номер 4 уже лишний.
Такой цикл часто записывают компактно, обозначая параметр и его границы. Чтобы не прятать действие счётчика, ниже я разворачиваю его через обычное условие:
```text
Начало → Ввод m → i := 1
↓
[i ≤ m?] ── Нет → Конец
│ Да
↓
Вывод i
↓
i := i + 1
│
└── возврат к [i ≤ m?]
```
После вывода последнего номера счётчик всё равно увеличится. При m = 3 он станет равен 4, но это значение уже не выводится. Следующая проверка завершит работу. Поэтому в трассировке переменная может принимать число, которого нет среди результатов.
Если переносишь этот алгоритм в Python, есть ещё одно различие. В официальном учебнике Python указано: правая граница `range` в последовательность не входит. Поэтому для номеров от 1 до m нужен диапазон `range(1, m + 1)`. Запись `range(1, m)` остановится раньше нужного номера. Блок-схема сама по себе не обязана копировать синтаксис языка.
Пять мест, которые я проверяю до раскрашивания блоков
Я проверил эти схемы на маленьких значениях, потому что длинная трассировка легко скрывает ошибку. Однажды у меня стрелка после `i := i + 1` возвращалась к сложению. Условие оставалось на рисунке, но повторно его никто не посещал. Получился бесконечный рост суммы.
Теперь прохожу рисунок в таком порядке:
Нахожу присвоения до первого использования переменных.
Отмечаю блок, который меняет условие следующего прохода.
Проверяю, куда именно приходит обратная стрелка.
Выполняю случай без повторений, если он разрешён задачей.
Записываю последнее значение счётчика и последнее выведенное значение отдельно.
Вот задача, начальные значения и переходы моей схемы: [добавь их]. Пройди алгоритм для n = 0, 1 и 4, если эти значения допустимы. Для каждой проверки покажи значения переменных и выбранную ветку. Если цикл не заканчивается, назови переход, из-за которого условие не меняется. Не исправляй схему молча: сначала покажи первое расхождение с условиями задачи.
Размер задания помогает выбрать и подходящий режим работы: один короткий цикл или несколько вложенных. С этой задачей соотноси описания тарифов. Объяснение чата всё равно сверяй с собственной трассировкой; уверенный текст не заменяет прохождения стрелок.
Напоследок измени в первой схеме `i ≤ n` на `i < n`. До вычислений предскажи, какое слагаемое исчезнет при n = 4. Затем пройди четыре проверки. Если можешь объяснить разницу между 10 и 6, у тебя уже есть способ разбирать цикл, а не запоминать его рисунок.
