0
1

Как решить данную задачу за один проход или не более чем за 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

изменен 28 Июн '21 20:09

3

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

(28 Июн '21 16:46) knop

Я не знаком с языком скобок. Не могли бы поподробнее прокомментировать ваш ответ? Я представил это так. Последовательность (1, 2, 2, 1, 3, 3) -- это в скобках -- ([, [[, ]], ], [[[, ]]]).

(28 Июн '21 17:18) vadimm
1

@vadimm, нет, это разные типы скобок. Круглые, фигурные, квадратные, уголковые. Но, в общем, можно и без слова "скобки" обойтись. Важно понимать, как работать со стеком.

(28 Июн '21 17:52) knop

С вашей записью тоже можно работать, но запятые же всё портят. А убирать нельзя: 1 2 1 2 не то же самое, что 1 2 2 1.

(28 Июн '21 17:54) knop

Тогда какие скобки вы имели ввиду? Причем тут запятые? Можно и без запятых. Строка. Перевод последовательности в строку не будем брать в счет. Пусть на входе содержится какая-нибудь строка из чисел: '1212...'. Вы написали -- "это скобки, открывающая и закрывающая, причем скобки разного типа не коммутируют". Можете привести пример, как записать строку '12312344' через скобки?

(28 Июн '21 18:23) vadimm

@vadimm ( [ { ) ] } < >

(28 Июн '21 19:11) knop
4

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

(28 Июн '21 19:50) falcao

@falcao, да. Спасибо. Я это почему-то упустил. Хотя и имел в виду. Исправил условие задачи.

(28 Июн '21 20:11) vadimm
3

@vadimm: "иметь в виду" всегда пишется раздельно. В отличие от фраз типа "ввиду отсутствия ресурсов, мы отменили свои планы".

(28 Июн '21 20:32) falcao

@falcao, исправил. Спасибо. А может еще что-то сказать по алгоритму?

(28 Июн '21 21:01) vadimm

@vadimm: над алгоритмом я не думал. Я так понимаю, выше @knop высказался, а он в такого рода вопросах разбирается.

(28 Июн '21 21:51) falcao

@knop, правильно я понимаю, что ваша идея со скобками и стеком должна давать однопроходный алгоритм или вы не уверены?

(28 Июн '21 21:56) vadimm

@vadimm да не "должна", а даёт.

(29 Июн '21 2:57) knop

@knop, не могли бы объяснить, зачем нужны скобки для стека? Почему нельзя брать просто числа?

(29 Июн '21 22:52) vadimm

@vadimm: разницы тут нет -- просто мыслить что-то на языке скобок иногда бывает удобнее. А при реализации стека, разные типы скобок по сути и становятся числами.

(29 Июн '21 23:16) falcao
показано 5 из 15 показать еще 10
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×281
×197
×80

задан
28 Июн '21 16:03

показан
189 раз

обновлен
29 Июн '21 23:16

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru