Set

Приклад 1

Отримати випадковим чином n цілих чисел. Вивести їх за зростанням. Однакові числа виводити один раз.

Будемо використовувати множиниу. Бо: всі елементи множини автоматично сортуються за зростанням та елементи, що вже є у множині, до неї не додаються.

#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    // Ініціалізація генератора випадкових чисел
    srand(time(0));
    
    set<int> numbers;  // Множина для зберігання унікальних чисел
    int n = 10;        // Кількість чисел для генерації
    
    cout << "Згенеровані числа: ";
    for (int i = 0; i < n; i++) {
        int x = rand() % 20;  // Генеруємо числа від 0 до 19
        cout << x << " ";
        numbers.insert(x);     // Додаємо число до множини
    }
    
    cout << "\nУнікальні числа за зростанням: ";
    for (int num : numbers) {
        cout << num << " ";  // Виводимо відсортовані унікальні числа
    }
    
    return 0;
}

Пояснення роботи програми:

Ініціалізація: Генератор випадкових чисел ініціалізується поточним часом.
Генерація чисел: Програма генерує 10 випадкових чисел від 0 до 19.
Зберігання у множині: Числа додаються до множини set, яка автоматично:
- Видаляє дублікати
- Сортує елементи за зростанням
Виведення результатів: Програма показує спочатку всі згенеровані числа, потім - унікальні відсортовані.

Приклад роботи програми:


Згенеровані числа: 7 4 2 8 5 2 4 9 1 7 
Унікальні числа за зростанням: 1 2 4 5 7 8 9

Ключові особливості:

Використання множини для автоматичного сортування та унікальності
Зрозумілий вивід з поясненнями
Коректна робота з випадковими числами
Простий і зрозумілий код

Приклад 2

Отримати випадковим чином n цілих чисел. Чи є серед цих чисел однакові?

Будемо використовувати множиниу. Бо елементи, що вже є у множині, до неї не додаються. Тобто, якщо кількість всіх чисел дорівнює кількості чисел у множині, то всі числа різні. А якщо ні, то були однакові.

#include <iostream>
#include <set>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    // Ініціалізація генератора випадкових чисел
    srand(time(0));
    
    set<int> unique_numbers;  // Множина для зберігання унікальних чисел
    int n = 10;              // Кількість чисел для генерації
    
    cout << "Згенеровані числа: ";
    for (int i = 1; i <= n; i++) {
        int x = i + rand() % 100;  // Генеруємо числа від i до i+99
        cout << x << " ";
        unique_numbers.insert(x);   // Додаємо число до множини
    }
    
    cout << "\nЧи є однакові числа? ";
    if (unique_numbers.size() < n) {
        cout << "Так, є дублікати";
    } else {
        cout << "Ні, всі числа унікальні";
    }
    
    return 0;
}

Пояснення роботи програми:

Ініціалізація: Генератор випадкових чисел ініціалізується поточним часом для унікальності результатів.
Генерація чисел: Програма генерує 10 випадкових чисел у діапазоні [i, i+99] для кожного i від 1 до 10.
Перевірка на дублікати: Множина set автоматично відкидає дублікати:
- Якщо розмір множини менший за кількість згенерованих чисел - є дублікати
- Якщо розмір дорівнює кількості чисел - всі числа унікальні

Приклад роботи програми:


Згенеровані числа: 56 43 101 87 125 42 56 147 108 93 
Чи є однакові числа? Так, є дублікати

Як це працює:

Множина (set) в C++ автоматично зберігає лише унікальні значення. Коли ми додаємо всі згенеровані числа до множини, її розмір буде меншим за загальну кількість чисел, якщо були дублікати.

Приклад 3

Отримати випадковим чином n цілих чисел. Серед чисел можуть бути однакові. Для кожного числа з’ясувати, скільки разів воно зустрічається.

Всі числа запишемо у множиниу та мультимножину. У множину числа запишуться один раз, а у мультимножину декілька разів. Перебираємо числа у множині, та використовуючи функцію count, для кожного числа з'ясовуємо, скільки разів воно зустрічається у мультимножині.

#include <iostream>
#include <set>
#include <multiset>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    // Ініціалізація генератора випадкових чисел
    srand(time(0));
    
    set<int> unique_numbers;      // Для зберігання унікальних чисел
    multiset<int> all_numbers;   // Для зберігання всіх чисел з повтореннями
    int n = 10;                 // Кількість чисел для генерації
    
    cout << "Згенеровані числа: ";
    for (int i = 1; i <= n; i++) {
        int x = i + rand() % 4;  // Генеруємо числа від i до i+3
        cout << x << " ";
        unique_numbers.insert(x);
        all_numbers.insert(x);
    }
    
    cout << "\n\nКількість входжень кожного числа:\n";
    for (int num : unique_numbers) {
        cout << "Число " << num << ": " << all_numbers.count(num) << " раз(и)\n";
    }
    
    return 0;
}

Пояснення роботи програми:

Ініціалізація: Генератор випадкових чисел ініціалізується поточним часом.
Генерація чисел: Програма генерує 10 чисел у діапазоні [i, i+3] для кожного i від 1 до 10.
Зберігання чисел:
- set зберігає унікальні числа (без повторень)
- multiset зберігає всі числа (з повтореннями)
Підрахунок повторень: Для кожного унікального числа з set рахуємо кількість входжень у multiset.

Приклад роботи програми:


Згенеровані числа: 2 3 4 4 6 6 7 8 9 10 

Кількість входжень кожного числа:
Число 2: 1 раз(и)
Число 3: 1 раз(и)
Число 4: 2 раз(и)
Число 6: 2 раз(и)
Число 7: 1 раз(и)
Число 8: 1 раз(и)
Число 9: 1 раз(и)
Число 10: 1 раз(и)

Ключові особливості:

Використовує set для унікальних значень
Використовує multiset для підрахунку кількості входжень
Має зрозумілий вивід з підписами
Коректно працює з випадковими числами

Приклад 4

Ввести два слова. Перевірити, чи вони є анаграмами (тобто складаються з однакових літер у будь-якому порядку).

Літери кожного слова запишемо у дві різні множини, а потім їх порівняємо. Якщо вони однакові, то так, інакше ні.

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    setlocale(0, "");  // Для підтримки українських літер
    
    multiset<char> letters1, letters2;  // Для зберігання літер з урахуванням кількості
    string word1, word2;
    
    // Введення слів
    cout << "Введіть перше слово: ";
    getline(cin, word1);
    cout << "Введіть друге слово: ";
    getline(cin, word2);
    
    // Видалення пробілів (якщо потрібно)
    word1.erase(remove(word1.begin(), word1.end(), ' '), word1.end());
    word2.erase(remove(word2.begin(), word2.end(), ' '), word2.end());
    
    // Додавання літер до мультимножин
    for (char c : word1) {
        letters1.insert(tolower(c));  // Регістронезалежне порівняння
    }
    for (char c : word2) {
        letters2.insert(tolower(c));
    }
    
    // Перевірка на анаграму
    cout << "Результат: ";
    if (letters1 == letters2) {
        cout << "Так, це анаграми";
    } else {
        cout << "Ні, це не анаграми";
    }
    
    return 0;
}

Пояснення роботи програми:

Введення слів: Користувач вводить два слова або фрази.
Обробка вхідних даних:
- Видаляються пробіли (для перевірки фраз)
- Літери переводяться в нижній регістр (регістронезалежна перевірка)
Зберігання літер: Кожна літера зберігається у мультимножині, яка враховує кількість входжень кожної літери.
Перевірка на анаграму: Якщо мультимножини літер ідентичні - слова є анаграмами.

Приклад роботи програми:


Введіть перше слово: Шалов
Введіть друге слово: Волаш
Результат: Так, це анаграми

Додано обробку пробілів (для перевірки фраз)
Реалізовано регістронезалежне порівняння
Додано зрозумілі повідомлення для вводу/виводу

Як це працює:

Анаграми - це слова, що складаються з одних і тих же літер у різному порядку. Мультимножина (multiset) зберігає елементи з урахуванням їх кількості, тому ідеально підходить для такої перевірки.

Приклад 5

Дано дві множини. Знайти числа, які є в обох множинах (перетин)

Код програми:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Ініціалізація множин
    set<int> s1 = {2, 3, 5, 7, 10, 12, 13, 19};
    set<int> s2 = {1, 5, 7, 13, 20, 37, 40};
    set<int> intersection;  // Для зберігання спільних елементів

    // Знаходження перетину множин
    for (int x : s1) {
        if (s2.count(x) > 0) {
            intersection.insert(x);
        }
    }

    // Виведення результату
    cout << "Перетин множин: ";
    for (int x : intersection) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Пояснення роботи програми:

Ініціалізація множин: Дві множини s1 і s2 ініціалізуються заданими значеннями.
Знаходження перетину:
- Для кожного елементу з першої множини (s1) перевіряємо, чи він є у другій множині (s2)
- Якщо елемент є в обох множинах, додаємо його до множини intersection
Виведення результату: Виводимо всі елементи множини intersection.

Приклад роботи програми:


Перетин множин: 5 7 13

Ключові особливості:

Використовує метод count() для перевірки наявності елемента
Зберігає результат у відсортованому вигляді (властивість set)
Має простий і зрозумілий код
Ефективно працює з відсортованими множинами

Приклад 6

Дано дві множини. Знайти числа, які є хоча б в одній множині (об'єднання)

Код програми:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Ініціалізація множин
    set<int> s1 = {2, 3, 5, 7, 10, 12, 13, 19};
    set<int> s2 = {1, 5, 7, 13, 20, 37, 40};
    set<int> union_set;  // Для зберігання об'єднання множин

    // Додавання елементів з першої множини
    for (int x : s1) {
        union_set.insert(x);
    }

    // Додавання елементів з другої множини
    for (int x : s2) {
        union_set.insert(x);
    }

    // Виведення результату
    cout << "Об'єднання множин: ";
    for (int x : union_set) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Пояснення роботи програми:

Ініціалізація множин: Дві множини s1 і s2 ініціалізуються заданими значеннями.
Формування об'єднання:
- Спочатку додаємо всі елементи з першої множини (s1)
- Потім додаємо всі елементи з другої множини (s2)
- Властивість set автоматично видаляє дублікати
Виведення результату: Виводимо всі елементи множини union_set у відсортованому порядку.

Приклад роботи програми:


Об'єднання множин: 1 2 3 5 7 10 12 13 19 20 37 40

Ключові особливості:

Використовує властивість set автоматично видаляти дублікати
Зберігає елементи у відсортованому порядку
Має простий і зрозумілий код
Ефективно об'єднує множини

Приклад 7

Дано дві множини. Знайти числа, які є у першій множині, але немає в другій (віднімання).

Код програми:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Ініціалізація множин
    set<int> s1 = {2, 3, 5, 7, 10, 12, 13, 19};
    set<int> s2 = {1, 5, 7, 13, 20, 37, 40};
    set<int> difference;  // Для зберігання різниці множин

    // Знаходження різниці s1 - s2
    for (int x : s1) {
        if (s2.count(x) == 0) {  // Якщо елемент відсутній у s2
            difference.insert(x);
        }
    }

    // Виведення результату
    cout << "Різниця множин s1 - s2: ";
    for (int x : difference) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Пояснення роботи програми:

Ініціалізація множин: Дві множини s1 і s2 ініціалізуються заданими значеннями.
Знаходження різниці:
- Для кожного елементу з першої множини (s1) перевіряємо, чи він відсутній у другій множині (s2)
- Якщо елемент є в s1, але відсутній в s2, додаємо його до множини difference
Виведення результату: Виводимо всі елементи множини difference.

Приклад роботи програми:


Різниця множин s1 - s2: 2 3 10 12 19

Ключові особливості:

Використовує метод count() для перевірки наявності елемента
Зберігає результат у відсортованому вигляді (властивість set)
Має простий і зрозумілий код
Ефективно працює з відсортованими множинами

Приклад 8

Дано дві множини. Знайти числа, які є у другій множині, але немає у першій (віднімання).

Код програми:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Ініціалізація множин
    set<int> s1 = {2, 3, 5, 7, 10, 12, 13, 19};
    set<int> s2 = {1, 5, 7, 13, 20, 37, 40};
    set<int> difference;  // Для зберігання різниці множин

    // Знаходження різниці s2 - s1
    for (int x : s2) {
        if (s1.count(x) == 0) {  // Якщо елемент відсутній у s1
            difference.insert(x);
        }
    }

    // Виведення результату
    cout << "Різниця множин s2 - s1: ";
    for (int x : difference) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Пояснення роботи програми:

Ініціалізація множин: Дві множини s1 і s2 ініціалізуються заданими значеннями.
Знаходження різниці:
- Для кожного елементу з другої множини (s2) перевіряємо, чи він відсутній у першій множині (s1)
- Якщо елемент є в s2, але відсутній в s1, додаємо його до множини difference
Виведення результату: Виводимо всі елементи множини difference.

Приклад роботи програми:


Різниця множин s2 - s1: 1 20 37 40

Ключові особливості:

Використовує метод count() для перевірки наявності елемента
Зберігає результат у відсортованому вигляді (властивість set)
Має простий і зрозумілий код
Ефективно працює з відсортованими множинами

Приклад 9

Дано дві множини. Знайти їх симетричну різницю.

Код програми:

#include <iostream>
#include <set>
using namespace std;

int main() {
    // Ініціалізація множин
    set<int> s1 = {2, 3, 5, 7, 10, 12, 13, 19};
    set<int> s2 = {1, 5, 7, 13, 20, 37, 40};
    set<int> sym_diff;  // Для зберігання симетричної різниці

    // Знаходимо елементи, які є в s1, але відсутні в s2
    for (int x : s1) {
        if (s2.count(x) == 0) {
            sym_diff.insert(x);
        }
    }

    // Знаходимо елементи, які є в s2, але відсутні в s1
    for (int x : s2) {
        if (s1.count(x) == 0) {
            sym_diff.insert(x);
        }
    }

    // Виведення результату
    cout << "Симетрична різниця множин: ";
    for (int x : sym_diff) {
        cout << x << " ";
    }
    cout << endl;

    return 0;
}

Пояснення роботи програми:

Ініціалізація множин: Дві множини s1 і s2 ініціалізуються заданими значеннями.
Знаходження симетричної різниці:
- Спочатку шукаємо елементи, які є в s1, але відсутні в s2
- Потім шукаємо елементи, які є в s2, але відсутні в s1
- Всі знайдені елементи додаємо до множини sym_diff
Виведення результату: Виводимо всі елементи множини sym_diff у відсортованому порядку.

Приклад роботи програми:


Симетрична різниця множин: 1 2 3 10 12 19 20 37 40

Ключові особливості:

Використовує метод count() для перевірки наявності елемента
Зберігає результат у відсортованому вигляді (властивість set)
Має простий і зрозумілий код
Ефективно працює з відсортованими множинами

Вперед Зміст