1

Тема: Еквівалентність множин

Привіт. Необхідно скласти програму перевірки еквівалентності двох множин, які зберігаються в одновимірному масиві. Що саме мається на увазі під словом "еквівалентність"?

2

Re: Еквівалентність множин

Не можу точно гарантувати, що ваш викладач це так розуміє, але зазвичай множини вважаються еквівалентними, якщо містять однакові елементи, тобто {2,3,5} еквівалентно {5,3,2}, але не {2,3} і не {2,3,5,7}.
Мене більше цікавить спосіб, яким дві множини зберігаються в одному масиві; хоча й тут можна нафантазувати.

Подякували: Limon1

3

Re: Еквівалентність множин

Я так розумію для перевірки спочатку треба обидві множини впорядкувати?? А тоді вже переходити до перевірки?

4

Re: Еквівалентність множин

Limon написав:

Я так розумію для перевірки спочатку треба обидві множини впорядкувати?? А тоді вже переходити до перевірки?

Непоганий варіант. Якщо ліньки і масиви невеликі - то можна й подвійним циклом обійтися.

5

Re: Еквівалентність множин

Вийшло щось типу такого:

#include <iostream>
#include <fstream>
#include <Windows.h>
using namespace std;
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int mas1[4] = {}, mas2[4] = {};
    ifstream file1("Mas1.txt"), file2("Mas2.txt");
    
    int i = 0, k = 4; // k - кількість елементів в множинах
    while (!file1.eof())
    {
        file1 >> mas1[i];
        cout << mas1[i] << " ";
        i++;
    }
    cout << endl;
    i = 0;
    while (!file2.eof())
    {
        file2 >> mas2[i];
        cout << mas2[i]<< " ";
        i++;
    }
    cout << endl;
        for (i = 0; i < k; ++i)
        {
            // У змінній s зберігається індекс найменшого значення, яке ми знайшли в поточній ітерації
            // Починаємо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0)
            int s = i;
            // Потім шукаємо менший елемент в іншій частині масиву
            for (int c = i + 1; c < k; ++c)
            {
                // Якщо ми знайшли елемент, який менше нашого найменшого елементу
                if (mas1[c] < mas1[s])
                    // то запам'ятовуємо його
                    s = c;
            }
            // s тепер найменший елемент
            // Міняємо місцями наше початкове найменше число з тим, яке ми виявили
            swap(mas1[i], mas1[s]);
        }
        for (i = 0; i < k; ++i)
        {
            // У змінній s зберігається індекс найменшого значення, яке ми знайшли в поточній ітерації
            // Починаємо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0)
            int s = i;
            // Потім шукаємо менший елемент в іншій частині масиву
            for (int c = i + 1; c < k; ++c)
            {
                // Якщо ми знайшли елемент, який менше нашого найменшого елементу
                if (mas2[c] < mas2[s])
                    // то запам'ятовуємо його
                    s = c;
            }
            // s тепер найменший елемент
            // Міняємо місцями наше початкове найменше число з тим, яке ми виявили
            swap(mas2[i], mas2[s]);
        }
        bool a = 1;
        for (int i = 0; i < k; ++i)
        {
            if (mas1[i] != mas2[i])
                a = 0;
        }
        if (a)
            cout << " Множини еквіваленті";
        else
            cout << " Множини не еквівалентні";
}

6

Re: Еквівалентність множин

https://www.google.com/search?-b-d&q=set+c%2B%2B

7

Re: Еквівалентність множин

Якщо через set, хіба множини (наприклад) {1,1,2,4} і {1,2,4} будуть еквівалентні?

8

Re: Еквівалентність множин

Ви певні, що для такої задачі потрібно будувати дерево? Ні, звісно, це варіант (особливо якщо згадати про std::multiset), однак складність у будь-якому варіанті O(n*log(n)) за оптимального сортування (std::sort); а якщо сортувати за O(n^2), як тут - вибіркою, то легше вже шукати в несортованих масивах, код простіший.
Про однакові елементи бажано уточнити у викладача. У множині однакових елементів бути не має.

9

Re: Еквівалентність множин

https://ideone.com/Rjb5DR

Подякували: Limon, leofun012

10

Re: Еквівалентність множин

koala написав:

https://ideone.com/Rjb5DR

Створили окремі методи для розрахунку еквівалентності? *THUMBSUP*  :)

11

Re: Еквівалентність множин

десь приблизно друге я й мав на увазі. бо перше і третє викликає зайві запитання