Задание 12 ЕГЭ по информатике

1. 1. Шаг 0. Важная деталь устройства программы: внутри одного оборота цикла стоят два независимых ЕСЛИ, а не ЕСЛИ-ИНАЧЕ. Значит, за один оборот замена может сработать дважды: сначала по правилу «22 → 4», потом по правилу «44 → 8». Это первое место, где теряют ответ.
2. 2. Начальная строка: 2222222222222 (тринадцать двоек).
3. 3. Оборот 1. Есть «22» → заменяем первое слева: 422222222222. Есть ли «44»? Нет — второе ЕСЛИ ничего не делает.
4. 4. Оборот 2. Есть «22» → 44222222222. Теперь появилось «44» → заменяем: 8222222222. За этот оборот сработали обе замены.
5. 5. Оборот 3. Есть «22» → 842222222. «44» нет.
6. 6. Оборот 4. Есть «22» → 84422222. Появилось «44» → 8822222.
7. 7. Оборот 5. Есть «22» → 884222. «44» нет — в строке стоит «88», а не «44».
8. 8. Оборот 6. Есть «22» → 88442. Появилось «44» → 8882.
9. 9. Оборот 7. Проверка условия цикла: «22» в строке 8882 нет, «44» нет. Цикл заканчивается.
10. 10. Ответ на первый вопрос: получится строка 8882. Ответ на второй: команда «заменить» сработала 9 раз — сосчитайте стрелки в трассировке.
11. 11. Шаг 9. Закономерность, которая видна из трассировки. Две двойки схлопываются в четвёрку, две четвёрки — в восьмёрку, то есть восьмёрка «стоит» четырёх двоек, четвёрка — двух. Значит, из n двоек получается n // 4 восьмёрок, а остаток n % 4 дописывается справа: 0 — ничего, 1 — «2», 2 — «4», 3 — «42». Проверим на нашем случае: 13 // 4 = 3 восьмёрки, остаток 1 даёт «2», итого 8882 ✔ Для восьми двоек получилось бы «88», для пятнадцати — «88842».
12. 12. Шаг 10. Самая частая ошибка — читать два ЕСЛИ как ЕСЛИ-ИНАЧЕ и делать по одной замене за оборот. Тогда «44» будет схлопываться не сразу, и строка пойдёт другим путём. Второй источник ошибок — забыть, что заменить меняет только первое вхождение: замена всех сразу даёт совсем другой ответ.

Ответ: 8882, замен 9

1. 1.

   s = '2' * 13
   zamen = 0
   while '22' in s or '44' in s:
       if '22' in s:
           s = s.replace('22', '4', 1)     # третий аргумент 1 — заменить одно вхождение
           zamen += 1
       if '44' in s:
           s = s.replace('44', '8', 1)
           zamen += 1
   print(s, zamen)

2. 2. Шаг 1. Ключ ко всему симулятору — третий аргумент replace. s.replace('22', '4') заменит все вхождения сразу, а Редактор меняет только первое слева. Единица в третьем аргументе и означает «одно вхождение». Пропустить её — значит смоделировать не того исполнителя.
3. 3. Шаг 2. Оператор in для строк — это ровно нашлось (v): '22' in s истинно, когда подстрока встречается. Цикл while — это ПОКА, а два if подряд — два ЕСЛИ из условия.
4. 4. Шаг 3. Программа печатает 8882 9: та же строка и то же число замен, что и в ручной трассировке.
5. 5.

   Шаг 4. Вторая задача банка: «ПОКА нашлось (83) заменить (83, 38) КОНЕЦ ПОКА. На вход подаётся строка из шести цифр 8, за которыми идут четыре цифры 3». Меняется только тело цикла:

   s = '8' * 6 + '3' * 4
   zamen = 0
   while '83' in s:
       s = s.replace('83', '38', 1)
       zamen += 1
   print(s, zamen)

6. 6. Шаг 5. Программа печатает 3333888888 24. Разберём, почему. Замена «83 → 38» меняет местами соседние восьмёрку и тройку, длина строки не меняется — это ровно один шаг пузырьковой сортировки. Каждое срабатывание переносит одну тройку на одну позицию влево.
7. 7. Шаг 6. Цикл кончится, когда ни одна тройка не стоит правее восьмёрки, то есть когда все тройки соберутся слева: 3333888888. А число замен равно числу пар «восьмёрка левее тройки» в исходной строке: каждая из четырёх троек должна пройти мимо всех шести восьмёрок, итого 4 · 6 = 24 ✔
8. 8. Шаг 7. Вот зачем нужны оба способа. Симулятор даёт ответ за секунду, но рассуждение про «4 · 6» позволяет ответить на вопрос для строки из 70 восьмёрок и 50 троек, где симулятор тоже справится, а вот ручная трассировка — нет. И оно же страхует от опечатки в коде: если программа выдаст что-то кроме 24, ошибка в программе, а не в арифметике.

Ответ: 8882 и 9; 3333888888 и 24

1. 1. Каждый такт машины — это три действия подряд: прочитать символ под головкой, записать новый, сдвинуться и перейти в новое состояние. Команду выбирают по паре «текущее состояние, прочитанный символ», и другого правила выбора нет.
2. 2. Такт 1. Состояние q0, под головкой 0. Подходит первая строка таблицы: записать 1, шаг вправо, остаться в q0. Лента: 111 (изменилась первая цифра), головка на второй позиции.
3. 3. Такт 2. Состояние q0, под головкой 1. Вторая строка: записать 0, вправо, q0. Лента: 101, головка на третьей позиции.
4. 4. Такт 3. Состояние q0, под головкой 1. Снова вторая строка: записать 0, вправо, q0. Лента: 100, головка ушла за последнюю цифру — там пусто.
5. 5. Такт 4. Состояние q0, под головкой A (пустой символ). Третья строка: оставить A, S — стоп, перейти в q1. Машина остановилась.
6. 6. Ответ: на ленте 100. Программа поменяла каждый бит на противоположный — это побитовое отрицание: было 011, стало 100.
7. 7. Обратите внимание на роль пустого символа. Он не украшение таблицы: именно встреча с ним говорит машине, что цепочка кончилась. Без строки «q0, A → …» машина не знала бы, что делать, и остановилась бы аварийно, а не по команде.
8. 8. И на роль состояний. Здесь состояние всего одно рабочее, поэтому машина просто идёт слева направо. В реальных заданиях состояний несколько: q0 — «иду вправо и инвертирую», q1 — «возвращаюсь к началу», q2 — «ищу первую единицу». Состояние — это память машины о том, что она уже сделала, и другой памяти у неё нет.

Ответ: 100

1. 1. Шаг 1. Прогонять пятьдесят символов вручную бессмысленно, поэтому смотрим на первые шаги и ищем закон. Строка «22222…»: первое вхождение «222» — это три левые двойки, они превращаются в «3». Получается «3» и сорок семь двоек.
2. 2. Шаг 2. Второй оборот. Тройка не входит ни в какое вхождение «222», поэтому замена снова захватывает три левые из оставшихся двоек: «33» и сорок четыре двойки.
3. 3. Шаг 3. Закон найден: каждый оборот съедает ровно три двойки и добавляет одну тройку, причём тройки копятся слева и в дальнейшем не участвуют.
4. 4. Шаг 4. Значит, процесс идёт, пока двоек остаётся не меньше трёх. Делим с остатком: 50 = 3 · 16 + 2. Шестнадцать оборотов, после которых остаются две двойки — вхождения «222» больше нет, цикл заканчивается.
5. 5. Шаг 5. Ответ: строка 3333333333333333 22 без пробела, то есть шестнадцать троек и две двойки, длина 18. Команда «заменить» сработала 16 раз.
6. 6.

   Шаг 6. Проверка симулятором:

   s = '2' * 50
   zamen = 0
   while '222' in s:
       s = s.replace('222', '3', 1)
       zamen += 1
   print(s, len(s), zamen)

7. 7. Шаг 7. Программа печатает ту же строку, её длину 18 и число замен 16 ✔
8. 8. Шаг 8. Почему ответ — это деление с остатком. Каждая замена уменьшает число двоек ровно на три, а начальное их число известно. Такой взгляд («что уменьшается на сколько за одну замену») решает большинство задач линии 12 про число срабатываний, и он же подсказывает, чем закончится строка: остатком от деления.

Ответ: 16 троек и две двойки; замен 16