|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ruslan Shevelyov 2:5020/9481.21 03 Feb 2003 13:59:08
To : Evgeniy Jirnov
Subject : Сложная (для меня) задача...
--------------------------------------------------------------------------------
and all other ppl/robots/animals reading this msg...
31 Jan 03 15:34, Evgeniy Jirnov wrote to All:
EJ> Сабж: есть словарь(текстовый файл), в котором содержатся 10 тыс
EJ> слов(каждое слово на новой строке). Требуется решить три задачи(не
EJ> зависимые друг от друга) с вариантами:
EJ> 1. Придти к конечному слову, изменяя одну букву. Все слова должны
EJ> содержать одно и тоже количество символов. Примерно так:
EJ> дом->док->сок->сук(первое слово - "дом", последнее - "сук"). Первое
EJ> слово вводится с клавиатуры. Последнее вводится с клавиатуры
EJ> 2. Придти к конечному слову, так чтобы следующее слово начиналось с
EJ> последней буквы предыдущего. Примерно так:
EJ> комок->куст->тезка->арка(первое слово - "комок", последнее - "арка").
EJ> Длина слов: a. Все слова должны быть с одинаковым количеством букв b.
EJ> Количество букв может различаться Последнее слово вводится с
EJ> клавиатуры
Первые две задачи я бы решал так: рассмотрим граф, в котором
вершинами являются слова; две вершины соединены ребром/дугой
тогда и только тогда, когда: для первой задачи -- слова различаются
на одну букву; для второй задачи -- последняя буква первого слова
совпадает с первой буквой второго слова. В этом графе заданы
две вершины, осталось найти путь (если он существует).
Hекоторые соображения по оптимизации этого процесса:
1. В задачах 1 и 2а можно сразу выкинуть из словаря все
слова, длина которых отличается от длины конечного слова;
2. Во второй задаче можно считать два слова одинаковыми,
если у них совпадают первая и последняя буквы. Такие "дубликаты"
также можно выкинуть;
3. Сокращённый словарь можно отсортировать и использовать
бинарный поиск;
4. Хранить рёбра графа для второй задачи явно незачем,
а для первой может оказаться целесообразным перед началом
поиска пути составить для каждой вершины список смежных
вершин (а лучше -- их индексов);
5. Если памяти много, можно использовать поиск в ширину.
WBR...
---
* Origin: Cosmo Canyon Station (2:5020/9481.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
