2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Обьединение множеств
Сообщение15.03.2010, 22:32 
Задача с беларусской областной олимпиады 2010.

Во входном файле имеются два множества, например:
Код:
[1, 3, 5..6]
[2, 6..8]


или

Код:
[]
[1000000]


Нужно их обьединить в одно, чтобы в выходном файле получилось:

в 1-ом случае:
Код:
[1..3, 5..8]


во втором:
Код:
[1000000]


может быть, у кого-то есть идеи, как это реализовать)
P.S. Длина каждой входной строки не превосходит 10000 символов, а каждый элемент множества не превосходит 10E9. Соответственно в выходном файле строка будет может превышать 10000 символов.

-- Пн мар 15, 2010 22:34:06 --

><>Sunny<><

 
 
 
 Re: Обьединение множеств
Сообщение15.03.2010, 22:50 
Это не по математике задача.
А решается она сортировкой всех концов отрезков.

 
 
 
 Re: Обьединение множеств
Сообщение16.03.2010, 23:24 
вообще, это как раз таки математическая задача.(если я не прав, поправьте).

Скорее всего автор имел ввиду задачу об объединении неупорядоченных целочисленных множеств(т.е. вида $\{0, 23, 1, 99, 3, 4, 2\}$). Или , по-другому, неотсортированных массивов.

Задачу можно свести к построению минимального остовного леса. (алгоритмы Прима и Краскала).

Как вариант предлагаю рассмотреть граф, заданный списком рёбер. Рёбра получим следующим образом: если заданы два множества $\{a_1, a_2, ... a_n\}$ и $\{b_1, b_2, ..., b_k\}, k \ge n$, то рёбрами будут $\{(a_1,b_1),...,(a_n,b_n),(b_{n+1},b_{n+1}),...,(b_k,b_k))\}$

теперь каждому ребру приписываем вес 1 и применяем любой из алгоритмов построения минимального остовного леса.

можно при этом последние $k-n$ рёбер сразу включить в остовный лес и не возиться с ними

P.S.: Какая-то очень похожая задача встречается при изучении бинарных деревьев поиска. Наверное, объединение деревьев. В общем, что-то там про графы

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group