Question

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр. заменить (v, w) нашлось (v) Дана программа для исполнителя Редактор: ПОКА нашлось (555) ИЛИ нашлось (333) ЕСЛИ нашлось (333) ТО заменить (333, 5) ИНАЧЕ заменить (555, 3) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА Дана строка, состоящая из 500 цифр 5. Сколько пятёрок было удалено за время обработки строки по этой программе?

Answer 1

После первого шага алгоритма из 500 "5" получается 1 "3" и 497 "5"; после второго - 2 "3" и 494 "5", после третьего - 3 "3" и 491 "5"; после четвертого - 492 "5". Таким образом, после каждых 4 шагов количество "5" уменьшается на 8.

К последнему шагу алгоритма в строке останется 500-62*8 = 4 "5".

После последнего шага - 1 "3" и 1 "5", т.е. "35".

Таким образом, за время обработки из строки удалится 500-1 = 499 пятёрок.

Answer 2

Давайте разберем по шагам, что происходит при выполнении программы на данной строке из 500 цифр 5:

1. Изначально имеем строку из 500 цифр 5.
2. В цикле ПОКА выполняем следующие шаги:
   • Проверяем наличие подстроки "555". Найдено 0 раз.
   • Проверяем наличие подстроки "333". Найдено 0 раз.
   • Поскольку оба условия не выполняются (ноль раз), то выходим из цикла ПОКА.

Таким образом, ни одной пятёрки не было удалено за время обработки строки по данной программе. Вся строка состояла из цифр 5, но программа не содержит команд, которые удаляют символы, а только преобразуют определенные цепочки цифр.