Question

Заменить в строке все символы 'A' на подстроку 'BC' Заменить в строке все символы 'B' на подстроку 'AС' Заменить в строке все подстроки 'СС' на подстроку 'AD' Процедура может выполняться многократно. В этом случае при очередном вызове на вход процедуре подается строка, получившаяся в результате предыдущего выполнения процедуры. Пусть исходно была строка 'AA', и процедуру выполнили 11 раз. Определите количество символов D в получившейся строке. В ответе укажите целое число. РЕШИТЬ ВРУЧНУЮ

Answer 1

Ответ:

4094

Объяснение:

Посмотрим, как меняется один символ A: A -> BC -> ACC -> AAD. Значит, количество символов A удваивается, а количество символов D увеличивается на количество символов A в предыдущей строке. Изначально А = 2. Тогда в конце выполнения программы D = 2 + 4 + 8 + ... + 2048. Это сумма членов геометрической прогрессии с первым членом 2 и знаменателем 2. Их сумма равна $D=\dfrac{2\cdot(2^{11}-1)}{2-1}=4094$

Answer 2

Давайте последовательно пройдемся через каждую итерацию и замену вручную:

Исходная строка: 'AA'

1. Первая итерация: Замена 'A' на 'BC': 'BCBC' Замена 'B' на 'AC': 'ACCC' Замена 'CC' на 'AD': 'ACAD'

2. Вторая итерация: Замена 'A' на 'BC': 'BCBCAD' Замена 'B' на 'AC': 'ACCCACD' Замена 'CC' на 'AD': 'ACADACD'

3. Третья итерация: Замена 'A' на 'BC': 'BCBCADBC' Замена 'B' на 'AC': 'ACCCACDAC' Замена 'CC' на 'AD': 'ACADACDAC'

4. ...

По сути, на каждой итерации замена символов 'A' на 'BC' и символов 'B' на 'AC' не влияет на количество символов 'D'. А замена 'CC' на 'AD' уменьшает количество символов на 1.

Изначально у нас была одна пара символов 'CC'. На каждой итерации эта пара уменьшается на одну, то есть количество символов 'D' тоже уменьшается на 1 с каждой итерацией.

Так как процедура выполняется 11 раз, количество символов 'D' в конечной строке будет равно изначальному количеству символов 'D' (1) минус 11 (количество итераций): 1 - 11 = -10.

Таким образом, в конечной строке будет -10 символов 'D'.