Решаем задачи по теме "Анализ алгоритма построения последовательности"

Теория по теме

Задача 1

Цепочки символов (строки) создаются по следующему правилу: в начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на n-м шаге приписывается цифра n.). Ниже показаны первые строки, сформированные по описанному правилу (в скобках записан номер строки, начиная с 0).
(0)0
(1)001
(2)0010012
(3)001001200100123
Сколько раз встретится цифра 1 в последней строке?

Задача 2

В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку дважды записывается предыдущая строка, а в конец строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Ниже показаны первые строки, сформированные по описанному правилу (в скобках записан номер строки, начиная с 0).
(0) 0
(1) 001
(2) 0010012
(3) 001001200100123
Какая цифра стоит в последней строке на 1022-м месте?

Задача 3

Упаковка информации методом RLE-кодирования состоит в следующем. Упакованная последовательность содержит управляющие байты, за каждым управляющим байтом следует один или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий за управляющим байт данных при распаковке нужно повторить столько раз, сколько записано в оставшихся 7 битах управляющего байта. Если же старший бит управляющего байта равен 0, то надо взять несколько следующих байтов данных без изменения. Сколько именно – записано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10000111 говорит о том, что следующий за ним байт надо повторить 7 раз, а управляющий байт 00000100 – о том, что следующие за ним 4 байта надо взять без изменений.
После кодирования методом RLE получилась следующая последовательность байтов (первый байт – управляющий):
00000011 10101010 00000010 10101111 10001111 11111111.
Сколько байт будет содержать данная последовательность после распаковки? Впишите в бланк только число.

Задача 4

Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа, это цифра 1. Каждая из следующих цепочек создается так. Сначала записывается порядковый номер данной строки, далее дважды записывается вся цепочка цифр из предыдущей строки. Первые 4 строки, созданные по этому правилу, выглядят следующим образом:
1
211
3211211
432112113211211
Сколько раз в общей сложности встречается в 9-й строке цифра 1?