Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Алгоритм поиска совпадений в словах

Автор: KycoK 5.11.2005, 06:18

У меня проблема с разработкой наиболее рационального алгоритма для последущей реализации на си++. В двух словах: - имеется 8 различных переменных (напр.: a, b, c, d, e, f, g, h) - из этих переменных задаются различные комбинации по 4 элемента - из них нужно найти комбинации с 3-мя совпадающими в любой последовательности элементами и выделить совпадающие в отдельную комбинацию по 3 элемента (напр.: acef && achf => acf). Если у какой-либо из комбинаций все элементы совпали или, если у какой-либо из комбинаций вообще ни с кем не оказалось совпадений, то прописать её в получившемся результате полностью, т.е. из 4-рех членов. В дальнейшем эта N-элементная комбинация не сравнивается с (N-1)-комбинациями - из получившегося результата снова по той же схеме выбирают совпадающие комбинации, но уже по 2-ум совпадениям. Если у какой-либо из комбинаций все элементы совпали или, если у какой-либо из комбинаций вообще ни с кем не оказалось совпадений, то прописать её в получившемся результате полностью - из получившегося результата снова по той же схеме выбирают совпадающие комбинации, но уже по 1-му совпадению. Если у какой-либо из комбинаций все элементы совпали или, если у какой-либо из комбинаций вообще ни с кем не оказалось совпадений, то прописать её в получившемся результате полностью Помогите начинающему программисту, кто чем может. Не брезговаю и готовыми программами =))

Автор: eskaflone 5.11.2005, 21:34

на каждую комбинацию заводишь переменнюю байт , совпадения проверять and'ом.

Автор: KycoK 6.11.2005, 11:14

Спасибо, но у меня проблема в том, чтобы машина видела не просто комбинацию, а именно 4 эл-та в ней.

Автор: Akina 7.11.2005, 09:42

Цитата(KycoK @ 6.11.2005, 12:14) проблема в том, чтобы машина видела не просто комбинацию, а именно 4 эл-та в ней. Нужно сравнивать не комбинации, а маски вхождения: Код for (i=1;i<4;i++) { if (num_of_part(n1,i)=num_of_part(n2,i)) then equals(n1,n2)++ } этот код заполнит тебе матрицу equals, каждый эл-т которой = кол-во совпадений эл-тов в наборах n1 и n2. А далее сколь тебе там надо - 3 совпадения? отбери те, где 3 в equals... надо исключать наборы? обработанные элементы и/или исключенные строки,столбцы помечай как equals(n1,n2)=-1

Автор: KycoK 7.11.2005, 16:50

Извини за мою тупость , но не мог бы ты рассказать немного поподробнее об этом способе. Ну чуточку раскрыть тему, так сказать. Потому что си я взялся изучать совсем недавно, и опыта у меня... ну очень мало.

Автор: Mit 7.11.2005, 19:26

а если с множеством попробовать

Автор: KycoK 10.11.2005, 09:52

А правда... что если множеством?

Автор: Mit 10.11.2005, 10:37

я до конца не понял задание, если можешь, попробуй наглядно объяснить (приведи пример)

Автор: Mit 10.11.2005, 10:41

и вообще то, что ты привел - это и есть задание или твое истолкование

Автор: KycoK 11.11.2005, 12:59

2Mit: Ну это я немного упростил основное задание, а в принципе ничего не изменилось

Автор: KycoK 11.11.2005, 13:59

Ну вот например даны комбинации (из этих же a,b,c,d,e,f,g,h): abcd, abch, abgd, abgh, afcd, afch, afgd, afgh, ebcd, ebch, ebgd. От программиста требуется создать программу, которая найдёт 3 одинаковых элемента в этих комбинациях... /попорядку, т.е. 1ый сравниваем со вторым, потом первый с третим,его же с четвёртым и т.д. Когда первый сравнили со всеми, переходим ко второму и опять начинаем сравнивать (но уже второй) по той же схеме. Так в теории, а на практике можно любым способом сравнивать/ ...и создаст новые комбинации по три элемента в каждом, исключая 4-ый, несовпадающий элемент из двух 4-значных комбинаций. и создавая из них одну. трёхзначную Ну например abcd сравниваем с abch, получаем abc abcd сравниваем с abgd, получаем abd abcd сравниваем с abgh, получаем abcd и abgh (если abgh ни с кем не совпадёт, т.е. не найдётся даже одной сходной с ней по трём элементам комбинации, то она переписывается в исходном виде, т.е. четырёхзначной. abcd итак уже совпала с двумя комбинациями, поэтому ей это не грозит) abcd & afcd = acd abcd & afch = afch abcd & afgd = afgd abcd & afgh = afgh abcd & ebcd = bcd abcd & ebgd = ebgd abch & abgd = abgd abch & abgh = abh abch & afcd = afcd abch & afch = ach abch & afgd = afgd abch & afgh = afgh abch & ebcd = ebcd abch & ebch = bch abch & ebgd = ebgd abgd & abgh = abg и т.д... Ну вот как-то так Вообще, я это дело столько раз делал на бумаге, поэтому могу предоставить перечень того, что с чем сокращается. Ну.. уловил суть?

Автор: KycoK 13.11.2005, 09:17

По идее всего комбинаций - 16 (когда по 4) по 3 - 8 по две - 4 А сама прогамма изначально должна была запрашивать ввод числа n - число элементов в комбинации. Вотъ

Автор: KycoK 15.11.2005, 15:32

Может у кого возникливопросы по формулировке задания? Или ещё что Я выложу что у меня на данный момент имеется

Автор: KycoK 2.12.2005, 18:57

Программа уже исправно ищет и генерирует матрицу из n=3 в n=2

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)