|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Yaroshevich 2:4635/1024.312 02 Feb 2003 06:14:55
To : Evgeniy Jirnov
Subject : Сложная (для меня) задача...
--------------------------------------------------------------------------------
Пятница 31 Январь 2003, Evgeniy Jirnov wrote to All:
EJ> Сабж: есть словарь(текстовый файл), в котором содержатся 10 тыс
EJ> слов(каждое слово на новой строке). Требуется решить три задачи(не
EJ> зависимые друг от друга) с вариантами:
Общее замечание:
Проблема сводиться к перебору(т.е. построению всего возможного дерева
переходов).И поэтому основная задача в оптимизации и ускорении поиска.
Искать нужно с двух сторон(с начала и с конца) одновременно.
Это колосально уменьшает объем дерева при длинной последовательности.
EJ> 1. Придти к конечному слову, изменяя одну букву. Все слова должны
EJ> содержать одно и тоже количество символов. Примерно так:
EJ> дом->док->сок->сук(первое слово - "дом", последнее - "сук"). Первое слово
EJ> вводится с клавиатуры. Последнее вводится с клавиатуры
А тут пригодиться индексный файл по размеру.
И вообще может тебе лучше работать через SQL - зачем писать то что уже
есть(есть индексы, оператор LIKE, который тебе может сильно пригодиться,и т.д.,
но незнаю есть ли драйв для работы с таблицами в формате текстового файла.Очень
сомневаюсь:) Переконвертить в таблицу можно без проблем.
EJ> 2. Придти к конечному слову, так чтобы следующее слово начиналось с
EJ> последней буквы предыдущего. Примерно так: комок->куст->тезка->арка(первое
EJ> слово - "комок", последнее - "арка"). Длина слов: a. Все слова должны быть
^^^^^^^^^^^^^
EJ> с одинаковым количеством букв b. Количество букв может
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
EJ> различаться Последнее слово вводится с клавиатуры
^^^^^^^^^^^
Может я чего не понял ;)
EJ> 3. Есть слово. Гхм... Как бы объяснить... В общем покажу на примере:
EJ> к->ур->а
EJ> а->му->р
EJ> р->яв->к
EJ> а->мб->а
EJ> Первое слово: кара, последнее - арка. Промежуточные: кура, амур, рявк,
EJ> амба. Hеобходимо придти от первого к последнему, используя слова из
EJ> словаря. Первое слово вводится с клавиатуры. Последнее: a. Вводится с
EJ> клавиатуры b. Hаходится в словаре
А это если я правельно понял комбинация первых двух задач?
EJ> Для всех задач: желательно, но не обязательно, найти самый короткий
EJ> путь
EJ> от первого слова до последнего.
При переборе с двух сторон ты сможешь найти и самый короткий путь, и все
возможные пути.
Всего наилучшего тебе, Evgeniy!
Dmitriy
--- GoldED+/W32 1.1.4.7
* Origin: (2:4635/1024.312)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
