Raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi

 
8. Barcha kichik to'plamlar to'plami 
Bizda 4 ta komponentdan iborat to'plam bo'lsin - biz ularni mos ravishda lotin 
harflarida A, B, C, D bilan belgilaymiz. 
Va masalaning shartlariga ko'ra, qandaydir xususiyatga ega bo'lgan bir nechta 
komponentlardan iborat kichik to'plamni tanlash talab qilinadi. Muammoni hal qilishning 
shunday usuli taklif etiladi: biz berilgan to'plamning HAMMA mumkin bo'lgan kichik 
to'plamlarini yaratamiz va yaratilgan har bir kichik to'plam uchun biz berilgan 
xususiyatga mos kelishini tekshiramiz. Muammoning muqobil varianti ma'lum 
xususiyatga ega bo'lgan berilgan to'plamning BARCHA kichik to'plamlarini sanashdir. 
Misol uchun: 
4 ta belgidan iborat A,B,C,D toʻplami uchun barcha kichik toʻplamlar toʻplamiga 
quyidagi toʻplamlar kiradi: 
Bo'sh to'plam 
Yagona to'plamlar: {A}, {B}, {C}, {D} 
Ikki elementli toʻplamlar: {A,B}, {A,C}, {A,D} {B,C}, {B,D}, {C,D} 
Uch elementli to'plamlar: {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D} 
To'rt elementli to'plam: {A,B,C,D} 
Agar kichik to'plamlarni yaratish tartibi muhim bo'lmasa (va, masalan, ma'lum 
xususiyatga ega bo'lgan barcha kichik to'plamlarni sanash kerak bo'lsa, bu) barcha 
to'plamlarni yaratish uchun eng oddiy kodlangan algoritmlardan biri. quyi to'plamlar 
quyidagicha. 
Заведем вектор B, состоящий из четырех чисел, каждое из которых может 
принимать значение 0 или 1. И будем считать, что значение 1 указывает на то, что 

---

соответствующий по номеру компонент исходного множества включается в 
множество, а значение 0 указывает на то, что элемент yoqilmayapti. 
Endi 0 dan 15 gacha bo'lgan ikkilik raqamlar ketma-ketligini va ularning tegishli 
kichik to'plamlarini ko'rib chiqing: 
4321 
DCBA 
0000 - bo'sh to'plam 
0001 A 
0010B 
0011AB 
0100C 
0101AC 
Miloddan avvalgi 0110 
0111 ABC 
1000D 
Milodiy 1001 yil 
1010 BD 
1011 ABD 
1100 CD 
1101ACD 
Miloddan avvalgi 1110 yil 
1111 ABCD 
Shunday qilib, jami 4 ta elementdan iborat to'plamning 16 xil kichik to'plami 
mavjud. Umuman olganda, N ta elementlar to'plamining barcha kichik to'plamlari 
to'plami 2N (N ning kuchiga ikkita) elementni o'z ichiga oladi. 
N ta elementlarning barcha kichik to'plamlari to'plamini shunday yaratishni 
ta'minlaydigan algoritm norasmiy ravishda quyidagicha tavsiflanishi mumkin: 
Biz N noldan iborat massiv hosil qilamiz - va uni bo'sh to'plam deb hisoblaymiz. 
Shunday qilib, joriy kichik to'plamning boshlang'ich qiymati bo'sh to'plamdir. 
Joriy kichik to'plamdan keyingi kichik to'plamni olish uchun biz 0 yoki 1 
raqamlarining joriy massivini quyidagicha qayta ishlaymiz: 

---

O'ng tomonda (massivning birinchi elementidan oxirgisigacha) biz nolga teng 
bo'lgan birinchi raqamni qidiramiz. 
Agar bunday raqam topilmasa, bu joriy kichik to'plam oxirgisi - barcha 
elementlardan iborat to'plam ekanligini anglatadi va algoritm bu bilan o'z ishini tugatadi. 
Agar 0 ga teng element topilsa, u 1 bilan almashtiriladi va uning o'ng tomonidagi 
barcha raqamlar (agar mavjud bo'lsa) nolga almashtiriladi. 
Keyinchalik rasmiylashtirilgan ushbu algoritmni quyidagicha yozish mumkin: 
Kirish (N) 
N+1 elementlarning B massivini nolga solish 
Xulosa (bo'sh to'plam) 
B[N+1]=0 bo'lsa 
i=1 
B[i]=1 B[i]=0 bo'lsa , i=i+1 
B[i]=1 
Chiqish (B massivi bilan belgilangan) 
Quyida N - to'plamdagi elementlarning sonini o'qiydigan dastur matni va barcha 
kichik to'plamlar to'plamini ko'rsatadigan, elementlarni lotin harflarida mos keladigan 
tartibda bildiradi: 
const 
alifbo : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; 
var 
b : massiv [1..100] bayt; 
N,i : bayt; 
boshlash 
readln(N); 
uchun i:=1 dan N+1 gacha b[i]:=0; 
writeln (' Bo'sh o'rnatish '); 
esa (b[N+1]=0) bajaring 
boshlash 
i:=1; 
B[i]=1 qilsa 

---

startB[i]:=0; inc(i); oxiri; 
B[i]:=1; 
i:=1 uchun n qilish 
agar b[i]=1 bo'lsa, yozing (alifbo[i]); 
yozish; 
oxiri; 
oxiri. 
Agar tuzilgan kichik to'plamlarni qayta ishlash (tahlil qilish) zarur bo'lsa, B 
massivini parametr sifatida qabul qiladigan qayta ishlash protseduralariga qo'ng'iroqlar 
qo'shilishi mumkin (uning yagona elementlari bilan joriy kichik to'plamga kiritilgan 
to'plam elementlarining raqamlarini ko'rsatadi).