Форум программистов, компьютерный форум CyberForum.ru

Ошбика в алгоритме нахождения разности множеств - C++

Восстановить пароль Регистрация
 
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
04.10.2012, 15:30     Ошбика в алгоритме нахождения разности множеств #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Set& Set::operator-(const Set &set)
{
    Set *raznost = new Set;
    if (this->size != 0 && set.size != 0)
    {
        for (int i = 0; i < this->size; i++)
        {
            for (int j = 0; j < set.size; j++)
            {
                if (this->data[i] == set.data[j])
                {
                    break;
                }
            }
            raznost->data[raznost->size] = this->data[i];
            ++(raznost->size);
        }
    }
    else {
        raznost->size = 0;
        return *raznost;
    }
    return *raznost;
}
В общем в чём проблема:
в два множества(это объекты) введены элементы:
sets[2].add('k'); sets[3].add('x');
sets[2].add('y'); sets[3].add('z');
sets[2].add('h'); sets[3].add('h');
На выходе должен быть результат разности sets[2] - sets[3] равен {k,y}
А получаю {k,y,h}.
Оператор - для объектов перегружен.
В принципе я знаю ошибку, если всё на бумаге или в уме раскидать, то результат правильный выдан, то есть ошибка семантическая.
Но как её решить, не могу я понять
Кучу вариантов перепробовал,везде всё возвращается к этому же результату.

Добавлено через 3 минуты
Так же я менял местами код делая вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Set& Set::operator-(const Set &set)
{
    Set *raznost = new Set;
    if (this->size != 0 && set.size != 0)
    {
        for (int i = 0; i < this->size; i++)
        {
            for (int j = 0; j < set.size; j++)
            {
                if (this->data[i] == set.data[j])
                {
                    break;
                }
                else
                {
                    raznost->data[raznost->size] = this->data[i];
                    ++(raznost->size);
                }
            }
        }
    }
    else {
        raznost->size = 0;
        return *raznost;
    }
    return *raznost;
}
Но это тожже не верно, потому что каждый элемент из первого множества сравниваеться с каждым из второго множества, и в итоге получаем {k,k,k,y,y,y,h,h}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
04.10.2012, 15:31     Ошбика в алгоритме нахождения разности множеств #2
C++
1
2
3
4
5
6
7
8
9
for (int j = 0; j < set.size; j++)//этот цикл у вас вообще бесполезен
            {
                if (this->data[i] == set.data[j])
                {
                    break;
                }
            }
            raznost->data[raznost->size] = this->data[i];//так как это выполнится в любом случае. не зависимо от того, что произойдет в цикле
            ++(raznost->size);
Добавьте булевый флаг перед циклом.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool should_add = true;
for (int j = 0; j < set.size; j++)
            {
                if (this->data[i] == set.data[j])
                {
                    should_add = false;
                    break;
                }
            }
            if(should_add)
            {            
                 raznost->data[raznost->size] = this->data[i];
                 ++(raznost->size);
            }

Не по теме:

эх, форматирование все съехало...

Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
04.10.2012, 15:46  [ТС]     Ошбика в алгоритме нахождения разности множеств #3
Цитата Сообщение от I.M. Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
for (int j = 0; j < set.size; j++)//этот цикл у вас вообще бесполезен
            {
                if (this->data[i] == set.data[j])
                {
                    break;
                }
            }
            raznost->data[raznost->size] = this->data[i];//так как это выполнится в любом случае. не зависимо от того, что произойдет в цикле
            ++(raznost->size);
Добавьте булевый флаг перед циклом.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool should_add = true;
for (int j = 0; j < set.size; j++)
            {
                if (this->data[i] == set.data[j])
                {
                    should_add = false;
                    break;
                }
            }
            if(should_add)
            {            
                 raznost->data[raznost->size] = this->data[i];
                 ++(raznost->size);
            }

Не по теме:

эх, форматирование все съехало...

Я уже добавлял булевый флаг, разници нету...выводит тоже самое {k,k,k,y,y,y,h,h}.Тут идёт сравнение каждого элемента с каждым элементом другого множества, получаеться каждый элемент сравниваеться трижды в данном случае, и трижды он не равен, поэтому трижды он записывается, и так до конца, а вот последний элемент, видно что не 3 раза вывелся а только 2, потому что наконец-то встретил равного себе. С этим и борюсь вот, но пока я проигрываю в борьбе\
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
04.10.2012, 16:19     Ошбика в алгоритме нахождения разности множеств #4
Цитата Сообщение от Elfenlide Посмотреть сообщение
Я уже добавлял булевый флаг
Наверняка вы его добавляли во вложенный цикл. Т.е. не туда.
Булевый флаг должен инициализироваться до цикла по j и проверяться один раз после цикла по j. Т.е. для каждого i будет одна проверка

Можете глянуть тут
http://www.cplusplus.com/reference/a...et_difference/
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
04.10.2012, 16:41     Ошбика в алгоритме нахождения разности множеств #5
Цитата Сообщение от Elfenlide Посмотреть сообщение
Я уже добавлял булевый флаг, разници нету...выводит тоже самое
все правильно вам говорят.
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
~/samples$ cat sample.c 
#include <stdio.h>
 
int main() {
 
    int a1[] = {1, 2, 3, 4, 5};
    int a2[] = {3, 4, 5, 6, 7};
    int flag, i = 0, j;
 
    for (; i < 5; ++i) {
        flag = 1;
 
        for (j = 0; j < 5; ++j)
            if (a1[ i ] == a2[ j ]) {
                flag = 0;
                break;
            }
        if (flag)
            fprintf(stdout, "%2i", a1[ i ]);
    }
    putchar('\n');
 
    return 0;
}
~/samples$ gcc sample.c -o sample
~/samples$ ./sample 
 1 2
~/samples$
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
04.10.2012, 21:41  [ТС]     Ошбика в алгоритме нахождения разности множеств #6
Цитата Сообщение от I.M. Посмотреть сообщение
Наверняка вы его добавляли во вложенный цикл. Т.е. не туда.
Булевый флаг должен инициализироваться до цикла по j и проверяться один раз после цикла по j. Т.е. для каждого i будет одна проверка
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Set& Set::operator-(const Set &set)
{
    Set *raznost = new Set;
    bool flag;
 
    if (this->size != 0 && set.size != 0)
    {
        for (int i = 0; i < this->size; ++i)
        {
            flag = true;
 
            for (int j = 0; j < set.size; ++j)
            {
                if (this->data[i] == set.data[j])
                {
                    flag = false;
                    break;
                }
                if (flag)
                {
                    raznost->data[raznost->size] = this->data[i];
                    ++(raznost->size);
                }               
            }
        }
    }
    else {
        raznost->size = 0;
        return *raznost;
    }
    return *raznost;
}
вот я так делал, и ничего...Даже если так прикинуть то выходит что:
Флаг устанавливается в "1", и становиться 0 только если значение х == у, а так как не равно, то и значение останется "1" у булевой переменной. В итоге сработает if(flag)

Добавлено через 4 минуты
Цитата Сообщение от Elfenlide Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
Set& Set::operator-(const Set &set)
{
    Set *raznost = new Set;
    bool flag;
 
    if (this->size != 0 && set.size != 0)
    {
        for (int i = 0; i < this->size; ++i)
        {
            flag = true;
 
            for (int j = 0; j < set.size; ++j)
            {
                if (this->data[i] == set.data[j])
                {
                    flag = false;
                    break;
                }
                if (flag)
                {
                    raznost->data[raznost->size] = this->data[i];
                    ++(raznost->size);
                }               
            }
        }
    }
    else {
        raznost->size = 0;
        return *raznost;
    }
    return *raznost;
}
вот я так делал, и ничего...Даже если так прикинуть то выходит что:
Флаг устанавливается в "1", и становиться 0 только если значение х == у, а так как не равно, то и значение останется "1" у булевой переменной. В итоге сработает if(flag)
Я понял свою ошибку)\\\Спасибо вам большое всем!)
Yandex
Объявления
04.10.2012, 21:41     Ошбика в алгоритме нахождения разности множеств
Ответ Создать тему
Опции темы

Текущее время: 02:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru