Задача 6.
Последовательность 011212201220200112... строится так: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, т.е.
0 -> 01 -> 0112 -> 01121220 ->...
Составить алгоритм, который по введенному N, (0<=N<=3000000000) определяет, какое число стоит на N-ом месте в последовательности.
|
Решение задачи 6.
Пусть a(k) - k-ый член последовательности.
Рассмотрим последовательность, формируемую по следующему правилу:
a(0)=0;
ряд
a(0)...a(2k-1)
получаем приписыванием к этой последовательности справа этой же последовательности, но при этом каждый член приписываемой части увеличивается на единицу. Получаем
0->01->0112->01121223->...
Докажем, что a(k) есть сумма единиц в двоичном представлении числа k.
Доказательство проведем по индукции. Для a(0)=0 это справедливо. Пусть предположение справедливо для всех a(i),
0<=i<=2(k-1)-1 (т.е. для всех чисел i, состоящих из не более чем k-1-го двоичных разрядов). Тогда в двоичном разложении числа l, 2(k-1)<=l<2k, в k-ом разряде появляется добавочная единица, и поэтому
a(l)=1+a(l-2(k-1))),
ч.т.д.
Возьмем a(i) mod 3, и получим число, стоящее на i-ом месте в последовательности, описанной в условии задачи.
Для того, чтобы найти a(i), необходимо, по доказанному, сосчитать количество единиц в двоичной записи числа i - см. задачу 5.
|
