Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 27.02.2015, 09:38   #1
NewLine
Пользователь
 
Регистрация: 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.

Подскажите алгоритм такой проверки. На псевдокоде, коде, блок схемой, текстом, как угодно. Нужна помощь.
NewLine вне форума Ответить с цитированием
Старый 27.02.2015, 10:22   #2
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

а вот кросспостить не надо, валите в первую тему
p51x вне форума Ответить с цитированием
Старый 27.02.2015, 10:33   #3
NewLine
Пользователь
 
Регистрация: 20.02.2011
Сообщений: 11
По умолчанию

Стоп. Где тут "за меня решите"?
Я сам пишу. Мне бы совет как алгоритм построить. Свой вариант я привел. Как бы это в алгоритм запихать. Какой там цикл и условия для выхода. Похоже без GoTo не обойтись

Последний раз редактировалось NewLine; 27.02.2015 в 10:36.
NewLine вне форума Ответить с цитированием
Старый 27.02.2015, 10:59   #4
p51x
Старожил
 
Регистрация: 15.02.2010
Сообщений: 15,695
По умолчанию

Цитата:
Сообщение от NewLine Посмотреть сообщение
Стоп. Где тут "за меня решите"?
Стоп. А научитесь читать и различать подпись и текст поста, а?

П.С. Хотя обычно, кто так бурно реагирует на подпись, то обычно как раз и подходят под нее.
p51x вне форума Ответить с цитированием
Старый 27.02.2015, 11:13   #5
NewLine
Пользователь
 
Регистрация: 20.02.2011
Сообщений: 11
По умолчанию

Ну, согласен. Тут не прав. Тем не менее "Валите" звучит несколько грубовато.
Ну да ладно. В этой теме больше читающих, возможно найдется кто-то кто даст дельный совет. Может даже вы? P51X?
Я сделал примерно так:
Код:
for (int j = 0; j < CurrColWordCo; j++)   //Для каждого из коротких слов списка, упорядоченного по длине. От коротких к длинным
		 {
		   CurrentStr=Form1->ListBox1->Items->Strings[j];  //Берем слово
		   TempPosition=0;                                                  // Текущая позиция 0.
		   TempPosition=AccessPointSeek(TempPosition, CurrentStr, TopWord);      //  Вернем точку входа этого слова в длинное
		   if (TempPosition==0)                                                                       //Если 0 буква, то
		   {
			 Delta[count]=SymbolsCount(CurrentStr);    //Here I remember all itteration Values  // массив запоминаний точек входа (чтобы вернуться можно было для иной попытки) 
			 TempPosition=Delta[count];                //REMEMBER! in case of mistake, i need to start seeking fom j=mistake word+1;  //поменял временную позицию
			 count=count+1;                                //Перескочил на следующее запоминание точки входа
		   }
		   else if (TempPosition>0 && (SymbolsCount(CurrentStr)+TempPosition)<TopWordLen)    //Если уже была точка входа, но слово еще можно подобрать - по длине влезет
		   {
			 if (AccessPointSeek(TempPosition, CurrentStr, TopWord)!=-1)              // И если это оно то
			 {
			   Delta[count]=Delta[count-1]+SymbolsCount(CurrentStr);                   //Сдвигаем точку входа далее
                           TempPosition=Delta[count]
			   count=count+1;                                                                          И плюс еще одна точка запомнена на случай отката
			 }                                                      
		   }
		 }
Так. Надо продолжить.
Прошу подсказки как логику построить

Последний раз редактировалось ACE Valery; 27.02.2015 в 12:49.
NewLine вне форума Ответить с цитированием
Старый 27.02.2015, 14:18   #6
NewLine
Пользователь
 
Регистрация: 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-да

Порядковый номер символа=длинне слова - значит нашли.
Дошли перебором до конца вариантов - не составимо слово из компонент.
Критерий несоставимости - для начального символа не подходит самое последнее, самое длинное слово.

Уважаемые форумчане, помогите ЭТО в алгоритм превратить. В голове своей я это представляю, но как тут с циклами и условиями это беда.
NewLine вне форума Ответить с цитированием
Старый 28.02.2015, 05:55   #7
NewLine
Пользователь
 
Регистрация: 20.02.2011
Сообщений: 11
По умолчанию

Неужели нет соображений никаких ни у кого на этот счет?
NewLine вне форума Ответить с цитированием
Старый 28.02.2015, 09:21   #8
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,792
По умолчанию

У меня точно нет.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 02.03.2015, 12:18   #9
NewLine
Пользователь
 
Регистрация: 20.02.2011
Сообщений: 11
По умолчанию

Уважаемые форумчане. Вот кое-что изобразил. Поправить прошу.
Тут кусок кода который и должен проверить возможность постройки

Код:
int PositionsOfWords[10];    //
		 int WordApplyed[10];
		 int WordCount=0;
		 int Start=0;
		 for (int k = 0; k < CurrColWordCo; k++)  //For Every words in a list
		 {
		   String CurrentStr=Form1->ListBox1->Items->Strings[k];     //Current string
		   int CurrentStrLen=SymbolsCount(CurrentStr);               //Symbols count in a current strng
		   Start=AccessPointSeek(Start, CurrentStr, TopWord);        //Seeking of first symbol number of short word in long one.
		   if (Start==0 && WordCount==0)
		   {
			 PositionsOfWords[WordCount]=CurrentStrLen;   //Запоминаю точки с которых продолжать поиски
			 WordApplyed[WordCount]=k;                    //Запоминаю какие слова применял. В случае необходимости вернуться назад, поиск начну со следующего за этим словом
			 Start=PositionsOfWords[WordCount];           //Стартовая позиция для поиска слов в длинном слове
			 WordCount=WordCount+1;                       //Количество слов...
		   }
		   if ((Start==PositionsOfWords[WordCount-1]+1) && WordCount>0)                   //если не ошибка, и слово нашлось в остатках длинного слова, причем в начале остатка
		   {
			 PositionsOfWords[WordCount]=PositionsOfWords[WordCount-1]+CurrentStrLen;
			 Start=PositionsOfWords[WordCount];
			 WordApplyed[WordCount]=k;
			 WordCount=WordCount+1;
			 if (Start==SymbolsCount(TopWord))
			 {
			   Words=Words+1;
			   Form3->Memo1->Lines->Add("It builded from other words");
			   break;
			 }
		   }
		   if (Start==-1)  //Если вообще не нашлось, то
		   {
			 PositionsOfWords[WordCount]=PositionsOfWords[WordCount-1]; //Забываем последнее из списка запомненых слов, откатываясь назад
			 Start=PositionsOfWords[WordCount];                         //Задаем новую стартовую позицию
			 WordCount=WordCount-1;                                     //Убираем счетчик примененных слов и запомненых элементов массивов
			 if ((k==CurrColWordCo-1) && WordCount==0)         //И если это последнее слово было, то признаем что составить его и вовсе нельзя
			 {
			   Form3->Memo1->Lines->Add("This word cannot be builded");
			   break;
			 }
			 k=WordApplyed[WordCount];
		   }
		 }
	   }
Не оставьте без внимания
NewLine вне форума Ответить с цитированием
Старый 02.03.2015, 20:58   #10
rrrFer
Санитар
Старожил
 
Аватар для rrrFer
 
Регистрация: 04.10.2008
Сообщений: 2,618
По умолчанию

Цитата:
Смысл следующий. Есть массив слов. Их, ну скажем 200 000. Как минимум.
Надо найти и вывести два самых длинных из них таких, что они являются любой комбинацией остальных слов массива. Это раз. А еще подсчитать, сколько вообще в этом массиве слов которые являются комбинацией остальных. Одно слово может быть использовано любое число раз.
Все остальное вроде как к теме не относится.
Начните с пояснения, что значит "является комбинацией"?

ЗЫ1. Откуда вообще задача?
ЗЫ2. Тебе нужен эффективный алгоритм или "тяп-ляп"? - то, что ты делаешь - работать будет невероятно медленно.
Зы3. Ты делаешь это настолько жестоко, что Чикатило кончил бы - инфа 100%

Последний раз редактировалось rrrFer; 02.03.2015 в 21:11.
rrrFer вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нужен скрипт или совет. 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