Задание 9 Параграф 6 ГДЗ Босова 11 класс (Информатика)

Задача

НАЧАЛО
ПОКА нашлось (33) ИЛИ нашлось (22)
ЕСЛИ нашлось (33)
ТО заменить (33, 2)
ИНАЧЕ заменить (22, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой выше программы к строке, состоящей из:
1) 500 идущих подряд цифр 3;
500 идущих подряд цифр 3;
333333….
2333333…..
2233333…..
333333……
При каждом повторении удаляются три цифры 3 за 4 шага
500 mod 3=2, останется 33 которые заменятся на 2.
Ответ: 2
2) 500 идущих подряд цифр 2;
500 подряд идущих 2;
222222….
322222…
332222….
22222…
Ответ: 3
3) 300 идущих подряд цифр 3 и следующих за ними 200 идущих подряд цифр 2.
300 подряд 3 и за ними 200 подряд 2
300 mod 3=0; останется 333, которые заменятся на 23
200 mod 3=2; останется 22, которые заменятся на 3
Получается 233 и после замены 22, и далее после еще одной замены, 3
Ответ: 3

Подробный ответ

Программа работает так: пока в строке есть подстрока $$33$$ или $$22$$, она заменяет первое слева вхождение $$33$$ на $$2$$, а если $$33$$ нет, то заменяет первое слева вхождение $$22$$ на $$3$$.

1) Строка из 500 цифр 3.

Пока есть $$33$$, каждая замена $$33 \to 2$$ уменьшает число троек на 2. Значит, из 500 троек можно выполнить $$500 : 2 = 250$$ замен, и строка станет из 250 цифр $$2$$.

Теперь в строке есть $$22$$, и программа заменяет их на $$3$$. Каждая замена $$22 \to 3$$ уменьшает число двоек на 2. Из 250 двоек получится $$250 : 2 = 125$$ троек.

Но после этого снова появятся $$33$$, и процесс будет повторяться. Удобнее заметить, что каждые две одинаковые цифры заменяются на одну противоположную, то есть длина строки уменьшается на 1 за каждую пару одинаковых цифр. Для 500 одинаковых троек итоговая строка будет состоять из одной цифры:

$$500 \equiv 2 \pmod 3$$, значит, останется $$33$$, которые заменятся на $$2$$.

2) Строка из 500 цифр 2.

Аналогично, сначала будут заменяться пары $$22 \to 3$$. Так как

$$500 \equiv 2 \pmod 3,$$

в конце останется $$22$$, которые заменятся на $$3$$.

3) 300 цифр 3, затем 200 цифр 2.

Для блока из 300 троек:

$$300 \equiv 0 \pmod 3,$$

значит, после всех замен от него не останется лишних цифр.

Для блока из 200 двоек:

$$200 \equiv 2 \pmod 3,$$

значит, в конце останется $$22$$, которые заменятся на $$3$$.