Разбор задачи B8 (демо ЕГЭ 2011)
Строки (цепочки символов латинских букв) создаются по следующему правилу.
Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется i-я буква алфавита), к ней слева дважды подряд приписывается предыдущая строка.
Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) AAB
(3) AABAABC
(4) AABAABCAABAABCD
Латинский алфавит (для справки): ABCDEFGHIJKLMNOPQRSTUVWXYZ
Имеется задание:
«Определить символ, стоящий в n-й строке на позиции 2n–1– 5, считая от левого края цепочки».
Выполните это задание для n = 8.
Определим позицию искомого символа:
2n–1– 5=28-1-5=27-5=128-5=123.
Введем обозначение: "AABAABCAABAABCD"-().
Распишем, какие будут созданы строки с 5-го по 8-й шаг.
(5) ()()E
(6)()()E ()()E F
(7) ()()E()()EF ()()E()()EF G
(8) ()()E()()EF()()E()()EFG ()()E()()EF()()E()()EFG H
Чтобы определить позиции символов, нужно определить сколько символов образуется на каждом шаге. Количество символов определяется по формуле:
Ni=2i-1,
где i-шаг.
На 7-м шаге образуется N7=27-1=127 символа:
(7) ()()E()()EF ()()E()()EF G127
На 8-м шаге образуется N8= 28-1=255 символов. Нам нужно найти 123 позицию. До 127 позиции символов на 7-м и 8-м шаге одинаковы:
(7) ()()E()()EF ()()E()()EF G
(8) ()()E()()EF()()E()()EFG ()()E()()EF()()E()()EFG H
Поэтому будем смотреть по 7-му шагу. Так проще,т.к. там меньше элементов. Определим позиции элементов, близкие к искомому:
(7) ()()E()()EF ()()E()()E125F126 G127
Получается,что элемент в позиции 123 нужно смотреть в ():
(4) AABAABCAABAABC123D124
Получили:С.