| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > Подскажите алгоритм |
| Автор: Chapaev 7.6.2006, 21:19 |
| Есть задача: "Найти множество всех слов, которые встречаются в каждом из двух заданных предложений. Использовать списки." Как лучше сделать? Забивать все слова первого в список, потом по-очереди брать каждый элемент и сравнивать его со всеми словами во втором и в зависимости от результата оставлять или выкидывать? И какие списки удобнее использовать двунаправленные или простые?  |
| Автор: Феона 9.6.2006, 14:08 |
| народ!вот такая задачка есть--решить "раскраску" методом перебора, реализуя тип раскраска в виде стэка(списка). Добавлено @ 14:16 ещё...---удалить из текста q все вхождения заданного слова w(текст и слово заданы списком символов).Написать модуль:выделения слова, сравнения его с даннным , удаление найденного слова.Модуль u_slovo дополнить процедурами. |
| Автор: Albinos_x 9.6.2006, 17:12 |
| Феона, создате новую тему |
| Автор: Pete 9.6.2006, 21:37 |
| Если хранить только указатель на первый элемент, а в каждом узле указатель на следующий (и предыдущий), то квадратичную сложность можно уменьшить, разве что на константу, упорядочив элементы по алфавиту. |
| Автор: Rockie 10.6.2006, 19:15 | ||||
ну я так тоже думаю. только я бы не выкидывал/оставлял, а печатал/не печатал соответственно =) imho списки надо использовать те, которые позволяют добиться цели. =)
про квадратичную сложность поподробней пожалуйста. |
| Автор: Pete 10.6.2006, 19:47 |
| Надо сравнить каждое слово с каждым. Пусть сравнение 2-х слов --- одна операция и пусть в предложениях соответственно m и n слов. Тогда сложность алгоритма в худшем случае будет mn. |
