#define TOTAL1 10 //количество первых строк
#define TOTAL2 10 //количество вторых строк
void FindNoDup()
{
LPSTR Str1[TOTAL1];
LPSTR Str2[TOTAL2];
// ... тут заполняются первые и вторые строки
for(int x1=0; x1<TOTAL1; x1++)
{
BOOL Flag = true;
for(int x2=0; x2<TOTAL2; x2++)
{
if(strcmp(Str1[x1], Str2[x2]) == 0)
{
Flag = false;
break;
}
}
if(Flag)
{
// Значит строка номер x1 не имет дупликатов во вторых строках
}
}
}
Ищем лишнюю строку.
Есть такие строки
1) первые логические строки str01, str02, str03, str_test;
2) вторые логические строки str11, str12, str13;
Где заведомо str01 равен str11, str02 = str12, str03 = 13.
Вопрос, как сравнивая поочередно все строки найти лишнюю строку, в данном случае str_test? Т.е. нужно найти строку, которая не соответствует ни одной строке из ворых логических строк? Может кто исходник подкинет?
1) первые логические строки str01, str02, str03, str_test;
2) вторые логические строки str11, str12, str13;
Где заведомо str01 равен str11, str02 = str12, str03 = 13.
Вопрос, как сравнивая поочередно все строки найти лишнюю строку, в данном случае str_test? Т.е. нужно найти строку, которая не соответствует ни одной строке из ворых логических строк? Может кто исходник подкинет?
не очень оптимально .
Цитата:
Originally posted by koderAlex
не очень оптимально .
не очень оптимально .
Ну так напиши как оптимально.
Цитата:
Originally posted by AlexandrVSmirno
Ну так напиши как оптимально.
Ну так напиши как оптимально.
Здесь просится алгоритм балансировки. Глянь вот по этой ссылке, может чего накопаешь:Балансировки на С++
Цитата:
Originally posted by AlexandrVSmirno
Здесь просится алгоритм балансировки. Глянь вот по этой ссылке, может чего накопаешь:Балансировки на С++
Здесь просится алгоритм балансировки. Глянь вот по этой ссылке, может чего накопаешь:Балансировки на С++
прогу писать не хочу . если интересно , то могу алгоритм написать .
Цитата:
Originally posted by koderAlex
прогу писать не хочу . если интересно , то могу алгоритм написать .
прогу писать не хочу . если интересно , то могу алгоритм написать .
Давай
Цитата:
Originally posted by Matush
Давай
Давай
а - массив сравнения
б - массив поиска (в нём ищем лишние строки)
а>>б (а - подмассив б : по условию задачи )
{б}>{а}(очевидно)
если добавить два условия , а именно
1) одинакавую длину строк (если не равны ,то дополнять не нулями )
2) строки на массивах упорядочнены (по алфавиту)
,то задача решается сравнением хеш строк .
хеш-строка - каждый элемент которой есть сумма (по модулю)элементов всех строк массива , но каждая следующая строка сдвинута на 1 .
11111111
11111111
+
122222221
для массива а хеш-строка создаётся один раз .
хеш-строка для б создаётся в цикле (условие выхода {а}={б}(равенство размеров массивов))
хеш-строки сравниваются (в простом случае с двух сторон - спереди(первый элемент с первым ,второй со вторым,...)и сзади (последний элемент с последним ,предполедний с продпоследним ,..)),по несоответствиям находят номера строк . строки помечают (чтоб не использовать при создании новой хеш строки )или удаляют из массива .
конец .
в данном цикле за один проход обнаруживается по две строки , но для больших массивов строк можно усложнить алгоритм сравнения и находить несколько строк за проход .
Алгоритм линейный и тривиальный.
1. Находим самую длинную строку. Ее длина N
2. Выделяем память под N символов, забиваем ее нулями
3. Идем опять по всем строкам. Текущую строку объединяем с данным массивом по принципу XOR (каждый символ текущей строки объединяем операцией XOR с соответсвтующим символом выделенной строки и полученный результат записываем на соответствующее место в выделенной строке).
В конце этого алгоритма в выделенной строке как раз и будет "лишняя" строка.
Потому что A XOR A = 0. Поэтому парные строки дадут 0. А непарная останется...
Кто непонял - разъяснения после нового года.
Всех с новым годом! :)
1. Находим самую длинную строку. Ее длина N
2. Выделяем память под N символов, забиваем ее нулями
3. Идем опять по всем строкам. Текущую строку объединяем с данным массивом по принципу XOR (каждый символ текущей строки объединяем операцией XOR с соответсвтующим символом выделенной строки и полученный результат записываем на соответствующее место в выделенной строке).
В конце этого алгоритма в выделенной строке как раз и будет "лишняя" строка.
Потому что A XOR A = 0. Поэтому парные строки дадут 0. А непарная останется...
Кто непонял - разъяснения после нового года.
Всех с новым годом! :)
Цитата:
Originally posted by S_T
Алгоритм линейный и тривиальный.
1. Находим самую длинную строку. Ее длина N
2. Выделяем память под N символов, забиваем ее нулями
3. Идем опять по всем строкам. Текущую строку объединяем с данным массивом по принципу XOR
Алгоритм линейный и тривиальный.
1. Находим самую длинную строку. Ее длина N
2. Выделяем память под N символов, забиваем ее нулями
3. Идем опять по всем строкам. Текущую строку объединяем с данным массивом по принципу XOR
Данный алгоритм работает только если строки повторяются парное число раз и есть только одна строка которая не повторяется
Для большого кол-ва слов применяем след. алгоритм:
1) сортируем слова в обоих списках N*log(N) + M*log(M);
2) сравниваем отсортированные списки N.
где M,N - кол-во слов в списках.
Для небольшого кол-ва слов этот алгоритм может быть неоптимальным. Более оптимальным в данном случае может быть алгоритм перебора с исключением найденных элементов:
1) берем слово из первого списка, ищем его во втором списке;
2) если находим, исключаем слово из обоих списков;
3) повторяем с п.1
Так понимаю, что в худшем случае это будет N*M
1) сортируем слова в обоих списках N*log(N) + M*log(M);
2) сравниваем отсортированные списки N.
где M,N - кол-во слов в списках.
Для небольшого кол-ва слов этот алгоритм может быть неоптимальным. Более оптимальным в данном случае может быть алгоритм перебора с исключением найденных элементов:
1) берем слово из первого списка, ищем его во втором списке;
2) если находим, исключаем слово из обоих списков;
3) повторяем с п.1
Так понимаю, что в худшем случае это будет N*M