Предлагаю завести тему о компьютерных алгоритмах
Для начала такая простая практическая задача. Надо написать функцию, которая меняет местами строчки в текстовом редакторе. В редакторе, текст представлен вектором строчек. Например, вот текст из пяти строчек.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
Пользователь хочет перебросить последние две строки в начало, чтобы было
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
Как решить эту задачу в общем случае, и перебросить последние m елементов вектора в начало? Текст может быть огромным и поэтому просто завести вторую копию текста не разрешается.
Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
А возможно скажем, другое стандартное представление:
указатель на 1-ую строку
строка:
указатель на следующую строку текст строки
Тогда в начале ставим указатель на ту строку, которую хотим 1-ой( т е 4-ую), в начале 5-ой ставим адрес 1-ой, а, а в начале 3-ей - признак конца.
Короче, мораль: решение зависит от структуры представления данных
Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
Ну если вектор очень длинный то и на адреса места не хватит. Будем считать, что это требование к алгоритму избежать копирование вектора.
Grigoriy написал(а):
Короче, мораль: решение зависит от структуры представления данных
Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист (по русски не знаю название термина) строчек. Это тоже ограничение, но можно конечно реализовать и Ваш вариант.
Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист
Linked list это совсем не вектор.
Вопрос же Григория касался того, позволяете ли формат ограничиться перестановкой адресов, или нужно копировать еще и данные.
Впрочем это не так важно.
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться
Да операция swap если надо имеется. Грубо говоря небольшое количество строк скопировать можно (например одну), нельзя копировать весь вектор или большую его часть.
Ну на первый заход...
В общем случае двигаются все записи. так что общие затраты как минимум О(N) где N - общее число записей.
1. Берем первую запись ( 0 - стартовый индекс) и делаем swap на ее новое место m. Первые m позиций предназначены для хвоста.
2. m едет на 2m и т.д.
3. До тех пор, пока к*m не попадает в хвост. Тогда swap делается в начало , например на позицию c и цикл повторяется.
Процесс зависит от взаимной делимости N и m.
Если вдруг кратные, то упрется. Тогда делаем переход на первый несдвинутый элемент (посчитать по делимости можно)
И так далее, пока не останется.
Эх, тревожно мне становится за имплементацию функциональности cut and paste
Вот решение которое кажется использовали классики (Керниган и Ричи)
Заметим, что обратить последовательность swap-ом сможет даже самый малограмотный програмер, трудно ему будет создать там баг. Поэтому такой алгоритм очень практичен:
(ba) = reverse(reverse(a)reverse(b)) - забавно, что формула аналогична транспонированию произведения матриц
Иными словами если надо из 12345 сделать 45123, то делаем
1) 32154 и 2) 45123
Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Например:
a,b,a,c,d,а,а - ответ a
a,b,c,a,d,c - ответ нет такого элемента
Библиотекарь упорядочивает книги. Вынимает наугад книгу и ставит на её место, свигая на одну позицию все книги с этого места до места вынутой книги. Сойдётся ли способ и если да, то после не больше скольких книго-перемещений?
Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Если есть много памяти, все элементы вектора целые и ограничены, то все просто
. Надо суммировать значения a(i) в таблице по адресам H(a(i)) и считать максимум. Будет O(N)
Если о векторе ничего неизвестно, то придется вводить хэш-функцию, но это уже O(N*log(N))
Надо подумать, как сэкономить на том, что нужно не значение максимума, а лишь факт превышает ли он половину....
Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах.
Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах.
В приведенной Вами последовательности не существует мажоритарного элемента и мы получим верный ответ, что такого элемента нет. Возможно я плохо сформулировал условие, но надо определить элемент который встречается больше чем N/2 раз.
Простая задачка. Как определить все возможные анаграммы для слова (слово подается на вход пользователем)?
Например:
апельсин -- спаниель
пасечник -- песчаник, песчинка