Форум » Обработка числовых последовательностей » №5311 (27.115) ошибки в решениях и примере » Ответить
№5311 (27.115) ошибки в решениях и примере
beep: Здравствуйте! Во-первых, в примере в ответе представлена цепочка, у которой левая и правая стороны неправильно посчитаны: Данные: [pre2] 7 15 12 5 1 4 15 5 [/pre2] Ответ: [quote]В этой последовательности числа можно переставить следующим образом: {4, 5, 15, 12, 15, 5, 1}, при этом L = 4 (подпоследовательность {4, 5, 12, 15}) и M = 4 (подпоследовательность {1, 5, 12, 15}), так что R = min(4 ,4) = 4. Ответ: 4.[/quote] Только нельзя с двух сторон построить такую цепочку. Тут может быть несколько вариантов ошибки, но при заданных данных ответ 3, а не 4. Во-вторых, все предложенные алгоритмы не учитывают ряд случаев. Перестановки подразумевают, что используются все члены множества. При строгом возрастании подряд не могут идти равные числа, их приходится раскидывать на левую и правую стороны. Если одинаковых чисел больше двух, то "лишние числа" переносятся в середину, чтобы они не мешали продолжению цепочки. Такие числа будем называть "перегородкой". Теперь у нас есть 2 варианта событий: когда в левой и правой сторонах одинаковое количество чисел, и когда в одной из сторон чисел на 1 больше. 1) Если у нас стороны одинаковой длины, то наличие перегородки ни на что не влияет и существует единственный ответ, это длина любой стороны. 2) Если у нас стороны разной длины, то есть 2 варианта: 2.1) Когда на концах каждой стороны стоит одинаковое число (наличие перегородки ни на что не влияет): Пример данных (без перегородки) [pre2] 5 1 2 3 3 2 [/pre2] Правильный ответ 2, но все алгоритмы выдают 3. Пример данных (с перегородкой) [pre2] 6 1 2 3 2 3 2 [/pre2] Правильный ответ 2, но все алгоритмы выдают 3. 2.2) Когда на каждом конце разные числа (стороны разной длины). И тут есть 2 варианта: 2.2.1) Без перегородки [pre2] 5 1 2 3 2 1 [/pre2] Алгоритмы работают правильно. 2.2.2) С перегородкой [pre2] 6 1 2 3 2 2 1 [/pre2] Правильный ответ 2, но все алгоритмы выдают 3.
Ответов - 2
MDF: beep пишет: Только нельзя с двух сторон построить такую цепочку Вы не поясняете, почему нельзя. Пример в задании показывает, что можно. beep пишет: Тут может быть несколько вариантов ошибки, но при заданных данных ответ 3 И не поясняете, почему для приведенной в примере последовательности ответ 3, а не 4. beep пишет: При строгом возрастании подряд не могут идти равные числа В приведенных в примере подпоследовательностях тоже нет одинаковых чисел. beep пишет: Перестановки подразумевают, что используются все члены множества. В приведенной в примере перестановке исходной последовательности тоже используются все ее члены. чтобы они не мешали продолжению цепочки. В своих рассуждениях Вы используете термин "цепочка" вместо термина "подпоследовательность", который приведен в задании. Если рассматривать задание, как оно есть, ошибок не будет.
beep: MDF пишет: В своих рассуждениях Вы используете термин "цепочка" вместо термина "подпоследовательность", который приведен в задании. Если рассматривать задание, как оно есть, ошибок не будет. Здравствуйте! Действительно, я на автомате воспринял подпоследовательность как подстроку. Спасибо!
полная версия страницы