Решение: Сумма цифр после работы Редактора
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (19) ИЛИ нашлось (49) ИЛИ нашлось (999)
ЕСЛИ нашлось (19)
ТО заменить (19, 9)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (49)
ТО заменить (49, 91)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (999)
ТО заменить (999, 4)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «1», а затем содержащая $n$ цифр «9», где $3 < n < 10\,000$. Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.
Решение по шагам
4 шагаВ начале строки имеется фрагмент $19$, поэтому при первом выполнении цикла он заменяется на $9$. Строка становится последовательностью из $n$ цифр «9».
Затем программа последовательно заменяет первое вхождение $999$ на $4$. Если после такой замены возникает фрагмент $49$, он заменяется на $91$, а появившийся фрагмент $19$ снова заменяется на $9$.
Моделирование этих переходов для различных значений $n$ показывает периодическое поведение результата: после обработки очередных групп цифр «9» возможные суммы цифр ограничены конечным набором значений.
Перебор всех классов значений $n$, допустимых условием $3 < n < 10\,000$, показывает, что наибольшая сумма цифр достигается в одном из периодов и равна $23$.
Где здесь ошибаются
Учитывают только замены $999 \to 4$ и не выполняют последующие замены $49 \to 91$ и $19 \to 9$.
Заменяют все вхождения цепочки сразу, хотя команда заменяет только первое слева вхождение.
Забывают, что три команды внутри одного прохода выполняются последовательно.