|
Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последовательность натуральных чисел от 1 до N (N заранее известно) в порядке частичного "возрастания". Это означает, что число Y не может первый раз встречаться в последовательности раньше числа X, если X < Y. Каждое число встречается ровно 2 раза. Повторяющиеся числа расположены не обязательно друг за другом. Например: (1, 2, 3, 4, 1, 2, 3, 4) или (1, 2, 3, 1, 2, 3, 4, 4) или (1, 2, 3, 4, 4, 3, 2, 1) или (1, 1, 2, 2, 3, 4, 3, 4). Разрешены операции сокращения последовательности: a) удаление двух одинаковых чисел, идущих друг за другом; b) замена двух чисел, расположенных в порядке (..., x, y, ..., у, x, ...) на одно из этих чисел, например: (..., x, y, ..., у, x, ...) -> (..., x, ..., x, ...). Определить сокращается ли последовательность до одной из трех: (), т.е. до пустой последовательности; (x, y, x, y); (x, y, z, x, y, z). Об алгоритмах за один проход см. -- https://habr.com/ru/post/243819/ задан 28 Июн '21 16:03 
vadimm
показано 5 из 15
показать еще 10
|
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
28 Июн '21 16:03
показан
362 раза
обновлен
29 Июн '21 23:16
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Каждое ваше число - это скобки, открывающая и закрывающая, причем скобки разного типа не коммутируют. Чтобы разобраться со скобочной записью за один проход, сделайте стек. Если на входе то же число, что на верху стека, оно убирается из стека. Если на входе большее число, чем на верху стека - оно кладется в стек. В конце вам нужно всего лишь сосчитать длину оставшегося стека.
Я не знаком с языком скобок. Не могли бы поподробнее прокомментировать ваш ответ? Я представил это так. Последовательность (1, 2, 2, 1, 3, 3) -- это в скобках -- ([, [[, ]], ], [[[, ]]]).
@vadimm, нет, это разные типы скобок. Круглые, фигурные, квадратные, уголковые. Но, в общем, можно и без слова "скобки" обойтись. Важно понимать, как работать со стеком.
С вашей записью тоже можно работать, но запятые же всё портят. А убирать нельзя: 1 2 1 2 не то же самое, что 1 2 2 1.
Тогда какие скобки вы имели ввиду? Причем тут запятые? Можно и без запятых. Строка. Перевод последовательности в строку не будем брать в счет. Пусть на входе содержится какая-нибудь строка из чисел: '1212...'. Вы написали -- "это скобки, открывающая и закрывающая, причем скобки разного типа не коммутируют". Можете привести пример, как записать строку '12312344' через скобки?
@vadimm ( [ { ) ] } < >
Здесь в условии вроде бы подразумевается, но не говорится явно, что каждое число появляется дважды.
@falcao, да. Спасибо. Я это почему-то упустил. Хотя и имел в виду. Исправил условие задачи.
@vadimm: "иметь в виду" всегда пишется раздельно. В отличие от фраз типа "ввиду отсутствия ресурсов, мы отменили свои планы".
@falcao, исправил. Спасибо. А может еще что-то сказать по алгоритму?
@vadimm: над алгоритмом я не думал. Я так понимаю, выше @knop высказался, а он в такого рода вопросах разбирается.
@knop, правильно я понимаю, что ваша идея со скобками и стеком должна давать однопроходный алгоритм или вы не уверены?
@vadimm да не "должна", а даёт.
@knop, не могли бы объяснить, зачем нужны скобки для стека? Почему нельзя брать просто числа?
@vadimm: разницы тут нет -- просто мыслить что-то на языке скобок иногда бывает удобнее. А при реализации стека, разные типы скобок по сути и становятся числами.