 |
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Предлагаю завести тему о компьютерных алгоритмах
Для начала такая простая практическая задача. Надо написать функцию, которая меняет местами строчки в текстовом редакторе. В редакторе, текст представлен вектором строчек. Например, вот текст из пяти строчек.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
Пользователь хочет перебросить последние две строки в начало, чтобы было
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
Как решить эту задачу в общем случае, и перебросить последние m елементов вектора в начало? Текст может быть огромным и поэтому просто завести вторую копию текста не разрешается.
|
|
-
Grigoriy
-
-
NOW ONLINE
-
Боярин
-
- Posts: 16389
- Thank you received: 452
-
Karma: 13
-
|
Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
А возможно скажем, другое стандартное представление:
указатель на 1-ую строку
строка:
указатель на следующую строку текст строки
Тогда в начале ставим указатель на ту строку, которую хотим 1-ой( т е 4-ую), в начале 5-ой ставим адрес 1-ой, а, а в начале 3-ей - признак конца.
Короче, мораль: решение зависит от структуры представления данных
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Grigoriy написал(а): Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую. Ну если вектор очень длинный то и на адреса места не хватит. Будем считать, что это требование к алгоритму избежать копирование вектора.
Grigoriy написал(а): Короче, мораль: решение зависит от структуры представления данных Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист (по русски не знаю название термина) строчек. Это тоже ограничение, но можно конечно реализовать и Ваш вариант.
Отредактировано PP (2010-05-29 23:44:21)
|
|
-
Хайдук
-
-
OFFLINE
-
Наместник
-
- Posts: 47195
- Thank you received: 125
-
Karma: 23
-
|
PP написал(а): линкед лист (по русски не знаю название термина) Связанный список, если не ошибаюсь.
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
PP написал(а): Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист Linked list это совсем не вектор.
Вопрос же Григория касался того, позволяете ли формат ограничиться перестановкой адресов, или нужно копировать еще и данные.
Впрочем это не так важно.
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Vladimirovich написал(а): Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться Да операция swap если надо имеется. Грубо говоря небольшое количество строк скопировать можно (например одну), нельзя копировать весь вектор или большую его часть.
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
Ну на первый заход...
В общем случае двигаются все записи. так что общие затраты как минимум О(N) где N - общее число записей.
1. Берем первую запись ( 0 - стартовый индекс) и делаем swap на ее новое место m. Первые m позиций предназначены для хвоста.
2. m едет на 2m и т.д.
3. До тех пор, пока к*m не попадает в хвост. Тогда swap делается в начало , например на позицию c и цикл повторяется.
Процесс зависит от взаимной делимости N и m.
Если вдруг кратные, то упрется. Тогда делаем переход на первый несдвинутый элемент (посчитать по делимости можно)
И так далее, пока не останется.
Итого O(N). Меньше низзя вроде.
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
С точки зрения скорости Ваш алгоритм хорош, но сумеют ли програмеры заимплементировать без багов, ведь наделают ошибок, нет?
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
PP написал(а): С точки зрения скорости Ваш алгоритм хорош, но сумеют ли програмеры заимплементировать без багов, ведь наделают ошибок, нет? Не мои проблемы
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Над быть проще, проще надо быть
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
PP написал(а): Над быть проще, проще надо быть Чтобы быть проще, надо памяти больше давать
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Эх, тревожно мне становится за имплементацию функциональности cut and paste Вот решение которое кажется использовали классики (Керниган и Ричи)
Заметим, что обратить последовательность swap-ом сможет даже самый малограмотный програмер, трудно ему будет создать там баг. Поэтому такой алгоритм очень практичен:
(ba) = reverse(reverse(a)reverse(b)) - забавно, что формула аналогична транспонированию произведения матриц
Иными словами если надо из 12345 сделать 45123, то делаем
1) 32154 и 2) 45123
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Но только чуточку дольше, главное мы сохранили O(N)
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
PP написал(а): Но только чуточку дольше Вот так и размножаются виндоусы
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Например:
a,b,a,c,d,а,а - ответ a
a,b,c,a,d,c - ответ нет такого элемента
Отредактировано PP (2010-06-01 00:21:13)
|
|
-
Хайдук
-
-
OFFLINE
-
Наместник
-
- Posts: 47195
- Thank you received: 125
-
Karma: 23
-
|
РР, а Вы слышали о такой задачке:
Библиотекарь упорядочивает книги. Вынимает наугад книгу и ставит на её место, свигая на одну позицию все книги с этого места до места вынутой книги. Сойдётся ли способ и если да, то после не больше скольких книго-перемещений?
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Вроде уже обсуждали эту задачу на форуме, разве не решили? Это звучит, как вероятностная задача. Интуитивно мат ожидание сходимости должно быть O(n^2)
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
PP написал(а): Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора. Если есть много памяти, все элементы вектора целые и ограничены, то все просто . Надо суммировать значения a(i) в таблице по адресам H(a(i)) и считать максимум. Будет O(N)
Если о векторе ничего неизвестно, то придется вводить хэш-функцию, но это уже O(N*log(N))
Надо подумать, как сэкономить на том, что нужно не значение максимума, а лишь факт превышает ли он половину....
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Vladimirovich написал(а): Если есть много памяти, все элементы вектора целые и ограничены, то все просто Тогда бы было совсем неинтересно
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Если интересно, вот ответ
--
|
|
-
Vladimirovich
-
-
OFFLINE
-
Инквизитор
-
- Posts: 99950
- Thank you received: 1821
-
Karma: 101
-
|
Не. пока не буду смотреть
Подумаю на досуге.
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Подумайте, алгоритм прост и изьящен имхо!
|
|
-
Автор: procrastinator
-
|
Он может быть прост и изящен, но абсолютно бесполезен, поскольку в конце по-прежнему не понятно, есть ли такой элемент или нет.
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
procrastinator написал(а): Он может быть прост и изящен, но абсолютно бесполезен, поскольку в конце по-прежнему не понятно, есть ли такой элемент или нет Для этого делается второй проход. Два прохода это O(N).
|
|
-
Автор: procrastinator
-
|
Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах.
|
|
-
mittelspiel
-
-
OFFLINE
-
Посадник
-
- Posts: 3974
- Thank you received: 14
-
Karma: 1
-
|
Ув. procrastinator, будем рады если Вы зарегистрируетесь и станете полноправным членом нашего преступного научного сообщества
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
procrastinator написал(а): Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах. В приведенной Вами последовательности не существует мажоритарного элемента и мы получим верный ответ, что такого элемента нет. Возможно я плохо сформулировал условие, но надо определить элемент который встречается больше чем N/2 раз.
Отредактировано PP (2010-06-04 20:55:59)
|
|
-
PP
-
-
OFFLINE
-
Холоп
-
- Posts: 31411
- Thank you received: 224
-
Karma: -124
-
|
Простая задачка. Как определить все возможные анаграммы для слова (слово подается на вход пользователем)?
Например:
апельсин -- спаниель
пасечник -- песчаник, песчинка
Отредактировано PP (2010-06-10 00:13:06)
|
|
-
Grigoriy
-
-
NOW ONLINE
-
Боярин
-
- Posts: 16389
- Thank you received: 452
-
Karma: 13
-
|
(Сигма(к(I)))!/ произведение (к(I))!
по всем буквам алфавита, где к(i) - число вхождений i-ой буквы в слово
|
|
|
|
 |