Ключевое слово
22 | 09 | 2019
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 29 Май 2010 17:24 #1

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Предлагаю завести тему о компьютерных алгоритмах
Для начала такая простая практическая задача. Надо написать функцию, которая меняет местами строчки в текстовом редакторе. В редакторе, текст представлен вектором строчек. Например, вот текст из пяти строчек.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
Пользователь хочет перебросить последние две строки в начало, чтобы было
4. Пиво без водки, деньги на ветер.
5. Мы за мир.
1. ППГ великий гений всех времен и народов.
2. В СССР не было очередей.
3. В США все хорошо живут.

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

алгоритмические задачки 29 Май 2010 19:27 #2

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 13702
  • Thank you received: 352
  • Karma: 16
Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
А возможно скажем, другое стандартное представление:
указатель на 1-ую строку
строка:
указатель на следующую строку текст строки
Тогда в начале ставим указатель на ту строку, которую хотим 1-ой( т е 4-ую), в начале 5-ой ставим адрес 1-ой, а, а в начале 3-ей - признак конца.
Короче, мораль: решение зависит от структуры представления данных

алгоритмические задачки 29 Май 2010 19:33 #3

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Grigoriy написал(а):
Непонятная задача. Например, возможно представление строчек вектором указателей на адреса. Тогда задача элементарно решается перестановкой - здесь копирование не проблема, адрес имеет длину небольшую.
Ну если вектор очень длинный то и на адреса места не хватит. Будем считать, что это требование к алгоритму избежать копирование вектора.
Grigoriy написал(а):
Короче, мораль: решение зависит от структуры представления данных
Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист (по русски не знаю название термина) строчек. Это тоже ограничение, но можно конечно реализовать и Ваш вариант.

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

алгоритмические задачки 29 Май 2010 21:43 #4

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 37872
  • Thank you received: 85
  • Karma: 22
PP написал(а):
линкед лист (по русски не знаю название термина)
Связанный список, если не ошибаюсь.

алгоритмические задачки 30 Май 2010 02:45 #5

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
PP написал(а):
Поэтому я написал (скорее всего не очень ясно), что в редакторе текст представлен, как вектор, а не линкед лист
Linked list это совсем не вектор.
Вопрос же Григория касался того, позволяете ли формат ограничиться перестановкой адресов, или нужно копировать еще и данные.
Впрочем это не так важно.
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться

Каждому - своё.

алгоритмические задачки 30 Май 2010 03:03 #6

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Vladimirovich написал(а):
Надо завести абстрактную ( с точки зрения алгоритма) операцию перестановки двух строк и более не париться
Да операция swap если надо имеется. Грубо говоря небольшое количество строк скопировать можно (например одну), нельзя копировать весь вектор или большую его часть.

алгоритмические задачки 30 Май 2010 17:44 #7

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
Ну на первый заход...
В общем случае двигаются все записи. так что общие затраты как минимум О(N) где N - общее число записей.

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

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

Итого O(N). Меньше низзя вроде.
Каждому - своё.

алгоритмические задачки 30 Май 2010 17:51 #8

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
С точки зрения скорости Ваш алгоритм хорош, но сумеют ли програмеры заимплементировать без багов, ведь наделают ошибок, нет?

алгоритмические задачки 30 Май 2010 18:01 #9

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
PP написал(а):
С точки зрения скорости Ваш алгоритм хорош, но сумеют ли програмеры заимплементировать без багов, ведь наделают ошибок, нет?
Не мои проблемы

Каждому - своё.

алгоритмические задачки 30 Май 2010 18:03 #10

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Над быть проще, проще надо быть

алгоритмические задачки 30 Май 2010 18:05 #11

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
PP написал(а):
Над быть проще, проще надо быть
Чтобы быть проще, надо памяти больше давать

Каждому - своё.

алгоритмические задачки 30 Май 2010 18:15 #12

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Эх, тревожно мне становится за имплементацию функциональности cut and paste
Вот решение которое кажется использовали классики (Керниган и Ричи)
Заметим, что обратить последовательность swap-ом сможет даже самый малограмотный програмер, трудно ему будет создать там баг. Поэтому такой алгоритм очень практичен:
(ba) = reverse(reverse(a)reverse(b)) - забавно, что формула аналогична транспонированию произведения матриц
Иными словами если надо из 12345 сделать 45123, то делаем
1) 32154 и 2) 45123

алгоритмические задачки 30 Май 2010 18:32 #13

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
Но дольше

Каждому - своё.

алгоритмические задачки 30 Май 2010 19:01 #14

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Но только чуточку дольше, главное мы сохранили O(N)

алгоритмические задачки 31 Май 2010 02:10 #15

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
PP написал(а):
Но только чуточку дольше
Вот так и размножаются виндоусы

Каждому - своё.

алгоритмические задачки 31 Май 2010 20:16 #16

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Есть вектор элементов. Как определить элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Например:
a,b,a,c,d,а,а - ответ a
a,b,c,a,d,c - ответ нет такого элемента

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

алгоритмические задачки 31 Май 2010 21:03 #17

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 37872
  • Thank you received: 85
  • Karma: 22
РР, а Вы слышали о такой задачке:

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

алгоритмические задачки 01 Июнь 2010 03:05 #18

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Вроде уже обсуждали эту задачу на форуме, разве не решили? Это звучит, как вероятностная задача. Интуитивно мат ожидание сходимости должно быть O(n^2)

алгоритмические задачки 01 Июнь 2010 14:59 #19

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
PP написал(а):
Есть вектор элементов. Как определить  элемент (если таковой имеется), которому равно более половины элементов вектора? Алгоритм должен быть О(N), где N длина вектора.
Если есть много памяти, все элементы вектора целые и ограничены, то все просто
. Надо суммировать значения a(i) в таблице по адресам H(a(i)) и считать максимум. Будет O(N)
Если о векторе ничего неизвестно, то придется вводить хэш-функцию, но это уже O(N*log(N))

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

алгоритмические задачки 01 Июнь 2010 16:52 #20

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Vladimirovich написал(а):
Если есть много памяти, все элементы вектора целые и ограничены, то все просто
Тогда бы было совсем неинтересно

алгоритмические задачки 03 Июнь 2010 04:01 #21

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Если интересно, вот ответ
--

алгоритмические задачки 03 Июнь 2010 20:17 #22

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 80662
  • Thank you received: 1118
  • Karma: 81
Не. пока не буду смотреть

Подумаю на досуге.
Каждому - своё.

алгоритмические задачки 03 Июнь 2010 20:40 #23

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Подумайте, алгоритм прост и изьящен имхо!

алгоритмические задачки 04 Июнь 2010 15:56 #24

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

алгоритмические задачки 04 Июнь 2010 16:05 #25

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
procrastinator написал(а):
Он может быть прост и изящен, но абсолютно бесполезен, поскольку в конце по-прежнему не понятно, есть ли такой элемент или нет
Для этого делается второй проход. Два прохода это O(N).

алгоритмические задачки 04 Июнь 2010 16:13 #26

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

алгоритмические задачки 04 Июнь 2010 16:21 #27

  • mittelspiel
  • mittelspiel's Avatar
  • OFFLINE
  • Посадник
  • Posts: 3974
  • Thank you received: 14
  • Karma: 1
Ув. procrastinator, будем рады если Вы зарегистрируетесь и станете полноправным членом нашего преступного научного сообщества

алгоритмические задачки 04 Июнь 2010 16:55 #28

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
procrastinator написал(а):
Все равно не убедили. В последовательности aaaaabbbbbc он выдаст кандидата 'c', ну убедимся мы, что кандидат ложный, а то что есть очень близкие кандидаты проморгаем.
Прямой подсчет частоты, если необходимо с хэшированием, гораздо практичнее при практически тех же затратах.
В приведенной Вами последовательности не существует мажоритарного элемента и мы получим верный ответ, что такого элемента нет. Возможно я плохо сформулировал условие, но надо определить элемент который встречается больше чем N/2 раз.

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

алгоритмические задачки 09 Июнь 2010 17:56 #29

  • PP
  • PP's Avatar
  • NOW ONLINE
  • Боярин
  • Posts: 23653
  • Thank you received: 143
  • Karma: 4
Простая задачка. Как определить все возможные анаграммы для слова (слово подается на вход пользователем)?
Например:
апельсин -- спаниель
пасечник -- песчаник, песчинка

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

алгоритмические задачки 09 Июнь 2010 18:03 #30

  • Grigoriy
  • Grigoriy's Avatar
  • OFFLINE
  • Боярин
  • Posts: 13702
  • Thank you received: 352
  • Karma: 16
(Сигма(к(I)))!/ произведение (к(I))!
по всем буквам алфавита, где к(i) - число вхождений i-ой буквы в слово
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум