ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

Даны две последовательности x[1]...x[n] и  y[1]...y[k] целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка n . k.

   Решение

Задачи

Страница: 1 [Всего задач: 5]      



Задача 76268  (#1.3.1)

Тема:   [ Индуктивные функции ]
Сложность: 2

Указать индуктивные расширения для следующих функций: 
(а) среднее арифметическое последовательности вещественных чисел;
(б) число элементов последовательности целых чисел, равных её максимальному элементу; 
(в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);
(г) максимальное число идущих подряд одинаковых элементов;
(д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;
(е) число групп из единиц, разделённых нулями (в последовательности нулей и единиц).
Прислать комментарий     Решение


Задача 76269  (#1.3.2)

Тема:   [ Индуктивные функции ]
Сложность: 2

(Сообщил Д. В.Варсанофьев) Даны две последовательности целых чисел x[1]...x[n] и  y[1]...y[k]. Выяснить, является ли вторая последовательность подпоследовательностью первой, то есть можно ли из первой вычеркнуть некоторые члены так, чтобы осталась вторая. Число действий порядка n + k.
Прислать комментарий     Решение


Задача 76270  (#1.3.3)

Тема:   [ Динамическое программирование: классические задачи ]
Сложность: 2+

Даны две последовательности x[1]...x[n] и  y[1]...y[k] целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка n . k.
Прислать комментарий     Решение


Задача 76271  (#1.3.4)

Тема:   [ Индуктивные функции ]
Сложность: 3

(из книги Д. Гриса) Дана последовательность целых чисел x[1],...,x[n]. Найти максимальную длину её возрастающей подпоследовательности (число действий порядка n log n).
Прислать комментарий     Решение


Задача 76272  (#1.3.5)

Тема:   [ Индуктивные функции ]
Сложность: 3

Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность?
Прислать комментарий     Решение


Страница: 1 [Всего задач: 5]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .