Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. заменить (v, w)

нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение "истина", в противном случае возвращает значение "ложь".

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (222)
заменить (222, 1)
заменить (111, 2)
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой программы к строке вида 1…12…2 (2019 единиц и 2119 двоек)?

Vanomasssss Vanomasssss    1   24.11.2020 23:21    7

Ответы
EkaterinaTrenina EkaterinaTrenina  24.12.2020 23:22

Обозначим через m количество единиц, а через n - количество двоек.

В цикле m и n изменяются следующим образом:

n=n-3

m=m+1

m=m-3

n=n+1

Итого: m=m-2; n=n-2. То есть и m и n уменьшаются на 2.

m  и n - нечетные, n-m=100. Следовательно, через некое количество вычислений, последовательно уменьшаясь на 2, m примет значение 3, а n - значение 103.

n=n-3=103-3=100

m=m+1=3+1=4

m=m-3=4-3=1

n=n+1=100+1=101

Теперь цепочки их трех единиц нет. До тех пор, пока цепочка из трех единиц не образуется, операции m=m-3 и n=n+1 мы, по условию, не производим. Повторим несколько вычислений в цикле.

n=n-3=101-3=98

m=m+1=1+1=2

возвращаемся к началу цикла

n=n-3=98-3=95

m=m+1=2+1=3

m=m-3=3-3=0

n=n+1=95+1=96

возвращаемся к началу цикла

n=n-3=96-3=93

m=m+1=0+1=1

Значения m=1 и n=101 изменились на m=1 и n=93.

То есть m как было, так и осталось равным единице, а n уменьшилось на 8.

8*[101/8]=8*12=96

101-96=5

То есть, через некоторое количество вычислений, мы придем к следующим значениям: m=1 и n=5

Далее получаем:

n=n-3=5-3=2

m=m+1=1+1=2

Поскольку строка из трех двоек больше не находится, цикл завершается.

На выходе получаем строку из двух единиц и двух двоек.

ПОКАЗАТЬ ОТВЕТЫ
Другие вопросы по теме Информатика