Карточки
Тесты
Главная
Курсы
Подписка
12. Выполнение алгоритмов для исполнителей: #298426
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦКонструкция ЕСЛИ–ИНАЧЕ одна, значит, за проход цикла выполняется ровно одна замена. Приоритет у цепочки $2222$: как только четыре двойки набрались, они тут же схлопываются, и до восьмёрок очередь не доходит.
Проследим за строкой из одних восьмёрок. Пока двоек меньше четырёх, работает ветка ИНАЧЕ: $8888 \to 22$, причём заменяется самое левое вхождение, поэтому двойки копятся в начале строки, а восьмёрки остаются справа сплошным блоком. Двух таких шагов хватает, чтобы получить $2222$ и потерять $8$ восьмёрок. Сразу после этого срабатывает первая ветка: $2222 \to 88$, двойки исчезают полностью, а восьмёрок становится на $2$ больше.
Итого за три шага строка снова состоит из одних восьмёрок, но их стало на $8 — 2 = 6$ меньше. Такой цикл повторяется, пока восьмёрок хватает на две замены, то есть пока их не меньше $8$.
Считаем: $70 = 6 \cdot 11 + 4$, поэтому после $11$ полных циклов ($33$ шага) остаются $4$ восьмёрки.
Разбираем остаток вручную. Строка $8888$: двоек нет, срабатывает $8888 \to 22$, получается $22$. Теперь ни $2222$ (двоек всего две), ни $8888$ в строке нет — условие цикла ложно, программа останавливается. Всего цикл отработал $33 + 1 = 34$ шага.
Ключевой момент — остаток от деления на $6$. Полезно помнить, чем заканчивается дело для остатков $4$, $5$, $6$, $7$: $22$, $228$, $2288$, $22888$ соответственно.
def run(s):
while '2222' in s or '8888' in s:
if '2222' in s:
s = s.replace('2222', '88', 1) # только первое вхождение
else:
s = s.replace('8888', '22', 1)
return s
print(run('8' * 70)) # 22
20
