|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
28.10.2016, 17:00 | #1 |
Новичок
Джуниор
Регистрация: 28.10.2016
Сообщений: 2
|
Восстановление последовательности
Этот вопрос по алгоритмам а не конкретно по С++, но раздел алгоритмы я не нашел поэтому написал сюда.
1. Есть конечная последовательность натуральных чисел обладающая следующим свойством: (*) Любой суффикс этой последовательности лексикографически( только числа вместо букв) больше этой последовательности, например: a = {3, 6, 10, 3, 6, 11, 3, 6, 99}, какой суффикс ни возьми: 99 >a, {6, 99} > a, {3, 6, 99} > a, ... и т.д Потом мы берем и записываем все сдвиги этой последоваетльности т.е. {6,10,3,6,11,3,6,99,3}; {10,3,6,11,3,6,99,3,6}; ... и т.д Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности. Для а ,например: {99, 10, 11, 3, 3, 3, 6, 6, 6} и вот надо воостановить по ней исходную последовательность. 2. Усложнение задачи 1. дана конечная последовательность натуральных чисел и мы слева направо начинаем искать максимальные подпоследовательности обладающие свойством (*) т.е. например: a = {3,56,78, 5,6,4,2,5,7,8,9,2,4,1} -> {{3,56,78,5,6,4}, {2,5,7,8,9},{2,4},{1}} Затем как в (1) для каждой подпоследовательности записываем все сдвиги (для посл. длин n , будет n всевозможных сдвигов) Потом берем все последовательности и сортируем в лексикографичесокм порядке и берем их последние элементы Получаем новую последовательность, по ней надо восстановить исходную. Помогут любые дельные идеи, реализую уже я их сам. |
28.10.2016, 20:15 | #2 |
Новичок
Джуниор
Регистрация: 28.10.2016
Сообщений: 2
|
Первую задачу я придумал как решать, например:
a = {3,5,7,4,5,5} исходная последовательность (*) Отсортированные сдвиги (**): {3,5,7,4,5,5} {4,5,5,3,5,7} {5,3,5,7,4,5} {5,5,3,5,7,4} {5,7,4,5,5,3} {7,4,5,5,3,5} Последовательность по которой надо восстановить исходную {5,7,5,4,3,5} 1. {3,..., 5} -> {5, 3} (часть иходной последовательности) {4,...., 7} -> {7,4} {5,...., 5} - >{5, 5} {5, ..., 4} -> { 4,5} {5,..., 3} -> {3,5} {7, ..., 5} -> {5,7} Мы знаем что за 3 следует 5 (3 одна поэтому никаких проблем), за 4 следует 5 (тоже нет проблем), за 5 может идти 3,5,7 , но мы знаем что (**) отсортировано поэтому 3,5,7 сортируем и последовательновписываем после пятерок, с 7ой никактх проблемю Получаем: 2. {3, 5, ..., 5} - > {5,3,5} {4, 5, ...., 7} -> {7,4,5} {5, 3, ...., 5} - > {5,5,3} {5, 5, ...., 4} -> {4,5,5} {5, 7, ...., 3} -> {3,5,7} {7, 4, ...., 5} -> {5,7,4} Дальше проделываем тоже самое и получаем нужную последовательность с точность до поворота (этого достаточно) Но вот в усложненном варианте (2ой задаче) такой подход не дает нужный результат. Например исходная последовательность: {3,3,6,3,3} разобьется на {{3,3,6}, {3}, {3}} Затем после сдвигов и сортировок: {3} {3} {3,3,6} {3,6,3} {6,3,3} Получаем последовательность из последних элементов: {3,3,6,3,3} Получаем пары: {3, ... , 3} - {3, 3} ложная пара тройка зациклена на себе {3, ..., 3} - {3, 3} снова ложная {3, ..., 6} - {6,3} {3, ..., 3} - {3,3} {6, ...., 3} - {3, 6} {3, 3, ..., 3} - неверно {3, 3, ..., 3} - неверно {3, 3, ..., 6} {3, 6, ..., 3} {6,3, ..., 3} |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
с++ Вводится последовательность ненулевых чисел,0-конец последовательности, определить наибольшее число в последовательности | ЮськаЮськовна | Помощь студентам | 3 | 10.11.2015 15:20 |
Если число x встречается в последовательности, упорядочить по невозрастанию часть последовательности (Паскаль) | димон4ик_ | Помощь студентам | 1 | 17.10.2011 23:00 |
Определить:формат последовательности параметров & способ размещения последовательности переменных | DenSyntax | Помощь студентам | 0 | 22.06.2010 17:26 |
Определить k-ую цифру последовательности Фибоначчи и последовательности натуральных чисел. | Med | Помощь студентам | 1 | 20.03.2009 11:40 |
Восстановление | Elm0 | Компьютерное железо | 3 | 30.05.2007 07:42 |