Задание 12 часть 1
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.
1. заменить (v, w)
2. нашлось (v)
Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (666)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 6)
ИНАЧЕ заменить (666, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из 239 идущих подряд цифр 6? В ответе запишите полученную строку.
Решение
Решим задачу с помощью программы на Python'е.
s = '6'*239
while ('2222' in s) or ('666' in s):
if '2222' in s:
s = s.replace('2222', '6', 1)
else:
s = s.replace('666', '2', 1)
print(s)
Здесь в начале формируется строка, состоящая из 239 шестёрок. Потом эта строка подаётся в программу. Программу переводим с русского языка на язык Питон.
Третий параметр в функции replace обозначает, что замену нужно производить один раз. Это в точности соответствует предложенной функции заменить.
Ответ получается 2266.
Ответ: 2266
Еще подобное задание (другой способ решения)
Исполнитель Редактор получает на вход строку цифр и преобразовывает ее.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Какая строка получится в результате применения приведенной ниже программы к строке, состоящей из 88 идущих подряд цифр 4? В ответе запишите полученную строку.
Аналитическое решение
Алгоритм сначала заменяет в цепочке цифр все четверки на единицы. Потом начинает заменять назад единицы на четверки, но как только в цепочке образуются 3 четверки, алгоритм заменяет их на единицу. Порядок замены имеет значение при поиске ответа, поэтому его нужно обязательно учитывать. Также важно, что замена выполняется всегда в начале цепочки.
Сначала уберем по возможности все четверки из цепочки.
88 / 3 = 29 и 1 в остатке.
Получается, что из цепочки уйдет 29 блоков по 3 четверки и образуется 29 единиц, 1 четверка останется в цепочке в самом конце.
Теперь будем последовательно убирать единицы из цепочки.
29 “1” + 1 “4”
1 “4” + 27 “1” + 1 “4”
2 “4” + 25 “1” + 1 “4”
3 “4” + 23 “1” + 1 “4”
24 “1” + 1 “4”
Как только в цепочке появились 3 четверки, алгоритм заменил их назад на единицу. Суммарно из цепочки ушло 5 единиц. Это действие будет повторяться циклически, поэтому можно посчитать, сколько блоков по 5 единиц уйдет из цепочки.
29 / 5 = 5 и 4 в остатке
Получается, что в цепочке останется 4 единицы и 1 четверка.
11114 → 4114 → 444 → 1
В итоге в цепочке останется только единица.
Решение с помощью компьютера
В самом задании у нас уже написана программа. Остается перевести ее на конкретный язык программирования. Напишем программу на Python.
Она будет выглядеть следующим образом:
Создаем строку, содержащую 88 четверок. Далее запускаем цикл, который будет проверять, есть ли в строке 3 четверки или 2 единицы. Пропиваем условие и замену в строке. Важно в методе replace() указать третий параметр, который отмечает, сколько замен нужно выполнить. По умолчанию replace() сразу заменит все цифры в строке, а нам нужно выполнять замены по одной.
При запуске данной программы мы также получим ответ 1.
Ответ: 1