Приклад

Сформувати дві кінцеві множини, заповнивши їх довільними латинськими літерами від A до Z. Обміняти місцями обидві множини, не вводячи додаткової змінної множинного типу.

1. Відомі значення елементів двох кінцевих символьних множин.

2. Ми не маємо додаткової інформації про множини, у завданні не оговорюється чи повинні множини мати пусте перетинання. Для розробки алгоритму розв’язання задачі (враховуючи обмеження на введення додаткової змінної множинного типу) корисними будуть круги Ейлера, за їх допомогою простіше визначити формули перетворень над множинами.

Розглянемо два варіанти можливих вхідних даних:

Перший варіант - множини не перетинаються.

Ми автоматично попадаємо в умови відомої задачі з теорії алгоритмізації та програмування, коли необхідно обміняти місцями значення двох змінних величин, не користуючись третьою. Якщо маємо множини a та b, треба скористатися трьома такими формулами перетворень:

a := a+b

b := a-b

a := a-b

Другий варіант - множини перетинаються.

Коли множини перетинаються, формули перетворення мають такий вигляд:

a :=a+b-a*b

b :=((a+b)-a)+(a-b)

a :=((a+b)-a)+(a-b)

Зрозуміло, що другий варіант є більш складним, але й більш загальним, він включає в себе перший (більш обмежений). Тому при розв’язанні будемо використовувати формули, наведені у другому варіанті.

3. Алгоритм:

4. Типи даних обираємо такі: litera - символьний; a, b - множини символів.

5. Текст програми:

program p8;

var a,b: set of char;

litera:char;

begin

a:=[‘F’,’I’,’R’,’S’,’T’]);

b:=[‘S’,’E’,’C’,’O’,’N’,’D’];

a:=a+b-a*b;

b:=((a+b)-a)+(a-b);

a:=((a+b)-a)+(a-b);

write(‘set a = ’);

for litera:=’A’ to ‘Z’ do

if litera in a then write(litera);

writeln;

write(‘set b = ’);

for litera:=’A’ to ‘Z’ do

if litera in b then write(litera);

readln

end.

4. Тестовий приклад:

До перетворення множина a складається з елементів-літер F, I, R, S, T; множина b складається з елементів-літер S, E, C, O, N, D.

Після перетворення маємо a = {S, E, C, O, N, D}, b = {F, I, R, S, T}.

4. Робочий розрахунок:

Програма вивела такі результати роботи

set a = SECOND

set b = FIRST

Варіанти завдань

1. Для інтервалу (1,255) побудувати множину чисел, кратних 3, використовуючи відому властивість: якщо сума цифр числа кратна 3, тоді все число ділиться на 3.

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

3. Для проміжку [1,255] побудувати множину чисел, кратних 11, використовуючи таку властивість: якщо суми цифр, що знаходяться на парних і на непарних місцях числа однакові, тоді все число ділиться на 11.

4. Побудувати множину, що складається з усіх цілих чисел діапазону 1..255, що можуть бути подані у виді суми квадратів натуральних чисел n і m.

5. Для інтервалу від 1 до 255 побудувати множину чисел, кратних 5, використовуючи властивість подільності на 5: якщо в числі остання цифра 0 або 5, тоді все число ділиться на 5.

6. Скласти множину всіх пар простих чисел інтервалу від 1 до 255. Пара простих чисел - це два простих числа, різниця між якими дорівнює 2 (наприклад, 3 і 5).

7. Для інтервалу від 1 до 255 побудувати множину чисел, кратних 9, використовуючи властивість подільності на 9: якщо в числі сума цифр ділиться на 9, тоді все число ділиться на 9.

8. Арифметична прогресія задана натуральними числами a₁ і d. Побудувати множину, що складається з усіх елементів цієї прогресії, що входять у діапазон [0, 255].

9. Для інтервалу від 1 до 255 побудувати множину чисел, кратних 4, використовуючи властивість подільності на 4: якщо число, утворене двома останніми цифрами ділиться на 4, тоді все число ділиться на 4.

10. Побудувати множину, що містить усі цифри, які не входять у десятковий запис натурального числа n.

11. Побудувати множину, що складається з спільних дільників двох чисел А та В (А, B=1,…,255).

12. Вхідними даними для програми є текст - слова з рядкових латинських літер. Побудувати множину, що складається з літер, які входять у текст не менше двох разів.

13. Заповнити множину цифрами чисел Каталана < 256. Числа Каталана визначаються формулами , .

14. Побудувати множину, що складається з простих дільників деякого натурального числа А.

15. Побудувати множину, що складається з досконалих чисел в інтервалі від 1 до 255. Досконалим називається таке число, що дорівнює сумі усіх своїх дільників, за винятком самого числа, наприклад, 28=1+2+4+7+14.

16. Три множини заповнені n випадковими натуральними числами з діапазону 1..200. Знайти мінімальне із середніх арифметичних елементів цих множин.

17. Побудувати множину двозначних чисел, сума цифр яких дорівнює числу N.

18. Вхідними даними для програми є рядок символів. Сформувати множину, що складається з елементів цього рядка - цифр і знаків арифметичних операцій і підрахувати кількість елементів отриманої множини.

19. Побудувати множину, що складається з дружніх чисел в інтервалі від 1 до 255. Дружніми числами називається така пара натуральних чисел M і N, для яких сума всіх дільників числа M (крім самого числа M) дорівнює числу N, а сума всіх дільників числа N (крім самого числа N) дорівнює числу M.

20. Побудувати множину, що включає спільні кратні двох чисел А та В із діапазону 1,…,255.

21. Множина складається з n випадкових натуральних чисел із діапазону 1..255. Знайти найближчий до середнього арифметичного елемент множини.

22. Дві множини заповнені випадковою кількістю випадкових натуральних чисел < 100. Обчислити середнє геометричне максимальних елементів цих множин.

23. Вхідною інформацією для програми є n випадкових чисел з діапазону 1000..10000. Заповнити множину числами, що визначають кількість одиниць у двійковому представленні випадкових чисел.

24. Заповнити множину числами Мерсенна < 256. Число Мерсенна - це просте число, що може бути отримане за формулою 2ⁿ-1, де n теж просте число.

25. Скласти програму, що отримує множину всіх спільних шістнадцяткових цифр трьох натуральних чисел А, В, С.