1 Востаннє редагувалося Lena_17 (22.12.2020 11:15:14)

Тема: Булеан множини

Я тільки починаю знайомитися з Pascal і мені потрібна допомога
У мене є завдання : ввести з клавіатури дві множини цілих даних.Реалізувати операцію симетричної різниці над цими множинами. Вивести на екран новоутворену множину. Реалізувати програмно побудову булеану цієї множини.

    var A,B,C:set of integer;
    x1,x2,x3,x4,x5: integer;
    y1,y2,y3,y4,y5: integer;
begin
      writeln('Введіть першу множину');
      readln(x1,x2,x3,x4,x5);
      A:=[x1,x2,x3,x4,x5];
      
      writeln('Введіть другу множину');
      readln(y1,y2,y3,y4,y5);
      B:=[y1,y2,y3,y4,y5];
      
      C:=(A+B)-(A*B);
     
      writeln('Симетрична різниця:', C);
       
    
End.

Як вивести булеан множини С? Чи можливо це взагалі?

2

Re: Булеан множини

Припустимо, що у вас Byte замість Integer. Тоді має бути щось типу такого:

var
  item: Byte;
...
  for item := Low(Byte) to High(Byte) do
    if item in C then
      write(item, ', ');
  writeln;

У мене немає класичного Паскаля, тому протестувати я цей код не можу.

В сучасному Делфі код був би такий:

for var item in C do
  write(item, ', ');
writeln;
Подякували: Lena_171

3 Востаннє редагувалося koala (22.12.2020 13:04:52)

Re: Булеан множини

Булеан найпростіше робити за допомогою двійкових чисел.
1. Фіксуєте послідовність елементів множини (наприклад, збираєте в масив способом, вказаним Torbinsом).
2. В циклі від 0 до 2кількість елементів-1 перебираєте біти змінної циклу, якщо 1 - виводите відповідний елемент. Таким чином, матимете для множини [1,2,3]:

i    двійкове представлення i    елемент булеану з [1,2,3]
0             000                        [     ]
1             001                        [1    ]
2             010                        [  2  ]
3             011                        [1,2  ]
4             100                        [    3]
5             101                        [1,  3]
6             110                        [  2,3]
7             111                        [1,2,3]
Подякували: Q-bart, Lena_17, leofun013

4

Re: Булеан множини

koala написав:

Булеан найпростіше робити за допомогою двійкових чисел.
1. Фіксуєте послідовність елементів множини (наприклад, збираєте в масив способом, вказаним Torbinsом).
2. В циклі від 0 до 2кількість елементів-1 перебираєте біти змінної циклу, якщо 1 - виводите відповідний елемент. Таким чином, матимете для множини [1,2,3]:

i    двійкове представлення i    елемент булеану з [1,2,3]
0             000                        [     ]
1             001                        [1    ]
2             010                        [  2  ]
3             011                        [1,2  ]
4             100                        [    3]
5             101                        [1,  3]
6             110                        [  2,3]
7             111                        [1,2,3]

підтверджую! Мені колись koala цей підхід теж пояснював)

5

Re: Булеан множини

Q-bart написав:

підтверджую! Мені колись koala цей підхід теж пояснював)

Зв'язок між двійковою системою, булеаном множини і біноміальними коефіцієнтами — штука цікава, особливо коли вперше ;-)

6

Re: Булеан множини

ReAl написав:
Q-bart написав:

підтверджую! Мені колись koala цей підхід теж пояснював)

Зв'язок між двійковою системою, булеаном множини і біноміальними коефіцієнтами — штука цікава, особливо коли вперше ;-)

я теж ось офігів сьогодні коли подумав. Виходить, що викладачі поставили нам завдання написати алгоритм пошуку булеану, а я просто заюзав природній алгоритм з двійкової системи. Алгоритму, як такого не розробляв.

Але зв'язок є

Прихований текст

Блін, реально пішов думати

7

Re: Булеан множини

Так а що там думати? Множина повністю тотожна функції, що для кожного об'єкту повертає "належить" чи "не належить", тобто деякій бінарній функції. Булеан - це, відповідно, множина функцій з множини в (0,1). Найпростіший спосіб перебрати всі комбінації нулів та одиниць - це двійкова система; якщо не очевидно, спитайте в Діріхле.

Подякували: Q-bart1

8

Re: Булеан множини

koala написав:

Булеан найпростіше робити за допомогою двійкових чисел.
1. Фіксуєте послідовність елементів множини (наприклад, збираєте в масив способом, вказаним Torbinsом).
2. В циклі від 0 до 2кількість елементів-1 перебираєте біти змінної циклу, якщо 1 - виводите відповідний елемент. ...

Паскалівські множини під капотом саме так і працюють. Тому який сенс винаходити велосипед, якщо усе потрібне уже вбудовано в мову? Єдина проблема в старому паскалі була вивести усе це на екран, але Делфі це успішно пофіксив.

9

Re: Булеан множини

Torbins написав:

Делфі це успішно пофіксив.

І як же в Delphi вивести булеан множини?

Подякували: leofun01, 0xDADA11C72

10

Re: Булеан множини

Я уже вище писав, якщо елементи множини є стандартними типами, то так:

for var Item in MySet do
  Write(Item, ', ');

Якщо використовується нестандартний тип, то трохи складніше:

uses
  System.TypInfo;
type
  TMySet = set of TMyEnum;
...
for var Item in MySet do
  Write(GetEnumName(TypeInfo(TMyEnum), Ord(Item)), ', ');

Хоча цей приклад трохи не реалістичний, бо якщо використовуються нестандартні типи, то малоймовірно, що їх імена будуть прямо виводитись на екран. Ну хіба що ідентифікатори на кирилиці написані. Але зазвичай там буде щось типу такого:

const
  EnumText: array[TMyEnum] of string = ('Перший', 'Другий', 'Третій');
...
for var Item in MySet do
  Write(EnumText[Item], ', ');

11

Re: Булеан множини

Ееее... А де охоплюючий

for var MySet in AllPossibleSubsetsOf(TMySet) do
  for var Item in MySet do
    Write(EnumText[Item], ', ');
Подякували: leofun011

12

Re: Булеан множини

ReAl
Ви про що взагалі? Ви хочете вивести усі можливі елементи перелічення? Це простіше робиться:

for var Item := Low(TMyEnum) to High(TMyEnum) do
  Write(EnumText[Item], ', ');

13

Re: Булеан множини

https://uk.wikipedia.org/wiki/Булеан

14

Re: Булеан множини

Ааа, дискретка. Ну тут не буде ніяких откровень, бо Делфі - не Матлаб, і навіть не Мейпл. До того ж, для великих наборів даних треба використовувати значно складніші структури. Але для поточної лаби можна реалізувати простенький алгоритм із використанням одного старого фокусу, який дозволяє уникнути зайвих приведень типів:

type
  TPowerEnum = (ps1, ps2, ps3, ps4, ps5, ps6, ps7, ps8, ps9, ps10);
  TPowerSet = set of TPowerEnum;
  TPowerArray = array[TPowerEnum] of Byte;

var
  PItems: TPowerArray;
  PEnum: TPowerEnum;
  PCount: Byte absolute PEnum;
  PSubSet: TPowerSet;
  PSubSetNum: Word absolute PSubSet;
...
  writeln('Булеан:');
  PCount := 0;
  for var Item in C do
  begin
    PItems[PEnum] := Item;
    Inc(PCount);
  end;
  for var Num := 0 to Trunc(IntPower(2, PCount)) - 1 do
  begin
    PSubSetNum := Num;
    for var PItem in PSubSet do
      write(PItems[PItem], ', ');
    writeln;
  end;
Подякували: leofun011

15

Re: Булеан множини

Ви певні, що:
- перетворення з рухомої коми не з'їсть надмірної кількості знаків при стерпних значеннях PCount (~70) - можна ж було shl скористатися;
- set у всіх версіях буде розкладений так само як і число (а не заміниться десь на big-endian, скажімо)?

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

16

Re: Булеан множини

koala
Для великих даних прості множини не підходять через обмеження по розміру, плюс у них проблеми з щільністю даних. Сам цей алгоритм також на великі дані не розрахований. Тому усе це виключно для лаби.

17

Re: Булеан множини

Ні, ну булеан від великої множини - це взагалі проблематично. Але я не знаю точно, як усередині влаштований set - там же має бути підтримка більш ніж 64 можливих елементів? Скажімо, set для 16-бітних чисел займатиме 8КБ - не так щоб мало, але й не фатально багато. А от PSubSetNum := Num у такому випадку вже не спрацює.

18

Re: Булеан множини

Якщо враховувати розміри кешів процесорів іще кілька років назад, то 8Кб - це багато. Тим більше, що у звичайних застосуваннях з тих восьми кілобайт буде піднято десятки два біт. Якщо робити для сучасних процесорів, то може й можна було б розширити, але лише до двохбайтових перелічень. Для чогось більшого усе одно треба якісь складні структури даних типу тих, що використовуються в базах даних.

19 Востаннє редагувалося ReAl (27.12.2020 16:25:29)

Re: Булеан множини

koala написав:

Але я не знаю точно, як усередині влаштований set - там же має бути підтримка більш ніж 64 можливих елементів?

У часи, коли я востаннє використовував Паскаль (це був старючий вже тоді BP6, донці в школі по інформатиці допомагав), set міг містити лише byte/char. Був це всередині масив з 32 байтів чи з 16 слів — от не знаю.

20

Re: Булеан множини

Не зрозумів про що мова в останніх кількох повідомленнях.
Для множин більших за 10 елементів: Не бачу сенсу виділяти память зразу під всі елементи булеана. Простіше зробити генератор і при потребі витягувати по 1 елемент.