4 сент. 2012 г.

Задачка: <L| и |R>

Заданы два оператора:
L : L(a,b) => ( 2 * a - b , b )
R : (a,b)R => ( a, 2 * b - a )
и начальная точка (a, b) = (0, 1).

Существует последовательность операторов L и R, такая, что в результате либо a = N, либо b = N.

Например:
Число 21 может быть получено кратчайшей последовательностью L L R L R:

  (a, b):   L(a, b) | (a, b)R

  (0, 1):   (-1, 1) | (0, 2)
 (-1, 1):   (-3, 1) | (-1, 3)
 (-3, 1):   (-7, 1) | (-3, 5)
 (-3, 5):  (-11, 5) | (-3, 13)
(-11, 5):  (-27, 5) | (-11, 21)


Какова минимальная длина последовательности с помощью которой можно получить N ?

Замечание №1: число N может лежать в диапозоне -231 .. 231-1.
Замечание №2: сложность O(log(N)).
Замечание №3: досупная память O(1).


внимание! комментарии содержат ответ.

8 комментариев:

Анонимный комментирует...

ad-hoc-solution

Vladimir Dolzhenko комментирует...

@Анонимный

честно сказать давно уже не брал шашку в руки с clojure, выглядит красиво, но что-то не пойму до конца ход мысли

ps. да и числа могут быть таки отрицательными.

Vladimir Dolzhenko комментирует...

@Анонимный

да и с таким заходом вообще-то не стыдно и подписаться)

Анонимный комментирует...

ad-hoc-solution-v2
Идея: c помощью любой последовательности операторов длины в точности n можно получить все числа [-2^n+1 2^n].

Анонимный комментирует...

ad-hoc-v2a-a-little-bit-smaller

Vladimir Dolzhenko комментирует...

@Анонимный

нет, всё конечно хорошо, только вот ... почему именно так

и как бы идея, что c помощью любой последовательности операторов длины в точности n можно получить все числа используя эти операторы далеко не очевидна

Анонимный комментирует...


Любая последовательность операторов длины в точности n позволяет
получить все числа [-2^n+1 2^n]

Индукция по n

Будем доказывать более сильное утв.
А именно все пары (x, y) имеют след структуру
если x > 0 то y = x - 2^k соотв. x [0 .. 2^n] (a)

База индукции:
n=1 (0, 1) верно

Шаг индукции:
Пусть для n <= k утв. верно
Рассмотрим пары для шага k+1
Для каждого числа x > 0 x <= 2^(k+1) необходимо показать, что есть
пара полученная не пред шаге, и применение одного из двух операторов
позволит получить пару с компонентом равным x (те сделав k+1 шаг) и
условием на связь x и y (a)

случай а)
Если x > 0 and x <= 2^k (те x мало) то, по предположению индукции есть пара с соотв. x
и можно применить один из операторов сохраняющий соотв. компонент.
Остается проверить, связь (a)

Без огр. общности x - первый компонент (иначе аналогично с заменой операторов)
R(x,y) = (x,2y-x)
x1 = x
y1 = 2y-x

y1 = 2y-x = 2(x-2^k) - x = 2x - 2^(k+1) - x = x - 2^(k+1)
утв. выполнено

случай б)
x > 2^k но тогда y = x - 2^k т.е. в данном случае y подпадает под предположение индукции.
и проводя абсолютно аналогичные расссуждения получим искомое.

Прошу прощения, слегка сумбурно выразился, но смысл вроде в этом есть.

Анонимный комментирует...

Идея примерно такая же.
I Докажем: для любого x>=2 cуществует посл-ть операторов {R,...L,..} такая, что второй элемент столбца R*...*(0,1)T равен x. При чем количество элементов последовательности соответствует числу знаков в двоичной записи числа x-1, где операторы L стоят на месте нулей , а R на месте единиц. Так, 21-1=10101 -1=10100. Значит число 21 - это второй элемент столбца RxLxRxLxLx(0 1)T. Доказательство по индукции.
1)2:2-1=1 - оператор R
3:3-1=10 - оператор RL ,
4:4-1=11 - RR. Т.о, для чисел x , для которых x-1 в двоичной записи имеет менее 3-х знаков доказано.
2)Предположим, что утверждение доказано для всех чисел, в двоичной записи которых n знаков.
A - произведение операторов длины n
A*(0,1)T ->x
Тогда
A*R = [(a11 b12)(-x+1 x)] *[(1 0)(-1 2)]=[(c11 c12)(-2*x+1 2*x)] (1)
A*R*(0,1)T -> 2*x - эквивалентно дописыванию 1 справа к двоичной записи x-1
A*L= [(a11 b12)(-x+1 x)]*[(2 -1)(0 1)]=[(d11 d12)(-2*x+2 2*x-1)] (2)
A*L*(0,1)T -> 2*x-1 - дописали 0 к двоичной записи x-1
Т.о., можем получить любую двоичную последовательность длины n+1.
(То, что последняя строка матрицы A имеет вид (-x+1 x) можно показать по индукции, но это видно также из (1) и (2): умножение на R и L не меняет этого соотношения)
II Аналогично для x<0. Произведение операторов начинается с L. Тогда для любого числа x<0 существует последовательность операторов {L,...R,..}такая что первый элемент столбца Rx...(0,1)T равен x. Количество элементов последовательности соответствует числу знаков в двоичной записи числа abs(x), где операторы R стоят на месте нулей , а L на месте единиц.