А1042

Условие:

В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны.

Тесты:

Число элементов в заданной последовательности Заданная последовательность Найденная подпоследовательность
20 1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48 3 6 9 12 15 18
20 1 9 17 25 90 91 92 13 18 23 28 100 75 50 45 44 43 42 41 40 1 9 17 25
20 155 100 80 83 86 89 -60 -40 -20 0 20 40 60 33 33 33 0 0 0 0 -60 -40 -20 0 20 40 60

Код:

План

План программы:

Задача нахождения искомой подпоследовательности решается путем выделения всех возможных возрастающих последовательностей, которые удастся обнаружить во входной последовательности. Для нахождения какой либо возрастающей последовательности необходимо убедиться, что все числа монотонно возрастают с одинаковым приращением. По — этому алгоритм решения задачи состоит из следующих шагов:

  1. Находим все возможные приращения, как все возможные разности между входными значениями
  2. Выполняем цикл по всем входным значениям, для каждого входного значения пытаемся найти остальные значения, имеющие монотонно возрастающее приращение. Это выполняется для каждого найденного приращения. Для этого организуется вложенный цикл по всем приращениям. Он состоит из двух подциклов – движение влево от начального значения – ищем предыдущие члены последовательности с меньшим приращением, и движение вправо – ищем следующие значения последовательности с большим приращением
  3. Найденные последовательности сохраняем для последующего выбора самой длинной. Последовательности короче трёх элементов, а также с отрицательным приращением(т.е. убывающие) – игнорируем
  4. Выполняем слияние найденных последовательностей, если они покрывают друг – друга
  5. Находим последовательность наибольшей длины

Программа реализована с использованием шаблонных классов стандартной библиотеки vector и map. Vector используется для хранения всех используемых последовательностей, включая разности. Map используется, как временный объект для сортировки и слияния приращений, которые в ходе поиска встречаются с часто повторяющимися значениями.

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

Входные данные

Программа позволяет работать не только с фиксированными 20-ю числами. Длинна входной последовательности задаётся. Ввод содржит первым элементом длину последовательности, а затем следуют числа самой последовательности.

Ссылка на ideone.com :  http://ideone.com/kf13Zv

Related Images:

One thought on “А1042

  1. Ну, во-первых неправильно работает.
    В первом тесте можно к Вашему результату добавить 48. Во втором — например, 90 91 92 100.

    А во-вторых, мы изучали динамическое программирование на лекции рассматривали задачу нахождения длиннейшей общей подпоследовательности двух строк. Потом говорили о задаче нахождения длиннейшей алфавитной подпоследовательности символов строки. Остается один шаг до Вашей задачи.

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