Шешімі: Редактор и цепочки цифр
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Команда «заменить (v, w)» заменяет первое слева вхождение цепочки $v$ на цепочку $w$. Команда «нашлось (v)» проверяет, встречается ли цепочка $v$ в строке, не изменяя её. Цикл выполняется, пока условие истинно.
Дана программа для Редактора:
НАЧАЛО
ПОКА нашлось (25) ИЛИ нашлось (355) ИЛИ нашлось (555)
ЕСЛИ нашлось (25)
ТО заменить (25, 5)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (355)
ТО заменить (355, 52)
КОНЕЦ ЕСЛИ
ЕСЛИ нашлось (555)
ТО заменить (555, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
На вход программе поступает строка, начинающаяся с цифры «3», а затем содержащая $n$ цифр «5», где $n>3$. Определите наименьшее значение $n$, при котором после выполнения программы в строке останутся только цифры «5».
Шешім по шагам
4 қадамДля каждого целого $n>3$ формируем начальную строку вида $3$ и $n$ цифр «5», затем последовательно применяем команды программы до тех пор, пока в строке встречается хотя бы одна из цепочек $25$, $355$ или $555$.
$$s=3\underbrace{55\ldots5}_{n}$$При моделировании учитываем, что за одну итерацию каждая команда заменяет только первое слева вхождение соответствующей цепочки, а проверки следующих команд выполняются уже для изменённой строки.
Проверка последовательных значений $n$ показывает, что при $n<19$ после завершения работы в строке остаётся цифра «3». При $n=19$ все заменяемые цепочки устраняются, и итоговая строка содержит только цифры «5».
Следовательно, наименьшее подходящее значение параметра равно $19$.
Где здесь ошибаются
Выполняют все замены одновременно, а не последовательно.
Заменяют все вхождения цепочки вместо первого слева.
Начинают проверку с неверного значения $n$ или не учитывают условие $n>3$.