33-dars: Bit va bitmask

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaKalitlar

Eshikda to’rtta qulf bor va sizda bir dasta kalit. Har kalit ba’zi qulflarni ochadi. «Qaysi qulflar ochildi?» degan holatni yozib borish uchun to’rtta katakcha yetadi: ochilgan bo’lsa bir, yopiq bo’lsa nol. Bu to’rtta katakcha — bitta son.

Bu darsdan keyin siz

• to’plamni son sifatida ifodalaysiz va uning bitlarini o’qiysiz
• barcha 2ⁿ ichki to’plamni bitta sikl bilan aylanasiz
• holatlarni to’plam bilan belgilaydigan DP yozasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·juftlikda·Qog'oz va 4 ta tanga

To’rtta tangani qatorga tering. Har tanga yozuv tomoni bilan tursa — 1, teskari bo’lsa — 0. Hozirgi holatni ikkilik son sifatida o’qing va uning o’nlik qiymatini yozing.

Endi barcha holatlarni tartib bilan chiqing: 0000, 0001, 0010… Nechtasi bor va oxirgisi qaysi son?

Nimani sezishingiz kerak

16 ta holat, oxirgisi 15. Ya’ni 0 dan 2⁴ − 1 gacha bo’lgan har son bitta holatni ifodalaydi. Endi «barcha variantni ko’rish» oddiy for siklga aylandi.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

Bitlar bilan ishlash

Kerakli amallar oz va ular Computer Fundamentals modulida ko’rilgan. Bu yerda ularning to’plam sifatidagi ma’nosi muhim.

Amal	Ma’nosi
1 << i	faqat i-bit yoqilgan son
m | (1 << i)	to’plamga i ni qo’shish
(m >> i) & 1	i to’plamda bormi
m & (m - 1)	eng past yoqilgan bitni o’chirish
m & (-m)	faqat eng past yoqilgan bit

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1maska = 02maska |= 1 << 23maska |= 1 << 04print(bin(maska), maska)5print((maska >> 2) & 1, (maska >> 1) & 1)6print(bin(maska | (1 << 1)))

Sizning bashoratingizTekshirish

Javobni ko'rish

0b101 5
1 0
0b111

To'plam {0, 2} bitta son bilan — 5 bilan — ifodalandi. Element qo'shish, tekshirish va olib tashlash bitta amalda bajariladi.

Barcha ichki to’plamlar

bitmaskbitmask

Ichki to’plamni butun son bilan ifodalash usuli: sonning i-biti i-element to’plamda bor-yo’qligini bildiradi.

barcha to'plamlarNusxalash

1sonlar = [3, 1, 4, 2]2n = len(sonlar)3eng = 04for maska in range(1 << n):5  y = sum(sonlar[i] for i in range(n) if (maska >> i) & 1)6  if y <= 6 and y > eng:7      eng = y8print(eng)

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1sonlar = [3, 1, 4, 2]2n = len(sonlar)3eng = 04for maska in range(1 << n):5  y = sum(sonlar[i] for i in range(n) if (maska >> i) & 1)6  if y <= 6 and y > eng:7      eng = y8print(eng)

Sizning bashoratingizTekshirish

Javobni ko'rish

6

Yig'indisi 6 dan oshmaydigan eng katta to'plam — masalan 3 + 1 + 2 yoki 4 + 2. Barcha 16 variant bitta sikl bilan ko'rib chiqildi.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 20	n = 25	n = 40
Barcha ichki to‘plamlar2^n	10⁶sig‘adi	10⁷sig‘adi	10¹²sig‘maydi
Holatlar bo‘yicha DP (2^k, k = 10)1	1sig‘adi	1sig‘adi	1sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

n ≤ 20 chegarasi deyarli har doim shu usulga ochiq taklif. n = 40 bo’lsa esa boshqa narsa kerak.

Bitmask ustida DP

Endi kuchliroq g’oya. Masala: k xil ko’nikma kerak, n nomzod bor, har biri ba’zi ko’nikmalarni biladi. Eng kichik jamoa nechta kishidan iborat?

To’liq izlash 2ⁿ jamoani ko’radi. Lekin erishilgan ko’nikma to’plamlari 2ᵏ ta — va odatda k ancha kichik.

tez.pyNusxalash

1nomzod = [0b011, 0b110, 0b001, 0b100]2k = 33toliq = (1 << k) - 14CHEKSIZ = 995dp = [CHEKSIZ] * (toliq + 1)6dp[0] = 07for m in range(toliq + 1):8  if dp[m] == CHEKSIZ:9      continue10  for maska in nomzod:11      yangi = m | maska12      if dp[m] + 1 < dp[yangi]:13          dp[yangi] = dp[m] + 114print(dp[toliq])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1nomzod = [0b011, 0b110, 0b001, 0b100]2k = 33toliq = (1 << k) - 14CHEKSIZ = 995dp = [CHEKSIZ] * (toliq + 1)6dp[0] = 07for m in range(toliq + 1):8  if dp[m] == CHEKSIZ:9      continue10  for maska in nomzod:11      yangi = m | maska12      if dp[m] + 1 < dp[yangi]:13          dp[yangi] = dp[m] + 114print(dp[toliq])

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Birinchi va ikkinchi nomzod birga uchala ko'nikmani qoplaydi. Holatlar soni 8 ta — nomzodlar soni 30 bo'lganda ham shuncha qoladi.

◆Asosiy g'oya

Bu 27-darsdagi knapsack bilan bir xil fikr: tanlovlar emas, holatlar sanaladi. Faqat bu yerda holat son emas, to’plam — va to’plam bitta songa siqilgan.

Foydali hiylalar

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1x = 122print(bin(x), x & (-x), x & (x - 1), bin(x >> 1))3print(bin(x).count("1"), x.bit_count())

Sizning bashoratingizTekshirish

Javobni ko'rish

0b1100 4 8 0b110
2 2

x & (-x) — eng past yoqilgan bit (Fenwick daraxti shunga qurilgan, 32-dars). x & (x-1) uni o'chiradi. bit_count() yoqilgan bitlar sonini beradi.

Sinab ko’r

Vizualda to’rtta sonning barcha 16 ta ichki to’plami ko’rib chiqiladi. Yuqori qator — maskaning bitlari.

Bitmask — barcha ichki to'plamlar

Yuqori qator — maskaning bitlari. Har bit bitta sonning taqdirini hal qiladi.

0 dan 2 darajali n gacha bo'lgan har son bitta ichki to'plamni ifodalaydi: uning bitlari qaysi elementlar olinganini ko'rsatadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. To'rtta son bor va yig'indisi 6 dan oshmaydigan eng katta to'plam kerak. Har son uchun ikki variant — olish yoki olmaslik, demak 2 darajali 4 = 16 to'plam.
2. Maska 0001: yig'indi 3 — sig'adi va yangi eng yaxshi natija.
3. Maska 0011: yig'indi 4 — sig'adi va yangi eng yaxshi natija.
4. Maska 0101: yig'indi 7 — 6 dan oshdi, bu to'plam yaramaydi.
5. Maska 0110: yig'indi 5 — sig'adi va yangi eng yaxshi natija.
6. Maska 0111: yig'indi 8 — 6 dan oshdi, bu to'plam yaramaydi.
7. Maska 1011: yig'indi 6 — sig'adi va yangi eng yaxshi natija.
8. Maska 1101: yig'indi 9 — 6 dan oshdi, bu to'plam yaramaydi.
9. Maska 1110: yig'indi 7 — 6 dan oshdi, bu to'plam yaramaydi.
10. Maska 1111: yig'indi 10 — 6 dan oshdi, bu to'plam yaramaydi.
11. Eng yaxshi natija — 6. Har to'plam bitta SON bilan ifodalandi: maskaning i-biti «i-son olindimi» degan savolga javob beradi.

bitlar

00010203

sonlar

3142

hisob

yig'indieng yaxshi0

To'rtta son bor va yig'indisi 6 dan oshmaydigan eng katta to'plam kerak. Har son uchun ikki variant — olish yoki olmaslik, demak 2 darajali 4 = 16 to'plam.

Ko'rilgan to'plam0

OrqagaO‘ynatishOldinga1/11Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

33 / 40

Masalan ta sonning barcha ichki to'plamlarini ko'rib chiqing.

Taklif qilingan yechim

1. 1maska 0 dan 2 darajali n gacha yuradi.
2. 2i-element to‘plamda bor-yo‘qligini maska & i bilan tekshiramiz.
3. 3Bor bo‘lsa uni yig‘indiga qo‘shamiz.
4. 4Har maskadan keyin eng yaxshi natijani yangilaymiz.

Bu javobning 2-qismi noto'g'ri. maska & i — bu i-bitni emas, i SONINING bitlarini tekshiradi. To'g'ri shakl: maska & (1 << i) yoki (maska >> i) & 1. Yozilgani i = 0 da har doim nol beradi va i = 3 da ikkita bitni birdan qamraydi.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1n elementli to'plamning nechta ichki to'plami bor?

Javobni ko'rish

2ⁿ. Har element uchun ikki variant — bor yoki yo’q.

2To'plamga i elementini qanday qo'shasiz?

Javobni ko'rish

m |= 1 << i. Bor-yo’qligini esa (m >> i) & 1 bilan tekshirasiz.

3n ≤ 20 chegarasi nimani ishora qiladi?

Javobni ko'rish

2ⁿ yechimni: 2²⁰ taxminan bir million, bu bemalol sig’adi. Shunchalik kichik chegara deyarli har doim ochiq taklif.

4Bitmask DP da nima sanaladi?

Javobni ko'rish

Tanlovlar emas, erishilgan to’plamlar. Ular 2ᵏ ta, k esa odatda elementlar sonidan ancha kichik.

5x & (-x) nima beradi va u qayerda ishlatilgan?

Javobni ko'rish

Eng past yoqilgan bitni. Fenwick daraxti (32-dars) butunlay shu amalga qurilgan.

Masalalar

Masalalar

3 ta

• Apple DivisionCSES 1623o'rta

  n ≤ 20. Har olma ikki guruhdan birida — bu aynan bitmask.

• Hamiltonian FlightsCSES 1690qiyin

  Holat: (ko‘rilgan shaharlar to‘plami, hozir qayerdaman). Klassik bitmask DP.

• Elevator RidesCSES 1653qiyin

  Har holat uchun ikki qiymat saqlanadi: liftlar soni va oxirgi liftdagi og‘irlik.

Lokal mashq: mashqlar/33-jamoa/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

To’rtta tangaga qaytib, 16 ta holatni ikkilik va o’nlik ko’rinishda jadvalga yozing. Keyin har holat uchun yoqilgan bitlar sonini yozing — qaysi sonlarda u eng katta?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

33-jamoa masalasini yeching. sekin.py (2ⁿ) va tez.py (2ᵏ) vaqtini n = 16, k = 10 da solishtiring.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Berilgan maskaning barcha ichki to’plamlarini aylanadigan sikl yozing. Ishora: q = (q - 1) & maska. Nega bu barcha ichki to’plamni beradi va nechta qadam qiladi?

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim