| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Прошу помощи в написании алгоритма поиска слова. |
| Автор: 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) пройтись по данному массиву и если числа идут по порядку, то обратить на эти места внимание, и проверить в самом словаре точность вхождения. Хотя можно конечно действовать и чуть по другому. Но это уже дело вкуса |
| Автор: dio30 4.7.2007, 14:37 |
| А следующие задания ты сделал? |
| Автор: BEOL 5.7.2007, 10:35 |
| Создавать масив типа чар и копировать туда весь словарь это во первых дико вовторых не самый быстрый метод допустим в руском словари тыщ 400 слов размером в 8 букв и меньше (т.к это основной размер почти всех слов) предположим что тогда в словаре средний размер слова выйдет 6 букв получается 400к.слов*6 букв/1024=2343,75 кб тоесть это не есть гуд грузить это всё в оперативную память этот метод не самый экономичный не самый быстрый но самый простой хотя это в данном случае не катит лучше воспользоваться хотябы мобильным алгоритмом т9 пробуй..... |
| Автор: SoWa 6.7.2007, 04:20 |
| Кхе, а что кроме массивов словарей предлагаешь? //Критиковать все горазды Ну оптимизируем словари. Надо сперва построить общий словарь слов длинной Х букв. Упорядочить. Потом придумать биективное отображение Char->Int. А потом по каким нибудь критериям разбить его на много массивов, нарпример по диапазонам 1-100; 100-200; 200-300 итд. Чтобы сразу знать, в каком именно массиве искать. Вотъ и новый метод решения, да, так. Другой вопрос- биективное отображение. По сути, числовой хэш. Как работает хэш я пока не знаю(слишком много для 17 лет), поэтому вы сами придумаете. |
| Автор: BEOL 6.7.2007, 15:56 |
| Вобще блин 1. Я никаво не критикую просто предложил алгоритм быстрее грузить пр 1 слову а не загонять весь словарь в оперативную память.... 2. То что тебе 17 лет это тебя не освобождает от отвецтвености за написаный бред мне тоже 17 лет и я не кричу это и изза этава мой код не стает быстрей или меньше занимает места.... 3. И третье """Потом придумать биективное отображение Char->Int. А потом по каким нибудь критериям разбить его на много массивов, нарпример по диапазонам 1-100; 100-200; 200-300""" Перегонаять из чара в инт разбивать на масивы )) тебе даже их прописовать надоест в описании и дойдёт до такова типа "char x40000=''";" |