Коля работает на складе. Каждое утро склад пустой, потом в течение дня туда постоянно то приносят, то уносят разные вещи, причем у каждой вещи есть свой уникальный 32битный идентификатор. К вечеру на складе всегда остается не более 4 вещей.

Коля хочет написать программу, которая бы следила за приходящими и уходящими вещами и в конце дня говорила бы ему идентификаторы оставшихся вещей. Как ему реализовать структуру данных, которая могла бы осуществить это, но при этом занимала бы не более четырех 32битных регистров?

Максимальное количество вещей, которое может быть на складе днем не ограничено.

GD Star Rating
loading...

14 Responses to Как реализовать структуру данных?

  1. LeBig:

    спешу заметить, что если у каждой вещи уникальный 32 битный идентификатор, то количество вещей ограничено 32 битами, а ни как не бесконечно много)

  2. Peels:

    Ну да, но количество бит тут непринципиально.

  3. Peels:

    Если бы надо было узнать про одну остающуюся вещь, то да. А как обобщить на 4–5 и более вещей?

  4. SpMonkey:

    нам бы тогда хватило одного регистра.. а тут, если поразмыслить и ХОЯить более хитрожопо, можно учесть все четыре 🙂 просто не знаю писать сюда мысли или опять осудят за досрочный ответ и облом кафов 🙂

  5. Peels:

    Ну если ты уверен что решил правильно, то лучше не пиши (я сам не особо думал про подход с xor–ом, ибо задача возникла в другом контексте, а так хоть подумаю). А если хочешь обсудить, можно обсудить.

    В любом случае помима xor есть еще одно (очевидно чем–то схожее, но другое) решение.

  6. SpMonkey:

    Нет, я не уверен, ибо это просто мысли которые сходу пришли в голову… просто подумал про кодирование информации –> код хемминга –> разбитие на группы
    До сих пор кажется, что здесь применимо… щас освобожусь подумаю подробнее…

  7. LeBig:

    Где ответ? сдаёмся уже) Меня переклинило — с двух часов дня до 4ночи я решал эту задачу. Написал несколько сот строк кода. Ничего не выходит.
    Или посте.

  8. Peels:

    Ключевое слово — корни многочлена.

  9. Rafol:

    Есть решение для (7*32+1)–битного регистра, над 4*32–битным надо еще подумать.

    Можно считать, что идентификаторы — элементы конечного поля GF(2^32). Каждому идентификатору w сопоставим вектор D(w) = (1, w, w^2,…, w^7). D(w) является вектором в (7*32+1)–мерном пространстве над GF(2) и следовательно может храниться в (7*32+1)–битном регистре R.

    В начале смены запишем в регистр R сумму значений функции D() от идентификаторов имеющихся в начале предметов. Если в начальный момент было 4 предмета с идентификаторами s1, s2, s3, s4, пишем в регистр D(s1) + D(s2) + D(s3) + D(s4).

    Если на склад поступил или если со склада выбыл предмет с идентификатором *, то прибавляем к текущему значению регистра D(*). Поскольку для всякого х D(*) + D(*) = 0, в конце смены в регистре будет содержаться сумма вида F = D(f1) + D(f2) + D(f3) + D(f4), где fi — идентификаторы оставшихся в конце смены предметов.

    По значению F однозначно определяются все D(fi), а значит и fi. Действительно, если бы нашлись какие–нибудь другие идентификаторы g1, g2, g3, g4 такие, что F = D(g1) + D(g2) + D(g3) + D(g4), то мы бы имели D(f1) + D(f2) + D(f3) + D(f4) + D(g1) + D(g2) + D(g3) + D(g4) = 0, что невозможно, поскольку все 8 слагаемых представляют собой 8 линейно независимых строк матрицы Вандермонда (по определению функции D()). Случаи, когда количество fi или gi меньше 4 аналогичны.

    Избыточность этой конструкции в том, что нам достаточно линейной независимости над GF(2), в то время, как имеется независимость над GF(2^32).

  10. Peels:

    Ну и еще она не очень хорошо работает если в конце дня на складе два предмета с одним идентификатором, что в принципе не запрещено (а мой ответ выше леКоростелю про то что не может быть бесконечно много вещей поэтому неверен).

    Вообще решение по идее таково, что в любой момент мы просто храним весь список вещей на складе (w1, w2, …, wn) как многочлен вида (*–w1)(*–w2)…(*–wn) над G(2^32). Только мы не храним весь многочлен, а всего лишь его остаток от деления на какой–нибудь неприводимый многочлен степени 3, который как раз помещается в 4 слова. Добавление и удаление элементов соответствует умножению или делению на член вида (*–w), которое можно совершать по модулю, ну а к вечеру мы по остатку и знанию что ведущий коэффициент равен 1 можем восстановить весь многочлен и разложить его обратно на множители.

    Я могу ошибаться или хотя бы заблуждаться в простоте некоторых шагов, ибо на самом деле очень глубоко эту задачку не продумывал и с многочленами по модулю очень давно дел не имел.

  11. NoDoctor:

    B–tree — ваш выбор

  12. Peels:

    Это ты к чему?

  13. NoDoctor:

    это я к тому что я задачи поставленные читать не умею. Сорри камрад, ступил.

Добавить комментарий