Question

Была исходная последовательность символов: AAABBABB В конец этой последовательности дописали ее копию, но развернутую зеркально (символы взяли в обратном порядке). Получилась строка: AAABBABBBBABBAAA Эту операцию повторили еще три раза, каждый раз дописывая в зеркальном отображении всю последовательность, полученную на предыдущем шаге. В результате получилась последовательность из 128 символов. В получившейся последовательности заменили все тройки идущих подряд символов BAB на ABA. Эту операцию повторяли до тех пор, пока тройки идущих подряд символов BAB не перестали встречаться в последовательности. Сколько букв B осталось в результирующей последовательности?

Answer 1

Тут не очень длинная строка получилась, её можно обработать и в таблице Excel.

Собственно, я составил таблицу для решения этой задачи (она прилагается к решению).
Самое большое преобразование там- это расстановка символов в обратном порядке.

Результат в таблице- после всех возможных замен символов BAB, в полученной строке осталось 24 буквы B.

Answer 2

Давайте разберемся в данной задаче шаг за шагом.

Исходная последовательность: AAABBABB

1. Дописываем зеркальное отображение: AAABBABBBBABBAAA (длина 16 символов)
2. Дописываем предыдущую последовательность зеркально: AAABBABBBBABBAAAAABBABBBBABBAAA (длина 32 символа)
3. Дописываем предыдущую последовательность зеркально: AAABBABBBBABBAAAAABBABBBBABBAAAAABBABBBBABBAAA (длина 64 символа)
4. Дописываем предыдущую последовательность зеркально: AAABBABBBBABBAAAAABBABBBBABBAAAAABBABBBBABBAAAAABBABBBBABBAAA (длина 128 символов)

Теперь заменяем все тройки идущих подряд символов BAB на ABA:

AAABBABBBBABBAAAAABBABBBBABBAAAAABBABBBBABBAAA (исходная последовательность)

Первая замена: AABABAABBBABAABAAAAABABAABBBABAABAAAAABABAABBBABAABAAA

Видим, что теперь у нас нет подстроки BAB. Таким образом, после этой операции все буквы B исчезли из строки. В результирующей последовательности не осталось ни одной буквы B.