Решать задания
Информатика · тема 13 из 13 · ОГЭ № 15 · ЕГЭ № 18

Исполнитель Робот: циклы, условия и путь по таблице

Как читать программы Робота на клетчатом поле со стенами (циклы «пока» и условия «если») и как в ЕГЭ-18 находить наибольшую и наименьшую сумму пути по таблице.

16 мин чтенияОГЭЕГЭ12 заданий

Коротко

главное за 30 секунд
  1. Робот ходит по клеткам: вверх, вниз, влево, вправо; в стену упираться нельзя, иначе отказ
  2. Проверки: «справа свободно», «слева стена» и т. д.; закрасить — красит клетку, где стоит Робот
  3. Цикл «нц пока условие … кц» повторяет тело, пока условие истинно (проверка до каждого шага)
  4. Программу разбирайте пошагово: запишите положение Робота и закрашенные клетки после каждого действия
  5. ЕГЭ-18: D[i][j] = a[i][j] + max(D[i−1][j], D[i][j−1]) — наибольшая сумма пути вправо и вниз (min — для наименьшей)

Поле, стены и команды

Поле Робота — клетчатая таблица. Клетки нумеруют: строки сверху вниз, столбцы слева направо. Между соседними клетками может стоять стена (на рисунках — жирная линия). Через стену Робот пройти не может; если команда ведёт в стену, происходит отказ.

Команды: вверх, вниз, влево, вправо — шаг на одну клетку; закрасить — закрашивает клетку, где стоит Робот.
Проверки: «сверху свободно», «снизу свободно», «слева свободно», «справа свободно» и обратные «… стена».
Проверь себя. Робот стоит в клетке (2, 1), между клетками (2, 3) и (2, 4) — стена. Робот повторяет «вправо», пока справа свободно. В каком столбце он остановится?

Ответ: 3

123451234Ркомандывверх, вниз, влево, вправозакраситьпроверкисправа свободно / стенасверху, снизу, слева — так жев стену идти нельзя: отказ
Рис. 1. Поле Робота: строки сверху вниз, столбцы слева направо; жирная линия — стена, Р — Робот в клетке (2, 1)

Цикл «пока» и ветвление «если»

нц пока справа свободно
  вправо
кц

Цикл «пока» сначала проверяет условие. Если оно ложно с самого начала, тело не выполнится ни разу. После выхода из цикла Робот стоит у стены.

если снизу свободно
  то закрасить
все

Ветвление «если» выполняет действие только при истинном условии; можно добавить «иначе».

Ловушка. В цикле «пока справа свободно: закрасить; вправо» последняя клетка перед стеной не закрашивается — цикл завершается раньше. Если нужно закрасить и её, после цикла ставят ещё одну команду «закрасить».
справа свободно?давправонетконец цикла (кц)
Рис. 2. Цикл «нц пока справа свободно: вправо»: условие проверяется до каждого шага

Как разбирать программу

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

Пример. Поле 4×6, Робот в клетке (1, 1), стены под клетками (1, 2) и (1, 4). Программа: «нц пока справа свободно: если снизу свободно, то закрасить; вправо». Робот проходит клетки (1,1)…(1,5). Снизу свободно у клеток 1, 3, 5 — закрашены три клетки. В клетке (1, 6) справа стена поля, цикл завершается.

Стены поля тоже считаются стенами: у края поля «справа свободно» ложно.
1234561234закрашены клетки 1, 3, 5в клетке 6 справа граница— цикл закончилсяответ: 3 клетки
Рис. 3. Разбор программы: Робот идёт по 1-й строке, клетку закрашивает, если снизу свободно (стены под клетками 2 и 4)

ЕГЭ-18: наибольшая и наименьшая сумма пути

В ЕГЭ-18 Робот идёт из левой верхней клетки в правую нижнюю, двигаясь только вправо или вниз. В каждой клетке лежит число (монеты). Нужно найти наибольшую и наименьшую сумму чисел вдоль пути.

Пусть D[i][j] — лучшая сумма пути до клетки (i, j). Тогда D[i][j] = a[i][j] + max(D[i−1][j], D[i][j−1]) для наибольшей суммы; с min — для наименьшей. В первой строке и первом столбце берут единственного «предка».

Пример. Таблица 3×4: (1, 3, 2, 5), (4, 1, 6, 2), (2, 7, 1, 3). Наибольшая сумма: первая строка D = 1, 4, 6, 11; вторая: 5, 6, 12, 14; третья: 7, 14, 15, 18. Наименьшая — 15.

Проверь себя. Сколько существует путей из левого верхнего угла в правый нижний в таблице 4×5, если можно идти только вправо и вниз? (Формула сочетаний C(7, 3).)

Ответ: 35

113426511451661221427714115318малое число — a (монеты)крупное число — DD = a + max(D сверху, D слева)путь: 1 → 4 → 2 → 7 → 1 → 3наибольшая сумма: 18
Рис. 4. ЕГЭ-18: в клетке — наибольшая сумма пути вправо и вниз: D = a + max(сверху, слева); лучший путь выделен
Практика

Закрепите тему: 12 заданий для ОГЭ и ЕГЭ

От простых к сложным: базовый уровень — 2, повышенный — 8, высокий — 2. Мгновенная проверка, подсказки, подробные решения и тренажёр ошибок.

Решать задания по теме Флеш-карточки