ГлавнаяИнформатикаКак решатьЦепочки символов (строки) создаются по следующему правилу

Цепочки символов (строки) создаются по следующему правилу

2016-06-13 16:00:16

Формулировка задания: Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из ... Каждая из последующих цепочек создается такими действиями ... Вот первые 4 строки, созданные по этому правилу. Какой символ стоит в K строке на N-м месте (считая слева направо)?

Задание входит в ЕГЭ по информатике для 11 класса под номером 6 (Анализ и построение алгоритмов для исполнителей).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа – цифры «1». Каждая из последующих цепочек создается такими действиями: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число – номер строки по порядку (на i-м шаге дописывается число «i»).

Вот первые 4 строки, созданные по этому правилу:
(1) 1
(2) 112
(3) 1121123
(4)
112112311211234

Какая цифра стоит в седьмой строке на 120-м месте (считая слева направо)?

Решение:

Вычислим количество символов в 7 цепочке, зная что в каждой следующей строке символов больше на 2k + 1, где k – количество символов в предыдущей строке.

1 строка: 1

2 строка: 2 ⋅ 1 + 1 = 3

3 строка: 2 ⋅ 3 + 1 = 7

4 строка: 2 ⋅ 7 + 1 = 15

5 строка: 2 ⋅ 15 + 1 = 31

6 строка: 2 ⋅ 31 + 1 = 63

7 строка: 2 ⋅ 63 + 1 = 127

Нам нужно узнать, какая цифра стоит на 120 месте в 7 строке, в которой 127 символов. Для этого воспользуемся известными правилами.

127 символом в 7 строке является цифра 7. С 64 по 126 символы – это повтор строки 6. Значит, 126-я цифра равна номеру 6 строки, то есть 6. 125-я цифра – номеру 5 строки, то есть 5. 124-я цифра – номеру 4 строки, то есть 4. 123-я цифра – номеру 3 строки, то есть 3. 122-я цифра – номеру 2 строки, то есть 2. 121-я цифра – номеру 1 строки, то есть 1.

Чтобы вычислить 120-ю цифру, обратим внимание на 2 строку, в ней дублируется цифра 1. Это же наблюдается во всех остальных строках. Значит, на 120 месте стоит цифра 1.

Ответ: 1

До экзаменов еще есть время!

Наверх