2-dars: To'liq izlash

1-darajaBronza — algoritmik fikrlash1–8 darslar

HayotdaVelosiped

Velosipedingizning raqamli qulfi bor, ikkita g’ildirak, har birida 0 dan 4 gacha. Kodni unutdingiz. Ukangiz «esla-da» deydi, siz esa boshqa yo’l tanlaysiz: 00, 01, 02… Yigirma beshinchi urinishda qulf albatta ochiladi.

Bu darsdan keyin siz

• to’liq izlashni yozasiz va uning necha variant ko’rishini oldindan sanaysiz
• to’liq izlash sig’adimi-yo’qmi degan savolga chegaraga qarab javob berasiz
• to’liq izlashni tashlab yubormay, uni etalon sifatida saqlab qolasiz

Avval qo’lda

Avval qo‘lda

~5 daqiqa·juftlikda·Qog'oz va qalam

Sinfdoshingiz ikki xonali maxfiy kod o’ylasin, har xona 0 dan 4 gacha. Siz taxmin aytasiz, u faqat «yo’q» yoki «ochildi» deb javob beradi — boshqa hech qanday ishora yo’q.

Taxminlaringizni qog’ozga tartib bilan yozib boring va nechtasida ochilganini sanang. Keyin o’rin almashing.

Nimani sezishingiz kerak

Eng yomon holatda 25 urinish kerak bo’ldi, chunki variant soni aynan shuncha. Bu son o’ylab topilmaydi — u sanaladi: 5 ta birinchi xona, har biriga 5 ta ikkinchi xona.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

To’liq izlash nima

to'liq izlashbrute force

Barcha mumkin bo’lgan variantni birma-bir ko’rib chiqib, shartga mos kelganini tanlash. Hech qanday hiyla ishlatilmaydi.

To’liq izlashning ikkita kuchli tomoni bor. Birinchisi — u har doim to’g’ri javob beradi, chunki hech bir variantni o’tkazib yubormaydi. Ikkinchisi — uni yozish oson, demak unda xato qilish ham qiyin.

◆Asosiy g'oya

To’liq izlash — uyalinadigan yechim emas, boshlang’ich nuqta. Uni yozmasdan tez yechimni izlash — javobni bilmasdan tekshiruvchi yozishga o’xshaydi.

Sekin yechim

Endi haqiqiy masala. Do’konda n ta narsa bor, sizda aniq X so’m bor va uni qoldiqsiz sarflamoqchisiz — ikkita narsa olib. Nechta juftlik bunga mos keladi?

Birinchi fikr to’g’ridan-to’g’ri: har juftlikni ko’rib chiqamiz.

sekin.pyNusxalash

1narxlar = [3, 7, 5, 5, 2]2maqsad = 103soni = 04for i in range(len(narxlar)):5  for j in range(i + 1, len(narxlar)):6      if narxlar[i] + narxlar[j] == maqsad:7          soni += 18print(soni)

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

Bashorat qilingNusxalash

1narxlar = [3, 7, 5, 5, 2]2maqsad = 103soni = 04for i in range(len(narxlar)):5  for j in range(i + 1, len(narxlar)):6      if narxlar[i] + narxlar[j] == maqsad:7          soni += 18print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Ikkita juftlik: 3 + 7 va 5 + 5. Ikkita beshlik ro'yxatda alohida narsalar, shuning uchun ular haqiqiy juftlik hisoblanadi.

Diqqat qiling: ichki sikl i + 1 dan boshlanadi. Nol dan boshlansa, har juftlik ikki marta sanaladi va narsa o’zi bilan ham juftlashadi.

Nega sekin

Ichki sikl tashqi siklning har qadamida qaytadan aylanadi, ya’ni jami taxminan n²/2 ta taqqoslash bo’ladi. Kichik ro’yxatda bu sezilmaydi, lekin masalaning chegarasi n ≤ 3000 deb yozilgan.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 100	n = 3 000	n = 200 000
Har juftni ko‘rishn^2	10 000sig‘adi	10⁶sig‘adi	10¹⁰sig‘maydi
Bir marta yurishn	100sig‘adi	3 000sig‘adi	200 000sig‘adi

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

Jadvalning ma’nosi bitta: n = 3000 da to’liq izlash sig’adi, shuning uchun uni yozish kerak. n = 200000 bo’lganda esa sig’maydi va biz boshqa narsa o’ylab topishga majburmiz.

Tez yechim

Juftlikni topish uchun ikkita sonni bir vaqtda ko’rish shart emas. Ro’yxat bo’ylab bir marta yurib, har bir narx uchun kerakli sherigi ilgari uchraganmi degan savolga javob bersak yetadi.

tez.pyNusxalash

1from collections import defaultdict2narxlar = [3, 7, 5, 5, 2]3maqsad = 104korilgan = defaultdict(int)5soni = 06for narx in narxlar:7  soni += korilgan[maqsad - narx]8  korilgan[narx] += 19print(soni)

Har narx uchun maqsad - narx ni oldin nechta ko’rganimizni bilamiz — shu son javobga qo’shiladi. Lug’atdan qidirish nega deyarli bir amal turishini 9-darsda ochamiz; hozircha muhimi shu: ikkita ichma-ich sikl bitta siklga aylandi.

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

Bashorat qilingNusxalash

1from collections import defaultdict2narxlar = [3, 7, 5, 5, 2]3maqsad = 104korilgan = defaultdict(int)5soni = 06for narx in narxlar:7  soni += korilgan[maqsad - narx]8  korilgan[narx] += 19print(soni)

Sizning bashoratingizTekshirish

Javobni ko'rish

2

Javob o'zgarmadi — o'zgargani ish hajmi. Ikkita yechim bir xil javob berishi ularning ikkalasi ham to'g'ri ekanini ko'rsatadigan eng oddiy dalil.

Sinab ko’r

Quyida to’liq izlash qulfni ochmoqda. Uning butun mohiyati shu tartibda ko’rinadi: hech narsa o’tkazib yuborilmaydi va hech narsa taxmin qilinmaydi.

To'liq izlash — 25 variantli qulf

O'ynatishni bosing: algoritm hamma variantni tartib bilan sinaydi.

Qulfning 25 varianti bittalab sinaladi. To'g'risi 17-urinishda topiladi.

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

1. Qulfda ikkita g'ildirak, har birida 0–4. Demak jami 5 x 5 = 25 variant.
2. 00 sinaldi — ochilmadi.
3. 01 sinaldi — ochilmadi.
4. 02 sinaldi — ochilmadi.
5. 03 sinaldi — ochilmadi.
6. 04 sinaldi — ochilmadi.
7. 10 sinaldi — ochilmadi.
8. 11 sinaldi — ochilmadi.
9. 12 sinaldi — ochilmadi.
10. 13 sinaldi — ochilmadi.
11. 14 sinaldi — ochilmadi.
12. 20 sinaldi — ochilmadi.
13. 21 sinaldi — ochilmadi.
14. 22 sinaldi — ochilmadi.
15. 23 sinaldi — ochilmadi.
16. 24 sinaldi — ochilmadi.
17. 30 sinaldi — ochilmadi.
18. 31 sinaldi — ochilmadi.
19. 32 — ochildi! 18-urinishda topdik.
20. To'liq izlash har doim topadi. Savol bitta: variant soni sig'adimi? Uch g'ildirakda 125, oltitasida 15 625 bo'ladi.

0001020304

1011121314

2021222324

3031323334

4041424344

Qulfda ikkita g'ildirak, har birida 0–4. Demak jami 5 x 5 = 25 variant.

Urinish0

OrqagaO‘ynatishOldinga1/20Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

2 / 40

MasalaRo'yxatdan yig'indisi X ga teng juftliklar sonini toping.

Taklif qilingan yechim

1. 1Ikkita ichma-ich sikl yozamiz: i va j.
2. 2Ikkalasi ham 0 dan n-1 gacha yuradi.
3. 3narxlar[i] + narxlar[j] == X bo‘lsa hisoblagichni oshiramiz.
4. 4Sikl tugagach hisoblagichni chiqaramiz.

Bu javobning 2-qismi noto'g'ri. j ham 0 dan boshlansa, har juftlik ikki marta sanaladi — (i, j) va (j, i). Bundan tashqari i == j holatida narsa o'zi bilan juftlashadi. To'g'risi: j uchun range(i + 1, n).

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

Javobni ko'rsatish

O’zingizni sinang

1Uchta g'ildirakli, har biri 0–4 bo'lgan qulfda nechta variant bor?

Javobni ko'rish

125 ta: har g’ildirak qolganlaridan mustaqil, shuning uchun sonlar ko’paytiriladi — 5 × 5 × 5. Oltita g’ildirakda esa 15 625 bo’ladi.

2Nega to'liq izlash yozilgandan keyin ham saqlab qo'yiladi?

Javobni ko'rish

U etalon bo’lib qoladi. Tez yechim yozilgach, ikkalasini bir xil kirishda yurgizib javoblarni solishtirish mumkin — farq chiqsa, xato bor. Bu usul 15-darsda stress-test deb ataladi.

3n ≤ 3000 chegarasi bilan n² yechim sig'adimi?

Javobni ko'rish

Sig’adi. 3000 × 3000 = 9 million taqqoslash, bu bir soniyalik chegaradan ancha past. Chegara raqamlari shuning uchun shartda yoziladi: ular qaysi yechim yetarli ekanini aytadi.

4Ichki siklda i + 1 o'rniga i yozilsa nima o'zgaradi?

Javobni ko'rish

Har narsa o’zi bilan ham juftlashadi. Masalan [5, 5] va X = 10 da javob 2 emas, 4 chiqadi: (0,0), (0,1), (1,0), (1,1).

5To'liq izlash qachon yagona yechim bo'lib qoladi?

Javobni ko'rish

Variantlar soni kam bo’lganda yoki masalada hech qanday tuzilma topilmaganda. Olimpiadada ko’p masalaning qisman balli aynan to’liq izlash uchun beriladi — nol baldan ancha yaxshi.

Masalalar

Masalalar

3 ta

• Creating StringsCSES 1622oson

  Barcha o‘rin almashtirishlarni hosil qiling. Takrorlanmasligi uchun to‘plamga soling.

• Apple DivisionCSES 1623o'rta

  n ≤ 20. Har olma ikki guruhdan birida — demak 2ⁿ variant, hammasini ko‘rib chiqing.

• TeamCodeforces 231Aoson

  Har masalani alohida ko‘ring. Hech qanday hiyla kerak emas.

Lokal mashq: mashqlar/02-juftlar/ — 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

Uch xonali, har xonasi 0–2 bo’lgan qulfning barcha variantini qog’ozga tartib bilan yozib chiqing. Nechta chiqdi? Endi hisoblab tekshiring: 3 × 3 × 3. Ikki son mos keldimi?

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

02-juftlar masalasini oching va sekin.py ni o’zingiz yozing. Keyin python mashqlar/tekshir.py 02-juftlar bilan yurgizing va u nechta testda o’tganini yozib qo’ying.

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

Apple Division masalasini yeching. Yechishdan oldin daftaringizga n = 20 da nechta variant bo’lishini va bu 10⁸ chegarasiga sig’ish- sig’masligini yozing. Keyin yechimingiz haqiqatan qancha vaqt olganini o’lchang va bashoratingiz bilan solishtiring.

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

Darsni tugatdim