▼

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 комментариев:

  1. Анонимный05 сентября, 2012 13:49

    ad-hoc-solution

    ОтветитьУдалить
  2. Vladimir Dolzhenko05 сентября, 2012 13:57

    @Анонимный

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

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

    ОтветитьУдалить
  3. Vladimir Dolzhenko05 сентября, 2012 13:57

    @Анонимный

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

    ОтветитьУдалить
  4. Анонимный05 сентября, 2012 14:35

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

    ОтветитьУдалить
  5. Анонимный05 сентября, 2012 15:05

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

    ОтветитьУдалить
  6. Vladimir Dolzhenko05 сентября, 2012 15:47

    @Анонимный

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

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

    ОтветитьУдалить
  7. Анонимный05 сентября, 2012 16:46


    Любая последовательность операторов длины в точности 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 подпадает под предположение индукции.
    и проводя абсолютно аналогичные расссуждения получим искомое.

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

    ОтветитьУдалить
  8. Анонимный11 сентября, 2012 02:05

    Идея примерно такая же.
    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 на месте единиц.

    ОтветитьУдалить