Предлагаю завести тему о компьютерных алгоритмах
Для начала такая простая практическая задача. Надо написать функцию, которая меняет местами строчки в текстовом редакторе. В редакторе, текст представлен вектором строчек. Например, вот текст из пяти строчек.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
Пользователь хочет перебросить последние две строки в начало, чтобы было
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.

Как решить эту задачу в общем случае, и перебросить последние m елементов вектора в начало? Текст может быть огромным и поэтому просто завести вторую копию текста не разрешается.

Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
А возможно скажем, другое стандартное представление:
указатель на 1-ую строку
строка:
указатель на следующую строку текст строки
Тогда в начале ставим указатель на ту строку, которую хотим 1-ой( т е 4-ую), в начале 5-ой ставим адрес 1-ой, а, а в начале 3-ей - признак конца.
Короче, мораль: решение зависит от структуры представления данных

Grigoriy написал(а):Ну если вектор очень длинный то и на адреса места не хватит. Будем считать, что это требование к алгоритму избежать копирование вектора.
Grigoriy написал(а):Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист (по русски не знаю название термина) строчек. Это тоже ограничение, но можно конечно реализовать и Ваш вариант.

Отредактировано PP (2010-05-29 23:44:21)

PP написал(а):Связанный список, если не ошибаюсь.

PP написал(а):Linked list это совсем не вектор.
Вопрос же Григория касался того, позволяете ли формат ограничиться перестановкой адресов, или нужно копировать еще и данные.
Впрочем это не так важно.
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться

Vladimirovich написал(а):Да операция swap если надо имеется. Грубо говоря небольшое количество строк скопировать можно (например одну), нельзя копировать весь вектор или большую его часть.

Ну на первый заход...
В общем случае двигаются все записи. так что общие затраты как минимум О(N) где N - общее число записей.

1. Берем первую запись ( 0 - стартовый индекс) и делаем swap на ее новое место m. Первые m позиций предназначены для хвоста.
2. m едет на 2m и т.д.
3. До тех пор, пока к*m не попадает в хвост. Тогда swap делается в начало , например на позицию c и цикл повторяется.

Процесс зависит от взаимной делимости N и m.
Если вдруг кратные, то упрется. Тогда делаем переход на первый несдвинутый элемент (посчитать по делимости можно)
И так далее, пока не останется.

Итого O(N). Меньше низзя вроде.

С точки зрения скорости Ваш алгоритм хорош, но сумеют ли програмеры заимплементировать без багов, ведь наделают ошибок, нет?

PP написал(а):Не мои проблемы

Над быть проще, проще надо быть

PP написал(а):Чтобы быть проще, надо памяти больше давать

Эх, тревожно мне становится за имплементацию функциональности cut and paste Вот решение которое кажется использовали классики (Керниган и Ричи)
Заметим, что обратить последовательность swap-ом сможет даже самый малограмотный програмер, трудно ему будет создать там баг. Поэтому такой алгоритм очень практичен:
(ba) = reverse(reverse(a)reverse(b)) - забавно, что формула аналогична транспонированию произведения матриц
Иными словами если надо из 12345 сделать 45123, то делаем
1) 32154 и 2) 45123

Но дольше

Но только чуточку дольше, главное мы сохранили O(N)

PP написал(а):Вот так и размножаются виндоусы

Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Например:
a,b,a,c,d,а,а - ответ a
a,b,c,a,d,c - ответ нет такого элемента

Отредактировано PP (2010-06-01 00:21:13)

РР, а Вы слышали о такой задачке:

Библиотекарь упорядочивает книги. Вынимает наугад книгу и ставит на её место, свигая на одну позицию все книги с этого места до места вынутой книги. Сойдётся ли способ и если да, то после не больше скольких книго-перемещений?

Вроде уже обсуждали эту задачу на форуме, разве не решили? Это звучит, как вероятностная задача. Интуитивно мат ожидание сходимости должно быть O(n^2)

PP написал(а):Если есть много памяти, все элементы вектора целые и ограничены, то все просто . Надо суммировать значения a(i) в таблице по адресам H(a(i)) и считать максимум. Будет O(N)
Если о векторе ничего неизвестно, то придется вводить хэш-функцию, но это уже O(N*log(N))

Надо подумать, как сэкономить на том, что нужно не значение максимума, а лишь факт превышает ли он половину....

Vladimirovich написал(а):Тогда бы было совсем неинтересно

Если интересно, вот ответ
--

Не. пока не буду смотреть
Подумаю на досуге.

Подумайте, алгоритм прост и изьящен имхо!

Он может быть прост и изящен, но абсолютно бесполезен, поскольку в конце по-прежнему не понятно, есть ли такой элемент или нет.

procrastinator написал(а):Для этого делается второй проход. Два прохода это O(N).

Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах.

Ув. procrastinator, будем рады если Вы зарегистрируетесь и станете полноправным членом нашего преступного научного сообщества

procrastinator написал(а):В приведенной Вами последовательности не существует мажоритарного элемента и мы получим верный ответ, что такого элемента нет. Возможно я плохо сформулировал условие, но надо определить элемент который встречается больше чем N/2 раз.

Отредактировано PP (2010-06-04 20:55:59)

Простая задачка. Как определить все возможные анаграммы для слова (слово подается на вход пользователем)?
Например:
апельсин -- спаниель
пасечник -- песчаник, песчинка

Отредактировано PP (2010-06-10 00:13:06)

(Сигма(к(I)))!/ произведение (к(I))!
по всем буквам алфавита, где к(i) - число вхождений i-ой буквы в слово