Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Прошу помощи в написании алгоритма поиска слова.


Автор: olegrolik 11.5.2007, 14:30
a.    Генерирует с повторениями 8 случайных букв английского алфавита.
b.    Проверяет, пользуясь приложенным словарем, можно ли составить из этих букв три пятибуквенных, три четырехбуквенных и три трехбуквенных слова (единственное вхождение буквы в слово). 
c.    При невозможности повторяет шаг (a).
Пример – pdfokope:
poker, …, …
code, …, …
pop, …, …
Сгенерированные буквы и слова отобразить на экране (вывести в консоль).
Алгоритм желательно максимально оптимизировать по времени.


--------------------------------
пунтк а и с не так сложны. самое главное - это пункт b. Помогите пожалуйста написать алгоритм поиска слов. Словарь - это текстовый документ такого вида :
Aarhus
Aaron
Ababa
aback
....
и т.д.
Спасибо за внимание.

Автор: Fin 11.5.2007, 16:15
Когда то я решал подобную задачу таким способом:
1) Создать массив с типом integer (int)  длиной по количеству символов находящихся в словаре. заполнить этот массив по возрастающей от 0 с шагом 1.  
2) Создать массив char и копировать туда весь текст словаря.   
3) Сортироть массив char по возрастающей. При этом, при переносе символа также переносить в массиве int на соответствуюшие места. Естественно тут нужна быстрая сортировка.
4) Теперь у нас получается массив вхождения символа в словарь
5) остается только по каждому генерируемому символу объединить массив вхождения и отсортировать его.
6) пройтись по данному массиву и если числа идут по порядку, то обратить на эти места внимание, и проверить в самом словаре точность вхождения. Хотя можно конечно действовать и чуть по другому. Но это уже дело вкуса smile

Автор: dio30 4.7.2007, 14:37
А следующие задания ты сделал?

Автор: BEOL 5.7.2007, 10:35
Создавать масив типа чар и копировать туда весь словарь это во первых дико вовторых не самый быстрый метод допустим в руском словари тыщ 400 слов размером в 8 букв и меньше (т.к это основной размер почти всех слов) предположим что тогда в словаре средний размер слова выйдет 6 букв получается 400к.слов*6 букв/1024=2343,75 кб тоесть это не есть гуд грузить это всё в оперативную память этот метод не самый экономичный не самый быстрый но самый простой хотя это в данном случае не катит лучше воспользоваться хотябы мобильным алгоритмом т9 пробуй.....   smile 

Автор: SoWa 6.7.2007, 04:20
Кхе, а что кроме массивов словарей предлагаешь? //Критиковать все горазды
Ну оптимизируем словари. Надо сперва построить общий словарь слов длинной Х букв. Упорядочить. Потом придумать биективное отображение Char->Int. А потом по каким нибудь критериям разбить его на много массивов, нарпример по диапазонам 1-100; 100-200; 200-300 итд. Чтобы сразу знать, в каком именно массиве искать. Вотъ и новый метод решения, да, так.

Другой вопрос- биективное отображение. По сути, числовой хэш. Как работает хэш я пока не знаю(слишком много для 17 лет), поэтому вы сами придумаете.

Автор: BEOL 6.7.2007, 15:56
Вобще блин  smile 
1. Я никаво не критикую просто предложил алгоритм быстрее грузить пр 1 слову а не загонять весь словарь в оперативную память....
2. То что тебе 17 лет это тебя не освобождает от отвецтвености за написаный бред мне тоже 17 лет и я не кричу это и изза этава мой код не стает быстрей или меньше занимает места....
3. И третье """Потом придумать биективное отображение Char->Int. А потом по каким нибудь критериям разбить его на много массивов, нарпример по диапазонам 1-100; 100-200; 200-300""" Перегонаять из чара в инт разбивать на масивы )) тебе даже их прописовать надоест в описании и дойдёт до такова типа "char x40000=''";" smile) ? даже зацикленость не на том!!! Aфтару темы основное написать алгоритм проверки (Составления из сгенерированного ряда символов 3 слова длиной н букв СО СЛОВАРНЫМ ПРАВОПИСАНИЕМ) фсё

Автор: SoWa 7.7.2007, 19:42
Не кипиши, спокойнее )
Функцию я такую придумал, да и без меня их немало. Конечно, числовой хэш бы лучше.
Задача на перебор. Или на ИИ. Ну если моск, пиши ИИ. А я перебор напишу. Алгоритм ведь вполне четкий.


Цитата(BEOL @  6.7.2007,  15:56 Найти цитируемый пост)
 алгоритм быстрее грузить пр 1 слову а не загонять весь словарь в оперативную память....

Ерм... А жесткие диски и индексация еще не придуманы?! Итерация при подгрузке выдет постоянно N. А со словарями- один раз создал за Н итерация, а потом спокойно юзаешь
Цитата(BEOL @  6.7.2007,  15:56 Найти цитируемый пост)
2. То что тебе 17 лет это тебя не освобождает от отвецтвености за написаный бред мне тоже 17 лет и я не кричу это и изза этава мой код не стает быстрей или меньше занимает места....

Стремись к оптимизации ) А больше кричишь- заметнее ;)

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)