Решение: Преобразование строки цифр
Исполнитель Редактор получает на вход строку цифр и может выполнять команды $\text{заменить}(v, w)$ и $\text{нашлось}(v)$. Команда $\text{заменить}(v, w)$ заменяет первое слева вхождение цепочки $v$ на цепочку $w$, а команда $\text{нашлось}(v)$ проверяет наличие цепочки $v$ в строке.
На вход программы подали строку, состоящую из 57 идущих подряд цифр 9. Чему равна сумма цифр в строке, которая получится после выполнения программы?
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (999)
ЕСЛИ нашлось (222)
ТО заменить (222, 19)
ИНАЧЕ заменить (999, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Решение по шагам
4 шагаИз исходной последовательности цифр 9 первые три замены $999$ на $2$ дают цепочку $222$. Она заменяется на $19$, после чего строка имеет вид $1\cdot 9^{49}$.
$$9^{57}\to 222\cdot 9^{48}\to 19\cdot 9^{48}=1\cdot 9^{49}$$Затем для образования очередной цепочки $222$ требуется заменить три цепочки $999$ на $2$. После замены $222$ на $19$ количество цифр 9 уменьшается на 8, а количество цифр 1 увеличивается на 1.
$$49\to41\to33\to25\to17\to9\to1$$После шести таких циклов цепочка принимает вид семи цифр 1 и одной цифры 9. Цепочек $222$ и $999$ больше нет, поэтому цикл завершается.
$$1^7\cdot9$$Находим сумму цифр итоговой строки.
$$7\cdot1+9=16$$Где здесь ошибаются
Считать, что все 57 цифр 9 сначала независимо заменяются на цифры 2.
Не учитывать, что после замены $222$ на $19$ новая цифра 9 присоединяется к оставшейся цепочке цифр 9.
Остановить выполнение после первой замены $222$ на $19$.