|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
27.02.2015, 09:38 | #1 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Нетривиальная задача. Нужен совет или помощь
Спрошу еще ив этой ветке. Может подскажет кто.
Смысл следующий. Есть массив слов. Их, ну скажем 200 000. Как минимум. Надо найти и вывести два самых длинных из них таких, что они являются любой комбинацией остальных слов массива. Это раз. А еще подсчитать, сколько вообще в этом массиве слов которые являются комбинацией остальных. Одно слово может быть использовано любое число раз. Что написано: 1. Функция поиска слов заданной длинны. Для того, чтобы начиная с самого длинного и по убыванию считать что-то. 2. Для каждого слова заданной длины, формируется список слов, которые упоминаются в нем как часть. 3. Функция сортировки найденных слов от короткого к длинному. 4. Функция поиска точки входа короткого слова в длинное. Примечание: Функция возвращает первое упоминание, но на вход получает начало поиска, чтобы можно было найти второе и так далее упоминание. В чем не могу разобраться: Логика такая: начиная с самого короткого упомянутого слова - они упорядочены ищем упоминание в длинном слове, затем в оставшейся части и так далее. В случае неудачи возвращаемся назад на количество символов равное последнему подобранному слову и ищем дальше, начиная со следующего по длине. Логика наглядно: длинное слово - abcdefghijklmn короткие a dcd abc defgh efgks klmds hijklm hijklmn алгоритм поиска: a- подходит, осталось bcdefghijklmn dcd-нет, abc-нет ..... hijklmn-нет. //Какое предыдущее значение? a. И оно односимвольное, значит возвращаемся на символ назад и снова ищем, но односимвольные слова пропускаем. a- не подошло. Значит dcd-нет abc-да, осталось defghijklmn. Снова с начала. a-нет, dcd-нет abc-нет defgh - да, осталось ijklmn и так далее. В случае ошибки надо вернуться назад на количество символов равного длине последнего подобранного слова, и может возвращаться надо и не один раз. Вдруг бы не подошло 2 последних подобранных значения а варианты были? Надо начать с определенной точки второй или третий раз, ведь оставались более длинные и подходящие слова. Как? Хотя бы алгоритм. Вот функции которые я написал. Пользуйтесь. int SymbolsCount(String Str) - вернет количество символов в слове int WordCounter(int ColNo) - вернет количество слов, которые упомянуты в длинном. ColNo - каждое длинное слово из массива пишется в таблицу. int AccessPointSeek(int StartP, String ShortS, String LongS) - вернет точку входа - номер буквы с которой начинается короткое слово в длинном. StartP - передается чтобы поиск не сначала начинать, а с заданного символа. Чтобы найти второе... нное вхождение. Все слова для конкретного длинного слова упорядоченные по длине находятся в ListBox. Подскажите алгоритм такой проверки. На псевдокоде, коде, блок схемой, текстом, как угодно. Нужна помощь. |
27.02.2015, 10:22 | #2 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,695
|
а вот кросспостить не надо, валите в первую тему
|
27.02.2015, 10:33 | #3 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Стоп. Где тут "за меня решите"?
Я сам пишу. Мне бы совет как алгоритм построить. Свой вариант я привел. Как бы это в алгоритм запихать. Какой там цикл и условия для выхода. Похоже без GoTo не обойтись Последний раз редактировалось NewLine; 27.02.2015 в 10:36. |
27.02.2015, 10:59 | #4 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,695
|
|
27.02.2015, 11:13 | #5 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Ну, согласен. Тут не прав. Тем не менее "Валите" звучит несколько грубовато.
Ну да ладно. В этой теме больше читающих, возможно найдется кто-то кто даст дельный совет. Может даже вы? P51X? Я сделал примерно так: Код:
Прошу подсказки как логику построить Последний раз редактировалось ACE Valery; 27.02.2015 в 12:49. |
27.02.2015, 14:18 | #6 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Я уже несколько поправил алгоритм. Жаль нет предложений как его строить. Работает все равно некорректно. Исходные данные:
Слово для проверки: abcdefghijklmnop Слова отобранные из кучи мусора: p a ab de cd abc fgh defghi ijklmno cdefghijklmno Логика такая: p -не подходит а- Подходит начиная со второго символа: p -нет a- нет .... cdefghijklmno-нет Вернулись назад и забыли что а подходило Перебираем слова следующие по длине после однобуквенных ab - подойдет. Начинаем сравнивать с третьего символа. p- нет a-нет .... cd- подошло Начинаем сравнивать с пятого символа. p- нет a-нет ... cdefghijklmno-нет Вернулись назад и забыли про cd. cd было двухбуквенным, значит начинаем с трехбуквенных и с третьего символа abc - нет fgh-нет ... cdefghijklmno-нет Вернулись назад и забыли про ab начинаем с трехбуквенных слов и с первого символа abc-да Начинаем с четвертого символа p-нет a-нет ... de-да Начинаем с шестого символа p-нет a-нет ... fgh - да Начинаем с девятого символа p-нет a-нет ... ijklmno-да Начинаем с шестнадцатого символа p-да Порядковый номер символа=длинне слова - значит нашли. Дошли перебором до конца вариантов - не составимо слово из компонент. Критерий несоставимости - для начального символа не подходит самое последнее, самое длинное слово. Уважаемые форумчане, помогите ЭТО в алгоритм превратить. В голове своей я это представляю, но как тут с циклами и условиями это беда. |
28.02.2015, 05:55 | #7 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Неужели нет соображений никаких ни у кого на этот счет?
|
28.02.2015, 09:21 | #8 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,792
|
У меня точно нет.
I'm learning to live...
|
02.03.2015, 12:18 | #9 |
Пользователь
Регистрация: 20.02.2011
Сообщений: 11
|
Уважаемые форумчане. Вот кое-что изобразил. Поправить прошу.
Тут кусок кода который и должен проверить возможность постройки Код:
|
02.03.2015, 20:58 | #10 | |
Санитар
Старожил
Регистрация: 04.10.2008
Сообщений: 2,618
|
Цитата:
Начните с пояснения, что значит "является комбинацией"? ЗЫ1. Откуда вообще задача? ЗЫ2. Тебе нужен эффективный алгоритм или "тяп-ляп"? - то, что ты делаешь - работать будет невероятно медленно. Зы3. Ты делаешь это настолько жестоко, что Чикатило кончил бы - инфа 100% Последний раз редактировалось rrrFer; 02.03.2015 в 21:11. |
|
|
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нужен скрипт или совет. | qbarsik | JavaScript, Ajax | 2 | 07.02.2012 23:51 |
Нужен совет или альтернатива. | vilison | Visual C++ | 23 | 28.10.2010 20:46 |
Нужна помощь или совет программиста | Demiurg2 | Фриланс | 8 | 16.10.2009 12:35 |
Нужна ваша помощь или дельный совет! | alex2008ean | Microsoft Office Access | 1 | 09.12.2008 22:12 |