12. Выполнение алгоритмов для исполнителей: Определите количество нулей в строке, получившейся в…
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах $v$ и $w$ обозначают цепочки цифр.
Определите количество нулей в строке, получившейся в результате применения приведённой ниже программы к входной строке $\underbrace{100\ldots00}_{80}$, т.е. к строке, состоящей из единицы, за которой следуют $80$ нулей подряд. В ответе запишите только количество нулей в получившейся строке.
НАЧАЛО
ПОКА нашлось (1)
ЕСЛИ нашлось (10)
ТО заменить (10, 0001)
ИНАЧЕ заменить (1, 00)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Единица в строке всё время ровно одна: обе замены её сохраняют ($10 \to 0001$) либо уничтожают ($1 \to 00$), а появиться новой неоткуда. Поэтому достаточно следить за тем, сколько нулей стоит справа от единицы.
Основная ветка. Пока справа от единицы есть хотя бы один нуль, цепочка $10$ находится, и работает замена $10 \to 0001$. Что она делает: убирает один нуль справа от единицы и дописывает три нуля слева от неё. Единица как бы сдвигается вправо через строку, оставляя за собой по три нуля вместо одного.
Баланс нулей за такой шаг: $-1$ справа и $+3$ слева, то есть общее количество нулей растёт на $2$.
Сколько таких шагов. Справа от единицы изначально $80$ нулей, и каждый шаг съедает ровно один, поэтому замена $10 \to 0001$ сработает $80$ раз. К этому моменту нулей станет $80 + 2 \cdot 80 = 240$, а единица окажется последним символом строки.
Завершающий шаг. Теперь цепочки $10$ нет, но единица есть, поэтому срабатывает ветка ИНАЧЕ: $1 \to 00$, что добавляет ещё $2$ нуля. Единиц в строке не остаётся, условие цикла становится ложным, и программа завершается. Всего цикл отработал $81$ шаг.
Итого нулей: $240 + 2 = 242$ (и это вся длина строки, поскольку единицы в ней больше нет).
Общая формула для $k$ нулей на входе: $3k + 2$. Проверка на малых значениях: при $k = 1$ получается $5$, при $k = 2$ — $8$, при $k = 3$ — $11$; при $k = 80$ имеем $3 \cdot 80 + 2 = 242$.
def run(s):
while '1' in s:
if '10' in s:
s = s.replace('10', '0001', 1) # только первое вхождение
else:
s = s.replace('1', '00', 1)
return s
print(run('1' + '0' * 80).count('0')) # 242