B8
(повышенный уровень, время – 10 мин)
Тема: Анализ алгоритма построения
последовательности.
Что
нужно знать:
·
в некоторых задачах (на RLE-кодирование, см. далее) нужно знать, что такое бит и байт, что байт
равен 8 бит, что такое старший бит, как переводить числа из двоичной системы в
десятичную
·
в классических задачах (на символьные цепочки) каких-либо
особых знаний из курса информатики, кроме умения логически мыслить, не
требуется
Пример задания:
Строки (цепочки символов латинских букв)
создаются по следующему правилу. Первая строка состоит из одного символа –
латинской буквы «А». Каждая из последующих цепочек создается такими действиями:
в очередную строку сначала записывается буква, чей порядковый номер в алфавите
соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается
предыдущая строка. Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) CBAABAA
(4) DCBAABAACBAABAA
Латинский алфавит (для справки):
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в
восьмой строке со 126-го по 132-е место (считая слева направо).
Решение:
1)
используя приведенное правило, можно построить
следующие строки:
(5)
EDCBAABAACBAABAADCBAABAACBAABAA
(6)
FEDCBAABAACBAABAADCBAABAACBAABAAEDCBAABAACBAABAADCBAA
BAACBAABAA
...
2)
мы быстро убедимся, что следующие строки получаются
достаточно длинные, и легко запутаться, отсчитывая символы с номерами 126-132 в
восьмой строке
3)
попробуем найти закономерности, позволяющие
решить задачу без выписывания 8-ой строки;
4)
прежде всего, заметим, что длины первых строк 1,
3, 7, 15, … – это числа вида 2i-1, где i – номер строки;
таким образом, длина 7-ой строки – 127, а длина восьмой – 255 символов
5)
восьмая строка строится так: восьмая буква
латинского алфавита (H) и затем – два раза седьмая строка (сверху написаны
номера символов)
|
1
|
2
|
128
|
129
|
255
|
|
H
|
GFEDC…
|
...AABAA
|
GFEDC…
|
...AABAA
|
6)
символы 126-132 находятся на границе двух
цепочек, повторяющих 7-ую строку; заметим, что в соответствии с заданным алгоритмом
можно легко определить первые символы в 7-ой строке (GFEDC) и последние символы (AABAA)
7)
далее сразу находим, что интересующая нас часть
8-ой строки имеет вид
|
125
|
126
|
127
|
128
|
129
|
130
|
131
|
132
|
133
|
|
A
|
B
|
A
|
A
|
G
|
F
|
E
|
D
|
C
|
8)
таким образом, правильный ответ – BAAGFED.
|
Возможные ловушки и проблемы:
·
можно, конечно, попробовать выписать заданную
строку и выделить нужные символы, но этот подход очень трудоемкий и чреват
случайными ошибками
·
чаще всего заданная цепочка находится на
границе, где соединяются две части строки (например, в этом задании – на
границе двух последовательностей, совпадающих с 7-ой строкой)
·
в задачах этого типа часто встречается игра на
последовательностях вида
2k: 1, 2, 4, 8, 16, …
2k-1: 1, 3, 7, 15, 31, …
полезно помнить формулу, которая «сворачивает»
сумму степеней двойки:
1 + 2 + 4 + 8 + … + 2k = 2k+1
- 1
(для доказательства используйте тот факт, что двоичное число, состоящее
только из единиц, имеет вид 2n-1)
|
| 
