ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Volkov Valeriy 2:5020/400 30 Sep 2001 18:16:49
To : Sergey Naidenov
Subject : Re: Выбоp всех слов из массива
--------------------------------------------------------------------------------
Hello Sergey Naidenov,
подумав возникли следующие мысли по поводу задачи
во первых длина слова в принципе не ограниченно сверху
следовательно можно решать задачу тольно искать все слова определнной
длинны.
1.Задачу наверно можно путем комбинаторики
представить отображения из [N,M] ~ [1..N..M]
определить понятие нормы между двумя числами
из всех чепочик длины n выблать только те у которых
длина между соседними буквами =1
вычислительная сложность правда будет (M*N)^n :(
2.Представить матрицу в виде графа
найдти множество путий не содержащий циклов
множество контуров в графе
потом для всех путей найти все слова + варианты
когда вна пути встречается цикл длины меньше остатка
3.Можно ещё подумать над тем что в принципе можно оценить
кол-во слов длины n
1: N*M
2: 4*N*M-2(N+M)
..
n: 4^(n-1)*N*M-2*(n-1)*(N+M)
по моему так.И нельзя ли из этого чегонибудь выжать?
С уважением Dooh
--- ifmail v.2.15dev5
* Origin: Gamma NNTP server Moscow Russia (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Выбоp всех слов из массива