Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.04.2010, 01:36
Новичок

Отправить личное сообщение для Fredo Посмотреть профиль Найти все сообщения от Fredo
 
Регистрация: 28.04.2010
Сообщений: 4

Задача о сортировке пузырьком
Помогите плиз со следующей задачкой:

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

Буду премного благодарен )))
  #2  
Старый 28.04.2010, 02:21
гость

 
Сообщений: n/a

источник задачи в студию!

и там же вроде бы все однозначно определется и восстанавливается.
  #3  
Старый 28.04.2010, 02:28
Новичок

Отправить личное сообщение для Fredo Посмотреть профиль Найти все сообщения от Fredo
 
Регистрация: 28.04.2010
Сообщений: 4

Мне моего науча привести ? )))

Например порядоченная последовательность (первая строка последовательность, вторая счетчики)

1 2 3 4 5 6 7
2 2 2 2 2 2 2

Востанавливается в 2 последовательности

3 2 1 6 7 4 5
и

3 4 1 2 7 6 5
  #4  
Старый 29.04.2010, 08:14
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Предположение такое:
Сформировать двудольный граф, одна доля которого содержит конечные положения, вторая начальные, а ребра соответствуют возможным переходам. Большинство чисел могут прийти на свое место из начальных позиций, удаленных влево и вправо не более, чем на счетчик (с шагом 2), но, скажем, единица направо двигаться не может, так что для нее только одно направление остается, и другие ограничения надо аккуратно рассмотреть.
Для полученного графа ищутся все совершенные паросочетания (в данном случае они же и реберные покрытия).
  #5  
Старый 29.04.2010, 22:02
Новичок

Отправить личное сообщение для Fredo Посмотреть профиль Найти все сообщения от Fredo
 
Регистрация: 28.04.2010
Сообщений: 4

Спасибо ) Уже сам с помощью графа начал решать до чего то докопался вроде )
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
вопрос по сортировке Wind Of Change Сортировка и поиск 3 18.05.2008 16:41