Задание 12: исполнитель Редактор и обработка строк

Задание 12 (базовый уровень): моделируем работу исполнителя Редактор над строкой.

Исполнитель Редактор обрабатывает строку символов двумя командами: заменить(v, w) заменяет первое вхождение подстроки v на w, а нашлось(v) проверяет, есть ли в строке подстрока v.

Что проверяет задание

Дана начальная строка (часто длинная и однообразная — например, «сто единиц подряд») и программа Редактора с циклом ПОКА. Нужно определить, что станет со строкой: её итоговый вид, длину или количество определённых символов. Вручную прокручивать цикл из сотен шагов нереально — поэтому метод номер один здесь именно моделирование на Python.

Соответствие команд Редактора и Python

Ключевая деталь: команда заменить в Редакторе меняет только первое вхождение. В Python это третий аргумент replace(..., 1). Забыть про единицу — самая частая ошибка: без неё заменятся сразу все вхождения, и поведение разойдётся с настоящим Редактором.

Разбор примера

Пусть дана программа: «ПОКА нашлось('11'): заменить('11', '2')», а начальная строка — семь единиц подряд. Что получится? Каждый шаг превращает первые две единицы в «2». Смоделируем:

def editor(s):
    while "11" in s:                 # нашлось('11')
        s = s.replace("11", "2", 1)  # заменить ПЕРВОЕ '11' на '2'
    return s

for k in [4, 5, 7]:
    start = "1" * k
    result = editor(start)
    print(f"старт '{start}' -> '{result}' (длина {len(result)})")

Вывод:

старт '1111' -> '22' (длина 2)
старт '11111' -> '221' (длина 3)
старт '1111111' -> '2221' (длина 4)

Видна закономерность: каждые две единицы сворачиваются в «2», и если единиц нечётно — одна остаётся в хвосте. Для строки из чётного числа единиц 2k длина результата k; для нечётного 2k+1 — длина k+1.

Более сложный пример с двумя правилами

Часто в цикле несколько команд заменить с условиями. Пусть: «ПОКА нашлось('333') ИЛИ нашлось('111'): ЕСЛИ нашлось('333') ТО заменить('333','1') ИНАЧЕ заменить('111','3')». Просто переносим логику:

def editor(s):
    while "333" in s or "111" in s:
        if "333" in s:
            s = s.replace("333", "1", 1)
        else:
            s = s.replace("111", "3", 1)
    return s

start = "3" * 7 + "1" * 5
print("старт:", start)
print("результат:", editor(start), "длина:", len(editor(start)))

Вывод:

старт: 333333311111
результат: 113311 длина: 6

Когда строка слишком велика: ищем закономерность

Если начальная строка — «100 девяток и 100 единиц», вводить её руками не нужно: сгенерируйте программно и смоделируйте. А чтобы найти общую формулу (для произвольного N), посчитайте результат для нескольких маленьких N и заметьте закономерность:

def editor(s):
    while "11" in s:
        s = s.replace("11", "2", 1)
    return s

# длина результата для строк из N единиц
for N in range(2, 9):
    s = "1" * N
    print(f"N={N}: длина результата = {len(editor(s))}")

Вывод:

N=2: длина результата = 1
N=3: длина результата = 2
N=4: длина результата = 2
N=5: длина результата = 3
N=6: длина результата = 3
N=7: длина результата = 4
N=8: длина результата = 4

Закономерность очевидна: длина = округление N/2 вверх, то есть (N+1)//2. Теперь ответ для N=100 даётся без прогона всего цикла: (100+1)//2 = 50. Связка «смоделировать на малых данных → увидеть формулу → применить к большим» — главный приём задания 12.

Длинная исходная строка из условия

Когда в задании строка задана как, например, «90 нулей, затем 80 единиц», её не нужно набирать вручную — сгенерируйте программно и сразу прогоните. Разберём: «Дана строка из 90 нулей и 80 единиц подряд. Команда: ПОКА нашлось('01') заменить('01','10'). Сколько символов '1' окажется слева от первого '0' в итоге?» Такой цикл «протаскивает» единицы влево; результат смоделируем целиком:

s = "0" * 90 + "1" * 80          # генерируем строку из условия

while "01" in s:
    s = s.replace("01", "10", 1) # каждая замена сдвигает '1' на шаг влево

# сколько единиц подряд в начале строки
prefix_ones = len(s) - len(s.lstrip("1"))
print("длина строки:", len(s))
print("единиц в начале:", prefix_ones)
print("первые символы:", s[:5], "...", "последние:", s[-5:])

Вывод:

длина строки: 170
единиц в начале: 80
первые символы: 11111 ... последние: 00000

Команда заменить('01','10') меняет каждую пару «ноль-единица» местами, постепенно перенося все единицы в начало. Итог предсказуем: все 80 единиц собираются слева, все 90 нулей — справа. Здесь моделирование наглядно показывает смысл алгоритма (это пузырьковая сортировка символов), а заодно мгновенно даёт точный ответ для строки из 170 символов.

Типичные ловушки

• Забыть «,1» в replace. Редактор меняет только первое вхождение; в Python пишите s.replace(v, w, 1).
• Цикл ПОКА — это while с предусловием. Проверка делается перед каждым шагом; если условие сразу ложно, тело не выполнится ни разу.
• Порядок проверок ЕСЛИ/ИНАЧЕ. Точно перенесите приоритет команд — что проверяется и заменяется первым.
• Зацикливание. Если замена не уменьшает строку и условие не перестаёт выполняться, программа зациклится — на экзамене такого не бывает, но при моделировании проверяйте, что строка реально меняется.

Итог

• Редактор переносится в Python один в один: нашлось → in, заменить → replace(v, w, 1), ПОКА → while.
• Замена касается только первого вхождения — обязательно третий аргумент 1.
• Для больших строк находите формулу на малых N и применяйте её к большому N.