Решение: Редактор и замены строк
Исполнитель «Редактор» получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки цифр v на цепочку цифр w. Если вхождений нет, строка не изменяется. Команда «нашлось (v)» проверяет наличие цепочки v в текущей строке, не изменяя её. Цикл выполняется, пока его условие истинно.
Программа:
НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
ЕСЛИ нашлось (12)
ТО заменить (12, 2)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (322)
ТО заменить (322, 21)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (222)
ТО заменить (222, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «2», где 3 < n < 10000. Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.
Решение по шагам
3 шагаДля каждого допустимого значения $n$ моделируем выполнение программы над строкой $1\underbrace{22\ldots2}_{n\text{ цифр}}$. После каждой итерации замены выполняются именно в указанном порядке.
Замена $12\to2$ устраняет начальную единицу и превращает начальный фрагмент строки в последовательность цифр «2». Затем замены $222\to3$ и $322\to21$ постепенно сокращают строку и изменяют сумму её цифр.
$$12\to2,\qquad 322\to21,\qquad 222\to3$$Проверка всех возможных состояний по мере увеличения $n$ показывает, что сумма цифр результата периодически повторяется с ограниченными значениями. Наибольшее значение, встречающееся при $3<n<10000$, равно $17$.
$$S_{\max}=17$$Где здесь ошибаются
Выполняют все возможные замены одного типа за итерацию вместо только первого найденного вхождения.
Меняют порядок выполнения трёх условных команд.
Останавливают цикл после одной итерации.
Учитывают исходную сумму цифр вместо суммы цифр в конечной строке.