12 мин чтенияисполнителиЧертёжникРоботЧерепахаРедакторзадание 6задание 12КЕГЭ
Исполнители: Чертёжник, Робот, Черепаха и Редактор
Разбор исполнителей из заданий 6 и 12: смещения и циклы Чертёжника, поле Робота с условиями, Черепаха и точки внутри фигуры, Редактор с заменой подстрок и инвариантами.
Открываем тему…
Что проверяют задания про исполнителей
В заданиях 6 и 12 нужно выполнить алгоритм исполнителя и определить итоговое положение, число клеток или результат преобразования строки. Условие даёт систему команд, а правильная техника — не проигрывать длинный алгоритм в уме, а выявить регулярность (цикл, сдвиг, инвариант) либо написать короткую модель на Python.
- Чертёжник: команды «сместиться на (a, b)», «повтори k [ … ]»; конечное положение — сумма смещений, умноженная на число повторов.
- Черепаха: «вперёд n», «направо m», «повтори k [ … ]», «поднять/опустить хвост»; обычно просят число точек с целыми координатами внутри фигуры или на её границе.
- Робот: движение по клеточному полю со стенками, команды вида «ПОКА справа свободно ВПРАВО», «ЕСЛИ … ТО … ИНАЧЕ …»; ответ — клетка остановки, число клеток обхода или число стартовых клеток с заданным свойством.
- Редактор: «заменить (v, w)» меняет первое слева вхождение v на w; «нашлось (v)» проверяет наличие v; цикл «ПОКА … ИЛИ …» с несколькими правилами.
Чертёжник и Черепаха
ПримерЧертёжник: возврат в начальную точку
Чертёжник начинает в точке (0, 0). Алгоритм: «Повтори 3 [ Сместиться на (2, 3); Сместиться на (−1, −4) ]; Сместиться на (a, b)». При каких a и b чертёжник вернётся в точку (0, 0)?
Решение
За один проход тела цикла смещение равно (2 − 1, 3 − 4) = (1, −1). Три повтора дают (3, −3). Чтобы вернуться, последняя команда должна компенсировать это смещение: (a, b) = (−3, 3).
Проверка: 3·(1, −1) + (−3, 3) = (0, 0). Если в условии просят «сумму a + b» или «наименьшее a», вычисляйте её уже по найденной паре. Для вложенных повторов умножайте суммарное смещение внутреннего цикла на число его повторений, затем на внешнее.
ПримерЧерепаха: точки внутри прямоугольника
Черепаха стоит в начале координат, хвост опущен, голова направлена вверх вдоль оси Oy. Алгоритм: «Повтори 2 [ Вперёд 8 Направо 90 Вперёд 5 Направо 90 ]». Сколько точек с целыми координатами лежит строго внутри получившейся фигуры?
Решение
За один проход Черепаха проходит 8 единиц вперёд, поворачивает направо, проходит 5 единиц и снова поворачивает. После двух повторов получается замкнутый контур — прямоугольник 8 × 5 (стороны вдоль и поперёк исходного направления).
Внутренние целые точки: по длине сторон 8 и 5 внутри находятся 8 − 1 = 7 и 5 − 1 = 4 целых позиции, всего 7·4 = 28. Точек на границе 2·(8 + 5) = 26; всего вместе с границей 28 + 26 = 54 = 9·6.
Формула для прямоугольника a × b: строго внутри (a − 1)(b − 1), включая границу (a + 1)(b + 1). Для сложной фигуры используйте формулу Пика: S = I + B / 2 − 1, где I — внутренние целые точки, B — граничные.
Робот на клеточном поле
ПримерРобот: остановка по условию
Робот стоит в клетке S. Символ # — стена, точка — свободная клетка. «ПОКА справа свободно ВПРАВО» выполняется, пока справа от Робота нет стены. Поле:
#########
#S..#...#
#.#.#.#.#
#.#...#.#
#.#####.#
#.......#
#########
Программа:
ПОКА справа свободно ВПРАВО
ПОКА снизу свободно ВНИЗ
ПОКА справа свободно ВПРАВО
ПОКА сверху свободно ВВЕРХ
В какой клетке остановится Робот (строка и столбец отсчитываются от левого верхнего угла рисунка, нумерация с 1) и сколько всего шагов он сделает?
Решение
Моделируем по циклам.
ВПРАВО: 2 шага, позиция (строка 2, столбец 4).
ВНИЗ: 2 шага, позиция (строка 4, столбец 4).
ВПРАВО: 2 шага, позиция (строка 4, столбец 6).
ВВЕРХ: 2 шага, позиция (строка 2, столбец 6).
Итог: Робот остановится в клетке (строка 2, столбец 6), всего сделает 8 шагов.
Программа на Python (grid — список строк поля, индексы с нуля):
r, c = 1, 1
steps = 0
for dr, dc in [(0, 1), (1, 0), (0, 1), (-1, 0)]:
while grid[r + dr][c + dc] != '#':
r += dr
c += dc
steps += 1
print(r + 1, c + 1, steps)
Редактор: замена подстрок
ПримерРедактор: сортировка нулей и единиц
Программа: «ПОКА нашлось (01) заменить (01, 10)». На вход подана строка 0101101. Сколько замен выполнит программа и какая строка получится?
Решение
Каждая замена 01 → 10 передвигает единицу на одну позицию влево и уничтожает ровно одну «инверсию» — пару (0 слева, 1 справа). Поэтому число замен равно числу таких пар: для строки 0101101: 8. Итоговая строка не содержит «01», то есть все единицы стоят слева, все нули справа: 1111000.
Подсчёт инверсий:
inv = zeros = 0
for ch in s:
if ch == '0':
zeros += 1
else:
inv += zeros
print(inv)
ПримерРедактор: сложение в унарной системе
Программа: «ПОКА нашлось (+1) заменить (+1, 1+); затем заменить (+, пусто)». На вход подана строка 111+11. Какая строка получится?
Решение
Пока справа от знака «+» есть единица, она перепрыгивает через плюс налево: 111+11 → 1111+1 → 11111+. После этого «+1» больше нет, остаётся стереть «+». Результат 11111 — унарная запись числа 5 = 3 + 2. Общее правило: строка из n единиц, плюс и m единиц превращается в n + m единиц.
Идея важна для задач с длинными строками: вместо 10⁵ шагов достаточно понять, что программа делает с количествами символов.
ПримерРедактор: инвариант и длинная строка
Программа: «ПОКА нашлось (11) ИЛИ нашлось (222): ЕСЛИ нашлось (11) ТО заменить (11, 2) ИНАЧЕ заменить (222, 1)». На вход подана строка из 55 единиц. Чему равна сумма цифр результата?
Решение
Запускаем модель (Python):
s = '1' * 55
while '11' in s or '222' in s:
s = s.replace('11', '2', 1) if '11' in s else s.replace('222', '1', 1)
print(s, sum(map(int, s)))
Программа останавливается после 42 замен и даёт строку «221»; сумма цифр равна 5.
Проверка инвариантом: припишем цифре 1 вес 1, цифре 2 вес 2 и будем считать суммарный вес по модулю 5. Замена 11 → 2 сохраняет вес (2 = 2), замена 222 → 1 даёт 6 ≡ 1 (mod 5). Для 55 единиц вес 55 ≡ 0, а у результата вес 5 ≡ 0 (mod 5) — совпадает.
ПримерШаблон модели Редактора
Как оформить на Python произвольную программу Редактора с несколькими правилами и приоритетом «первое подходящее»? Примените шаблон к программе «ПОКА нашлось (12) ИЛИ нашлось (21): ЕСЛИ нашлось (12) ТО заменить (12, 21) ИНАЧЕ заменить (21, 1)» и входу 121212.
Решение
Шаблон: список правил в порядке приоритета и цикл, который применяет первое подходящее правило.
rules = [('12', '21'), ('21', '1')]
s = '121212'
while any(a in s for a, _ in rules):
for a, b in rules:
if a in s:
s = s.replace(a, b, 1)
break
print(s)
Замена 12 → 21 переставляет цифры, а 21 → 1 удаляет двойку. Результат для входа 121212: «111» (замен выполнено 9). Метод replace(a, b, 1) заменяет именно первое вхождение слева, как и команда Редактора. Если программа может не завершиться, добавьте счётчик шагов и лимит.