Тема: Еквівалентність множин
Привіт. Необхідно скласти програму перевірки еквівалентності двох множин, які зберігаються в одновимірному масиві. Що саме мається на увазі під словом "еквівалентність"?
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → C++ → Еквівалентність множин
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися
Привіт. Необхідно скласти програму перевірки еквівалентності двох множин, які зберігаються в одновимірному масиві. Що саме мається на увазі під словом "еквівалентність"?
Не можу точно гарантувати, що ваш викладач це так розуміє, але зазвичай множини вважаються еквівалентними, якщо містять однакові елементи, тобто {2,3,5} еквівалентно {5,3,2}, але не {2,3} і не {2,3,5,7}.
Мене більше цікавить спосіб, яким дві множини зберігаються в одному масиві; хоча й тут можна нафантазувати.
Я так розумію для перевірки спочатку треба обидві множини впорядкувати?? А тоді вже переходити до перевірки?
Я так розумію для перевірки спочатку треба обидві множини впорядкувати?? А тоді вже переходити до перевірки?
Непоганий варіант. Якщо ліньки і масиви невеликі - то можна й подвійним циклом обійтися.
Вийшло щось типу такого:
#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 << " Множини не еквівалентні";
}
Якщо через set, хіба множини (наприклад) {1,1,2,4} і {1,2,4} будуть еквівалентні?
Ви певні, що для такої задачі потрібно будувати дерево? Ні, звісно, це варіант (особливо якщо згадати про std::multiset), однак складність у будь-якому варіанті O(n*log(n)) за оптимального сортування (std::sort); а якщо сортувати за O(n^2), як тут - вибіркою, то легше вже шукати в несортованих масивах, код простіший.
Про однакові елементи бажано уточнити у викладача. У множині однакових елементів бути не має.
Створили окремі методи для розрахунку еквівалентності?
десь приблизно друге я й мав на увазі. бо перше і третє викликає зайві запитання
Сторінки 1
Для відправлення відповіді ви повинні увійти або зареєструватися