Блок-схема: пример поиска максимума в списке отрицательных чисел. Разбери фигуры, ветвление, возврат цикла и пустой ввод по схеме и таблице прохождения.
Андрей
Преподаватель, научный редактор
6 мин чтения
Ноль оказался «максимумом» списка −8, −3, −11, −5. Такого числа в списке нет. Я проверил учебный алгоритм: ошибка начиналась с присваивания `m = 0`. Блок-схема, пример которой разберём ниже, позволяет найти этот сбой до оформления программы. Вместе с ним станут видны две другие важные вещи: куда возвращается цикл и что делать, когда список пуст.
Будем искать наибольшее значение среди целых чисел. Для непустого списка ответ должен быть одним из его элементов и не уступать остальным. Номер максимума пока не ищем.
Миф: блок-схема — пример только для оформления кода
Мне полезно рисовать её до программы. На схеме можно решить, когда брать первое число, что сравнивать дальше и при каком условии остановиться. Код пока не нужен. При составлении схемы достаточно договориться о данных и переходах.
Для нашего образца нужны три обозначения:
`A` — список чисел, элементы нумеруем с 1.
`n` — количество элементов, `i` — номер проверяемого элемента.
`m` — наибольшее из уже просмотренных значений.
Я собрал схему с обычными обозначениями действий, условий и ввода-вывода. В текстовом рисунке формы упрощены скобками; при переносе в графический редактор выбирай соответствующие фигуры.
Ромб — Проверить условие и выбрать продолжение — `< i <= n ? >`
Параллелограмм — Получить данные или вывести результат — `/ Ввести A /`, `/ Вывести m /`
Вот полный пример, включая пустой ввод. Знак `<=` означает «меньше или равно», а `A[i]` — элемент с номером `i`.
```text
(Начало)
|
/ Ввести A /
|
[n = длина A]
|
< n = 0 ? > --Да--> / Список пуст / --> (Конец)
|
Нет
v
[m = A[1]; i = 2]
|
+-----------> < i <= n ? > --Нет--> / Вывести m / --> (Конец)
| |
| Да
| v
| < A[i] > m ? >
| / \
| Да Нет
| | |
| [m = A[i]] |
| | |
| +----+----+
| |
| [i = i+1]
| |
+-------------------+
```
В ромбе задаём вопрос. Присваивание `m = A[i]` выполняется в отдельном прямоугольнике. Благодаря этому видно, когда значение действительно меняется, а когда проверка оставляет его прежним. Один и тот же ромб нельзя читать как безусловную команду обновления максимума.
Миф: начальное значение максимума всегда равно нулю
Я попробовал пройти ошибочную версию с начальным `m = 0`. Первое число −8 не больше нуля. Второе −3 тоже. Остальные ещё меньше. Ни одно сравнение не прошло. В конце остался ноль, который мы сами назначили до просмотра чисел.
На положительных числах такой дефект легко пропустить. Для списка 4, 2 обе версии вернут 4. Поэтому удачный ответ на одном удобном наборе ещё не объясняет, верна ли начальная установка.
В исправленном варианте беру `m = A[1]`. На старте просмотрен ровно один элемент, поэтому он и есть текущий максимум. Дальше начинаю с `i = 2`. Первое число не нужно сравнивать само с собой.
Вот проход по списку:
Номер i · Текущее A[i] · m до сравнения · A[i] > m? · m после
2 — −3 — −8 — Да — −3
3 — −11 — −3 — Нет — −3
4 — −5 — −3 — Нет — −3
Ответ −3. Он принадлежит списку и больше остальных чисел. Я сохраняю именно значение первого элемента, а не его номер: запись `m = 1` вернула бы ту же проблему с посторонним числом.
Начинать с первого элемента можно только после проверки, что этот элемент существует. Поэтому в полном образце выше проверка `n = 0` расположена раньше обращения к `A[1]`.
Миф: обе ветви сравнения можно сразу вести к выводу
После сравнения очередного числа поиск обычно ещё не закончен. Если число оказалось больше `m`, обновляем максимум. Если нет, оставляем прежний. Дальше обе ветви встречаются перед увеличением `i`, и выполнение возвращается к вопросу `i <= n`.
В нашем проходе сравнение значений выполняется 3 раза. А условие продолжения цикла проверяется четыре раза: при `i = 2`, 3, 4 и 5. Последняя проверка даёт «Нет», потому что элементов всего четыре. К `A[5]` схема уже не обращается.
Для списка из одного числа `i = 2`, `n = 1`. Условие `2 <= 1` сразу ложно, и схема выводит первый элемент. Проверка цикла стоит до чтения `A[i]`, поэтому второго элемента ей не требуется.
Преждевременный выход хорошо виден на другом наборе: −8, −3, −1. После первого обновления `m` равно −3, но это ещё не окончательный ответ. Последний элемент −1 должен изменить его снова. Я проверяю такой пример, когда стрелка из обновления подозрительно быстро приходит к выводу результата.
Есть и обратная ошибка: забыть увеличить `i`. Тогда схема возвращается к проверке с тем же номером и снова рассматривает прежний элемент. Для непустого остатка списка такой цикл не закончится. Увеличение номера нужно на обеих ветвях сравнения, а не только после успешного обновления `m`.
Смысл `m` не меняется. Это максимум среди уже просмотренных элементов. Мы либо нашли значение больше прежнего, либо убедились, что очередное число его не меняет. Так ответ обосновывается всем проходом, а не одним сравнением.
Миф: пустой список просто вернёт ноль
В пустом списке нет ни первого элемента, ни значения, которое можно объявить наибольшим. В нашем алгоритме это отдельный исход: вывести «Список пуст» и завершить работу. Возвращать ноль вместо такого сообщения нельзя — он будет выглядеть обычным результатом вычисления.
При этом сам ноль не запрещён. Если вход содержит 0 и −2, максимум действительно равен 0. Различаются отсутствие результата и законное значение из данных.
Для проверки образца я держу такие наборы:
`[-8, -3, -11, -5]` → −3: все числа отрицательные.
`[-6]` → −6: одного элемента достаточно, сравнения в цикле не нужны.
`[-4, -4]` → −4: равенство не требует замены значения.
`[0, -2]` → 0: ноль допустим как настоящий элемент.
`[]` → сообщение о пустом списке.
Если хочется обсудить отдельный переход, открой чат LibraChat и задай задачу словами:
Проверь алгоритм поиска максимального значения. Элементы A нумеруются с 1. Сначала проверяется пустота списка, затем m=A[1], i=2. Пока i<=n, сравниваем A[i]>m, при успехе обновляем m, после обеих ветвей увеличиваем i. Разбери вход [-8,-3,-11,-5] по состояниям i и m. Отдельно объясни выход для пустого списка и для одного элемента.
LibraChat помогает разбирать задачи; сравни его объяснение с таблицей прохождения и полным маршрутом цикла. Для подготовки учебных материалов можно отдельно посмотреть тарифы LibraChat.
Теперь поменяй только первый элемент исходного списка на 0. Объясни, почему схема вернёт ноль уже обоснованно, хотя присваивание `m = 0` в прежнем варианте было ошибкой. Решает происхождение начального значения и дальнейшая проверка списка.
