Шешімі: Символ в рекурсивной строке
Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа — цифры «1». Каждая из последующих цепочек создается так: в очередную строку дважды записывается цепочка цифр из предыдущей строки (одна за другой, подряд), а в конец приписывается еще одно число — номер строки по порядку (на $i$-м шаге дописывается число «$i$»). Вот первые 4 строки, созданные по этому правилу: (1) 1; (2) 112; (3) 1121123; (4) 112112311211234. Какая цифра стоит в седьмой строке на 120-м месте, считая слева направо?
Шешімін қадамдап көрсету
7 қадамОбозначим длину строки с номером $n$ через $L_n$. Каждая строка, кроме первой, содержит две копии предыдущей строки и одну цифру номера строки.
$$L_1=1,\quad L_n=2L_{n-1}+1$$Получаем длины строк:
$$L_1=1,\ L_2=3,\ L_3=7,\ L_4=15,\ L_5=31,\ L_6=63,\ L_7=127$$В седьмой строке позиция 120 находится во второй копии шестой строки: $120-63=57$.
В шестой строке позиция 57 находится во второй копии пятой строки: $57-31=26$.
В пятой строке позиция 26 находится во второй копии четвёртой строки: $26-15=11$.
В четвёртой строке позиция 11 находится во второй копии третьей строки: $11-7=4$.
В третьей строке позиция 4 находится во второй копии второй строки: $4-3=1$. Первый символ второй строки равен $1$.
Где здесь ошибаются
Қате учитывать длину приписываемого нөмір строки.
Забывать вычитать длину первой копии предыдущей строки.
Продолжать переход к предыдущей строке после попадания в приписываемую цифру.