|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Ezhguroff 2:5020/400 04 Feb 2003 16:19:28
To : Evgeniy Jirnov
Subject : Re: Сложная (для меня) задача...
--------------------------------------------------------------------------------
Привет! "Evgeniy Jirnov" <Evgeniy.Jirnov@p13.f1230.n5030.z2.fidonet.org>
сообщил(а):
Элементарная волна по графу, где соседние узлы различаются на 1 букву.
EJ> Первое слово вводится с клавиатуры. Последнее вводится с клавиатуры
А вот это никакого отношения к задаче не имеет.
EJ> 2. Придти к конечному слову, так чтобы следующее слово начиналось с
EJ> последней буквы предыдущего. Примерно так:
EJ> комок->куст->тезка->арка(первое слово - "комок", последнее - "арка").
Загоняешь словарь в базу данных, создаешь индексы по первой и последней
буквам слов и выполняешь 1 sql-запрос - в подавляющем большинстве случаев
достаточно будет одного слова. В твоем примере это:
комок->кара->арка.
Если в одно слово не удалось, выполняешь немного более сложный sql-запрос,
отыскивающий два слова...
А т.к. слов всего 10000, то весь словарь элементарно влезает в один массив в
ОЗУ. Сортируешь его по критерию <первая буква>, <последняя буква>, <длина
слова>...
EJ> 3. Есть слово. Гхм... Как бы объяснить... В общем покажу на примере:
EJ> к->ур->а
EJ> а->му->р
EJ> р->яв->к
EJ> а->мб->а
EJ> Первое слово: кара, последнее - арка. Промежуточные: кура, амур, рявк,
EJ> амба.
Аналогично задаче N 2 - ищешь в базе данных подходящие слова и все...
EJ> b. Hаходится в словаре
Каким образом?
С уважением, Андрей.
P.S. Sorry, если пришло в двух экземплярах - гейт глючит.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
