?

Log in

No account? Create an account
Previous Entry Share Next Entry
Задача
Слон
yashunsky
За несколько шагов она из практической стала интересной :) но, возможно, еще есть дыры в формулировке:
Есть стек с какими-то натуральными числами в случайном порядке. Как (можно ли) найти наименьшее недостающее число, используя O(1) памяти за O(N)?
(последнее, возможно, излишне: честно говоря, я не очень представляю, можно ли что-то осмысленное делать со стеком дольше чем O(N), если у нас O(1) памяти)
И если нет, то как можно ослабить условие, чтобы задача решалась? :)
O(N) памяти и O(N log N) шагов — это очевидная оценка сверху.

  • 1
Что значит "недостающее"?

Что можно сделать со стеком? Должен ли он в конце быть в исходном состоянии?

я пока думал над задачей придумал что может означать "недостающее" :)
мое предположение - "минимальное натуральное число, отсутствующее в стеке"

Признаться, вообще не понимаю, с какого конца подступиться. :(

ну да, это именно оно.

со стеком можно делать что угодно. Собственно, с константной памятью, я так понимаю, его невозможно восстановить, ведь вынуть точно надо будет всё.

А "недостающее", да, имелось в виду "минимальное натуральное число, отсутствующее в стеке"

Я так и подумал. Не понимаю, как это сделать.

ну как раз получить O(1) по памяти легко, если ослабить требования по сложности

... ослабить требования по сложности до O(n^2) кажется
можно ли быстрее?...

я пока и такой не получил :) тот вариант про который думал в начале оказался неверным

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

я шел по пути ужесточения )) изначально это вообще была задачка про auto-increment поле в БД ))

А зачем тебе там произвольный доступ? Он, вроде, в данной задаче от списка не отличается. Или ты его и имел в виду?

)))

Ну как бы да, отсортировать стек без произвольного доступа в константной памяти нельзя. Сортировка как таковая для задачи не нужна, но по сути все равно.

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

стек с произвольным доступом — это уже экзотика, хотя могу себе такое представить :)

да ладно, все равно стек это как правило либо массив либо список )

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

Дисклеймер: я не программист, только сейчас нагуглила, что такое О(1) и вообще не уверена, что мой комментарий в тему, но сказать что-нибудь хочется.

Если ячейка стека имеет ограничение по объему (пусть, например, она однобайтовая, может содержать числа от 1 до 256), то задача имеет как минимум одно решение, некрасивое, зато в лоб: берем 256 пронумерованных булевских переменных (в начале пусть в них стоит "ложь"), находим среди них ту, чей номер соответствует значению верхнего элемента стека, ставим туда "истина", выкидываем верхний элемент стека и берем следующий, и так пока стек не кончится. После этого проверяем подряд булевские переменные и выдаем в качестве ответа номер первой, в которой "ложь", если такой не нашлось, то ответ - 257.

Если у ячейки стека нет ограничения по объему, то при любом заранее данном объеме константной памяти можно загнать в первую же ячейку стека число, которое в константную память не влезет, и в этом случае, по-моему, со стеком нельзя сделать вообще ничего осмысленного.

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

Мысль на самом деле отличная, я ее тоже думал. Но тут ведь как... все зависит от размера элемента.
Если там байт, то еще ладно, а вот если хотя бы int16 (2 байта), то это уже 65536 значений или 8 килобайт памяти.
С другой стороны конечно под условие задачи подходит блестяще - O(1) памяти и O(N) сложность )


Edited at 2015-05-15 10:36 pm (UTC)

мне надоело редактировать два комментария в параллель, см ниже :)

Edited at 2015-05-15 11:08 pm (UTC)

Ну да, я тут как математик из анекдота: решение существует, про практичность не спрашивали :)

Анекдот есть почти в тему:
Сумасшедший дом для математиков. Один бегает и говорит другим "я тебя продифференцирую!" и они в ужасе убегает. Подбегает к очередному:
—Я тебя продифференцирую!
—Пофиг, я ex
—А я — d/dy!

тут не столько умолчание, сколько нечеткость вопроса. Я подумаю, как увязать максимальный размер числа с N, чтобы у задачи одна размерность осталась :)

Но да, под то условие, которое я написал, подходит :)

Например: Есть числа от 1 до N. из них взяли произвольные N-k и поместили в случайном порядке в стек. найти наименьшее не взятое при k>1 (чтобы не просто XOR был :) ) Тогда, соответсвенно, ограничение по памяти увеличиваем до O(ln N), а по операциям оставляем O(N). Ничего не упустил?

Кстати, в такой формулировке можно, наверное сказать, что N известно и просить найти хоть какое-то не взятое число.

Edited at 2015-05-15 11:07 pm (UTC)

  • 1