Алгоритмы и блок-схемы: разбор задач ОГЭ

В задании написано: «Определите, при каком наибольшем введённом значении переменной s программа выведет число 42». Ты смотришь на четыре строчки кода и не понимаешь, с какой стороны заходить: перебирать все числа подряд? Решать уравнение? Угадать?

Или другое: дана блок-схема с ромбами и стрелками, вопрос — «что выведет алгоритм при x = 7». И ты честно ползёшь по стрелкам глазами, теряешь, где был, начинаешь заново.

Обе задачи решаются одним и тем же приёмом — трассировкой: аккуратной таблицей, где по шагам записано, что происходит с каждой переменной. Приём скучный, механический и абсолютно надёжный: он не требует догадки и не даёт сбиться. Ниже — теория (свойства алгоритма, фигуры блок-схем, три базовые конструкции), а потом шесть задач формата ОГЭ, разобранных до ответа.

Что такое алгоритм и какие у него свойства

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

В ОГЭ и в контрольных спрашивают пять свойств. Учить их лучше не списком, а через контрпример: что сломается, если свойства не будет.

Исполнитель — тот, кто выполняет алгоритм: человек, робот, компьютер. У каждого исполнителя есть система команд (СКИ) — конечный список того, что он умеет, и среда — то, где он работает. Робот из ОГЭ умеет пять команд и живёт на клетчатом поле; больше он не умеет ничего, и это главное ограничение, из которого растут все задачи.

Четыре способа записать алгоритм

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

Фигуры блок-схемы

Фигур немного, и каждая жёстко закреплена за своим смыслом. Путать нельзя: за фигуру-не-по-назначению на контрольной снимают балл.

Три правила оформления, которые проверяют всегда:

1. Один овал «начало» и один овал «конец». Не два конца в разных ветках — ветки должны сойтись в одну точку перед концом.
2. Из ромба выходят ровно две стрелки, подписанные «да» и «нет». Неподписанная стрелка — ошибка.
3. Стрелки идут сверху вниз и слева направо. Обратная стрелка допустима только для цикла, и её направление обязательно рисуют.

Ошибка: записывать присваивание в ромбе или условие в прямоугольнике. Ромб задаёт вопрос («x > 0?»), прямоугольник выполняет действие («x = x − 1»). Это разные вещи, и по фигуре читающий должен понимать, что происходит, не вчитываясь в текст.

Три базовые конструкции

Любой алгоритм, какой угодно сложности, собирается из трёх конструкций. Это доказанный факт (теорема о структурном программировании), и он полезен практически: увидев незнакомую схему, разложи её на эти три — и она перестанет пугать.

Следование — действия идут подряд, одно за другим.

[начало] -> [ввод a] -> [b = a * 2] -> [вывод b] -> [конец]

Ветвление — в зависимости от условия выполняется одна из двух веток.

            +-----------+
            |  x > 0 ?  |
            +-----------+
             да /   \ нет
               /     \
     [вывод "плюс"]  [вывод "минус"]
               \     /
                \   /
              [дальше]

Бывает неполным: если условие ложно, не делается ничего. Тогда ветка «нет» просто идёт вниз, минуя действие.

Цикл — действия повторяются, пока верно условие.

        +-------------+
   +--> |  s > 0 ?    |--- нет ---> [выход]
   |    +-------------+
   |          | да
   |    [s = s - 12]
   |    [n = n + 6]
   +----------+

Циклы бывают трёх видов, и различать их обязательно:

Задача 1. Трассировка: что выведет алгоритм

Дан алгоритм. Заполните трассировочную таблицу и определите, что будет выведено.

a = 1
b = 1
нц для i от 1 до 5
  a = a + i
  b = b * 2
кц
вывод a, b

Трассировочная таблица — главный инструмент этого раздела. Столбцы: номер шага и все переменные. Каждая строка — состояние после одного прохода цикла.

Ответ: 16 и 32.

Как считать, чтобы не сбиться: на каждой строке бери значение из предыдущей строки, а не то, что уже написал в этой. На шаге 3: a было 4, прибавляем i = 3 → 7. b было 4, умножаем на 2 → 8.

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

Задача 2. ОГЭ, задание 6: наибольшее значение

Ниже приведена программа. При каком наибольшем введённом значении переменной s программа выведет число 42?

s = int(input())
n = 0
while s > 0:
    s = s - 12
    n = n + 6
print(n)

Здесь перебирать числа не нужно — задача решается рассуждением с конца.

Шаг 1. Сколько раз выполнился цикл? За один проход n увеличивается на 6, начальное значение 0. Чтобы получить 42, нужно 42 / 6 = 7 проходов.

Шаг 2. Что это значит для s? За семь проходов из s вычли 7 × 12 = 84. Условие цикла проверяется перед каждым проходом, значит:

• перед седьмым проходом s было ещё положительным: s − 6 × 12 > 0, то есть s > 72;
• после седьмого прохода цикл закончился: s − 7 × 12 ≤ 0, то есть s ≤ 84.

Шаг 3. Ответ. Подходят все целые s от 73 до 84. Наибольшее — 84.

Проверим крайние значения вручную:

При 84 после седьмого вычитания получается ровно 0, условие s > 0 ложно — цикл останавливается. При 85 остаётся 1, и цикл делает восьмой проход. Поэтому 84 — граница.

Тот же приём работает и на «наименьшее значение». Например, для программы с шагами s = s − 7 и n = n + 5 и выводом 30: проходов 30 / 5 = 6, значит s − 5 × 7 > 0 (s > 35) и s − 6 × 7 ≤ 0 (s ≤ 42). Подходят 36…42, наименьшее — 36, наибольшее — 42.

Универсальная формула для таких заданий. Если за проход из s вычитают d, к n прибавляют p, а вывод должен быть N, то число проходов k = N / p, и подходят все s из промежутка:

d * (k - 1)  <  s  <=  d * k

Проверь на нашем примере: d = 12, k = 7 → 72 < s ≤ 84. Сходится.

Задача 3. Исполнитель Робот (задание 15.1)

Робот живёт на клетчатом поле, между клетками бывают стены. Его система команд:

Управляющие конструкции записываются так:

нц пока <условие>
  <команды>
кц

если <условие> то
  <команды>
все

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

Решение:

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

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

Трассировка для стены длиной 3 клетки:

Три главные ошибки в задачах про Робота:

• Перепутан порядок «закрасить» и «вправо». Если написать вправо; закрасить, робот пропустит первую клетку и закрасит одну лишнюю за концом стены.
• Использована длина стены. В условии сказано «длина неизвестна» — значит, нц для i от 1 до 5 недопустимо. Только цикл «пока» с условием об окружении.
• Забыто, что алгоритм должен работать при любой длине. Проверь свой ответ на стене из одной клетки: приведённое решение закрасит ровно одну и остановится.

Задача 4. Исполнитель Вычислитель

У исполнителя две команды: 1. прибавь 1 и 2. умножь на 2. Первая увеличивает число на экране на 1, вторая удваивает его. Составьте алгоритм получения из числа 3 числа 22, содержащий не более 5 команд. В ответе запишите только номера команд.

Перебирать вперёд бесполезно: вариантов много. Идём от ответа назад, разворачивая команды.

Обратные команды: «прибавь 1» разворачивается в «вычти 1», «умножь на 2» — в «раздели на 2» (доступно, только если число чётное).

Читаем прямые команды снизу вверх: 11212.

Проверка вперёд: 3 → (+1) 4 → (+1) 5 → (×2) 10 → (+1) 11 → (×2) 22. Пять команд, ответ верный. Полный перебор подтверждает, что это единственное решение длиной до пяти команд.

Совет: правило движения назад — если число чётное, сначала пробуй делить; если делить нельзя или деление уводит мимо цели, вычитай. Так решаются почти все задачи про Кузнечика, Удвоитель и подобных исполнителей.

Задача 5. Алгоритм Евклида: чтение чужой схемы

Что вычисляет этот алгоритм? Выполните его для a = 48, b = 18.

ввод a, b
нц пока a <> b
  если a > b то
    a = a - b
  иначе
    b = b - a
  все
кц
вывод a

Трассировка:

Вывод: 6.

Это алгоритм Евклида, он находит наибольший общий делитель двух чисел. И правда: НОД(48, 18) = 6.

Такие задания («что делает алгоритм») решаются в два хода: сначала честно трассируешь на конкретных числах, потом смотришь на результат и узнаёшь его. 6 из 48 и 18 — это НОД. Если бы вышло 864, это было бы НОК. Если бы после цикла стояло вывод a + b — что-то другое.

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

Задача 6. Поиск максимума: собираем блок-схему сами

Дана последовательность из N чисел. Найти наибольшее.

Разложим на три конструкции, из которых состоит любой алгоритм.

1. Следование: ввести N, ввести первое число и объявить его текущим максимумом.
2. Цикл: повторить N − 1 раз для остальных чисел.
3. Ветвление внутри цикла: если очередное число больше текущего максимума — заменить максимум.

Блок-схема:

        [начало]
            |
        [ввод N]
            |
      [ввод x; max = x]
            |
    [для i от 2 до N]<-------+
            |                |
        [ввод x]             |
            |                |
       +---------+           |
       | x > max?|           |
       +---------+           |
        да |  | нет          |
    [max = x] |              |
           \  /              |
            \/               |
            +----------------+
            |
       [вывод max]
            |
        [конец]

Тот же алгоритм на Python:

n = int(input())
biggest = int(input())
for i in range(n - 1):
    x = int(input())
    if x > biggest:
        biggest = x
print(biggest)

Проверка: последовательность 4, 17, 3, 17, 9 → вывод 17. Последовательность −5, −2, −9 → вывод −2.

Почему нельзя написать biggest = 0 до цикла. На отрицательных числах программа выдала бы 0 — число, которого в последовательности нет. Поэтому за начальный максимум берут первый элемент, а цикл идёт по оставшимся N − 1. Это одна из самых частых ошибок в задачах на поиск максимума, и проверяют её именно отрицательными данными.

Как самому нарисовать блок-схему за пять шагов

1. Выпиши, что дано и что нужно получить. Это будущие параллелограммы ввода и вывода.
2. Опиши решение словами по пунктам, каждый пункт — одно действие. Не «посчитать всё», а «прибавить x к сумме».
3. Отметь, где есть выбор («если … то …») — это ромбы, и где есть повтор («для каждого», «пока») — это циклы.
4. Нарисуй сверху вниз, соединяя стрелками. Ветки ромба обязательно сведи обратно в одну линию.
5. Протрассируй на двух наборах данных: обычном и крайнем (N = 1, все числа равны, все отрицательные). Если на крайнем ломается — схема неверна, даже если на обычном сработала.

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

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

Брать новое значение переменной вместо старого. В строке a = a + i справа стоит прежнее a. Записывай значения по строкам и бери их только из предыдущей строки.

Путать цикл «пока» и цикл «до». Цикл с предусловием может не выполниться ни разу; цикл с постусловием выполняется минимум один раз. В задачах на границы это меняет ответ.

Забыть, что условие проверяется до тела цикла. Именно из-за этого в задании 6 граница получается s ≤ 84, а не s < 84.

Использовать в задаче про Робота известную длину стены. «Длина неизвестна» — прямой запрет на цикл со счётчиком.

Начинать поиск максимума с нуля. Работает только для заведомо положительных чисел. Начинай с первого элемента.

Рисовать две стрелки из прямоугольника или неподписанные ветки ромба. Формальная ошибка оформления, за которую снимают балл, даже если алгоритм верный.

Частые вопросы

Какие свойства алгоритма спрашивают на ОГЭ?

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

Как решать задание 6 ОГЭ по информатике?

Не перебором, а с конца. Раздели требуемый вывод на приращение счётчика — получишь число проходов цикла k. Дальше запиши двойное неравенство: после (k − 1) проходов условие цикла ещё истинно, после k проходов — уже ложно. Из него сразу видны и наибольшее, и наименьшее подходящее значение.

Что означает ромб в блок-схеме?

Проверку условия. В ромб пишут вопрос, на который есть ответ «да» или «нет» (x > 0?, a <> b?), и из него выходят ровно две стрелки с подписями «да» и «нет». Действие в ромб писать нельзя — для действий есть прямоугольник.

Чем цикл «пока» отличается от цикла «до»?

В цикле «пока» (с предусловием) условие проверяется перед телом: если оно ложно с самого начала, тело не выполнится ни разу. В цикле «до» (с постусловием) условие проверяется после тела, поэтому тело выполняется как минимум один раз. Цикл со счётчиком — отдельный вид: число повторов известно заранее.

Как писать алгоритм для исполнителя Робот, если длина стены неизвестна?

Только через цикл «пока» с условием об окружении: нц пока снизу стена … кц, нц пока справа свободно … кц. Робот не умеет измерять расстояния, он умеет лишь проверять, есть ли стена рядом. Любое число в алгоритме («повторить 5 раз») в такой задаче будет ошибкой.

Обязательно ли рисовать блок-схему, если можно сразу написать программу?

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

Что дальше

• Python в школе: разбор первых 10 задач — те же конструкции, но кодом, с заданием 15.2 ОГЭ.
• Информатика: разбор задач на системы счисления и логику — вторая большая тема ОГЭ.
• Информатика и программирование школьнику — с чего начинать и в каком порядке.
• Как подготовиться к ОГЭ — план по всем предметам, не только по информатике.
• ЕГЭ по информатике: план подготовки — если идёшь в 10-й класс с информатикой.
• Трассировка сходится, а ответ не тот? Выложи задачу на Razbery — там разберут пошагово и покажут, на каком проходе цикла разошлось.